java - 广度优先搜索中的计数级别(起始节点和目标节点之间的距离)

Question

任何人都可以帮助我如何使用 Java 中的广度优先搜索来计算图形的访问级别？

这是我的方法，我有开始节点 (str) 和结束节点 (goal)，当循环到达目标节点时应该停止。

我现在想要的是统计从起始节点到结束节点的层数。

public void bfs(String str,String goal) {
    int strInx = findIndex(str);
    vertexList[strInx].wasVisited = true;
    theQueue.insert(strInx);
    int v2;
    boolean bre = false;
    while (!theQueue.isEmpty()) {
        System.out.println(vertexList[theQueue.getFront()].label);
        int v1 = theQueue.remove();
        while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
            vertexList[v2].wasVisited = true;
            System.out.println("--V2--->"+vertexList[v2].label);
            theQueue.insert(v2);

            if(goal.equals(vertexList[v2].label)) {
                bre=true;
                break;
            }
        }
        if(bre) 
            break;   
    }                
    for (int j = 0; j < nVerts; j++) {
        vertexList[j].wasVisited = false;
    }
}

Answer 1

您可以使用以下方法之一来跟踪当前级别:

1. 使用两个队列而不是一个:currentLevelQueue 和 nextLevelQueue

2. 使用一个队列跟踪节点，另一个队列跟踪关联层

3. 使用包含级别字段的包装类并将此类的实例存储在队列中