0

無向グラフを作成しようとしているので、以下のコードを使用して、実行後にグラフを作成しました。出力は次のとおりです。

{1=[2, 5, 10, 18], 
 2=[1, 3], 3=[2, 4], 
 4=[3, 5], 5=[1, 4, 6], 
 6=[5, 7], 7=[6, 8], 
 8=[7, 9], 9=[8], 10=[1, 11], 
 11=[10, 12, 13, 11, 11], 
 12=[11, 19], 13=[11], 
 19=[12], 18=[1], 
 21=[22], 22=[21]}

今、最短経路を見つけるために BFS を実装しようとしています。私の質問は: ハッシュマップを使用して bfs を実装することは可能ですか? または、ハッシュマップの代わりにどの方法を使用すればよいかわかりません。

Map<Integer, ArrayList<Integer>> adj;

public Graph(ArrayList<String> nodes) {
    adj = new HashMap<Integer, ArrayList<Integer>>();
    for (int i = 0; i < nodes.size(); ++i) {
        adj.put(Integer.parseInt(nodes.get(i)), new ArrayList<Integer>());
        }
    }

public void addNeighbor(int v1, int v2) {
    adj.get(v1).add(v2);
}
4

1 に答える 1

1

可能な場合、ハッシュマップを使用して bfs を実装することは可能ですか? または、ハッシュマップの代わりにどの方法を使用すればよいかわかりません。

はい、可能です。隣接リストを使用しています。BFS を実装するには、キューが必要です (Java にはこのためのインターフェースがあります)。グラフをトラバースするには、キュー内の 1 つのノードから開始します。このキューが空でない間に、次のノードを取得し、隣接するすべてのノードをキューに追加します。ここで にアクセスする必要がありますMap。

于 2012-12-29T22:19:39.633 に答える