广度优先搜索中的计数级别（起始节点和目标节点之间的距离） [英] Counting levels in Breadth First Search (Distance between start node and goal node)

问题描述

有人可以帮助我如何使用Java中的广度优先搜索来计算图形的访问水平吗？

这是我的方法，我有开始节点（str）

我现在要计算的是从起始节点到结束节点的级别。 / p>

  public void bfs（String str，String target）{
 int strInx = findIndex（str）; 
 vertexList [strInx] .wasVisited = true; 
 theQueue.insert（strInx）; 
 int v2； 
布尔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; 
休息时间； 
} 
} 
 if（bre）
休息； 
} 
 for（int j = 0; j< nVerts; j ++）{
 vertexList [j] .wasVisited = false; 
} 
} 
  

解决方案

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

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




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




3. 使用一个队列包装器类，包括一个级别字段，并将此类的实例存储在队列中

Can anyone help me how to count the visited levels of a graph using Breadth First Search in Java?

Here is my method, I have start node (str) and end node (goal), when the loop reach the goal node it should be stopped.

What I want now is counting the levels from start node to end node.

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

解决方案

You can use one of the following approaches to track the current level:

1. Use two queues instead of one: currentLevelQueue and nextLevelQueue

2. Use one queue to track the nodes another one to track the associated level

3. Use a wrapper class that includes a level field and store instances of this class in the queue

这篇关于广度优先搜索中的计数级别（起始节点和目标节点之间的距离）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！