LoginSignup
0
0

More than 3 years have passed since last update.

重みあり有向グラフの隣接行列と隣接リスト(Java)

Posted at

問題

重みあり有効グラフの隣接行列と隣接リスト
可変長配列がちょっとややこしいJavaで厄介なのは隣接リスト。

でも「もう配列は現場で使わないかな。Listが基本だと思う」とTwitterでフォロワーに言われたので慣れましょうとかなんとか。
現場に入る未来があるかどうかは別として。

コード

import java.util.Scanner;
import java.util.ArrayList;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] gl = new int[n][n]; //隣接行列
        ArrayList<TreeMap<Integer, Integer>> al = new ArrayList<TreeMap<Integer, Integer>>(); //隣接グラフ

        for(int i=0; i<n; i++){
            TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>();   //グラフ初期化
            al.add(tm);
        }

        for(int i=0; i<m; i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1; //aからbに向かう枝が
            int k = sc.nextInt();

            gl[a][b] = k;   //行列を1にする

            al.get(a).put(b, k);
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                System.out.print(gl[i][j]);
            }
            System.out.println("");
        }

        // System.out.println(al);

        for(int i=0; i<n; i++){     //グラフ表示
            for(Integer key : al.get(i).keySet()){
                System.out.print(key + "(" + al.get(i).get(key) + ")");
            }
            System.out.println("");
        }
    }
}

覚書

1.新しくクラスを作ってみるなど迷走したが、HashMapを使えばいいんだと気づく。

2.HashMapだと「keyの順番(ノード名)」でソートするところで躓いたので、TreeMapで実装。

3.何気に一番時間かかったのここだと思う。外側のArrayListを順番に取ってきて、中のTreeMapのkeyを取ってきて(このfor文の書き方も覚えないとだな……)、key表示とkeyの中身を……

        for(int i=0; i<n; i++){     //グラフ表示
            for(Integer key : al.get(i).keySet()){
                System.out.print(key + "(" + al.get(i).get(key) + ")");
            }
            System.out.println("");
        }

参考

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0