使用Map<Integer、ArrayList<Integer>>的BFS

Question

我正在尝试创建一个无向图，所以我使用以下代码在执行后创建了一个图，我得到的输出是：

{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);
}

Answer 1

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

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