java - 使用 Map> 的 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

Is it possible to use the hashmap to implement bfs if it is possible how can i do it? or it is not possible which method should i use instead of hashmap.

是的，这是可能的。您正在使用邻接表。要实现 BFS，您需要一个队列(Java 中有一个接口(interface))。要遍历图表，您从队列中的单个节点开始，虽然该队列不为空，但您会获取下一个节点并将所有相邻节点添加到队列中，这里是您需要访问 Map.