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 以找到最短路径。我的问题是：如果可能的话，是否可以使用 hashmap 来实现 bfs？我该怎么做？或者我应该使用哪种方法代替 hashmap 是不可能的。

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

如果可以的话，是否可以使用 hashmap 来实现 bfs 我该怎么做？或者我应该使用哪种方法代替 hashmap 是不可能的。

是的，这是可能的。您正在使用邻接列表。要实现 BFS，您将需要一个队列（Java 中有一个用于此的接口）。要遍历图表，您从队列中的单个节点开始，当此队列不为空时，您将获得下一个节点并将所有相邻节点添加到队列中，这里是您需要访问您的Map.

于 2012-12-29T22:19:39.633 回答