java - 计算广度优先搜索中遍历的边数？

Question

这是我的 bfs 算法。我想存储我在字段边缘中遍历的边数，但我无法弄清楚在哪里放置变量来为每个边添加一个。我不断得到太长的答案，所以我认为这比简单地增加边缘更难。

应该注意的是，这应该只计算沿着真实路径的边缘，而不是额外的边缘。

public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        x.visited = true;
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return edges;
            }
            for(Vertex n: t.neighbours){
                if(!n.visited){
                    n.visited = true;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return edges;   
    }

感谢任何和所有帮助。如果您需要更多类(class)/方法，请告诉我

编辑

import java.util.ArrayList;

public class Vertex {

    public static char currentID = 'a';
    protected ArrayList<Vertex> neighbours;
    protected char id;
    protected boolean visited = false;
    protected Vertex cameFrom = null;
    public Vertex(){
        neighbours = new ArrayList<Vertex>();
        id = currentID;
        currentID++;
        Graph.all.add(this);
    }
    public void addNeighbour(Vertex x){
        int a;
        while(x == this){
             a = (int) (Math.random()*(Graph.all.size()));
             x = Graph.all.get(a);
        }           
            if(!(neighbours.contains(x))){
                neighbours.add(x);
                x.addNeighbour(this);
                //System.out.println(this + " Linking to " + x);
            }
    }
    public void printNeighbours(){
        System.out.println("The neighbours of: " + id + " are: " + neighbours);
    }
    public String toString(){
        return id + "";
    }

}

Answer 1

在您的 Vertex 中类，创建一个 Vertex cameFrom您设置为指向 Vertex 的字段你来自访问该节点的时间。您甚至可以替换您的 boolean visited字段(如果是 null 则 Vertex 尚未被访问过)。

然后，当你找到Vertex y时只需按照指针返回 Vertex x计算您行走时走了多少步。

如果您不想更改 Vertex类，然后保留一个 Map<Vertex,Vertex>在您的搜索过程中，它存储从您正在访问的顶点到您来自的顶点的映射。当你到达终点时，你可以以同样的方式沿着路径到达起点。

---

也许是这样的:

    public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return pathLength( t );
            }
            for(Vertex n: t.neighbours){
                if(n.cameFrom == null || n != x){
                    n.cameFrom = t;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return -1;  
    }

    public int pathLength( Vertex v )
    {
       int path = 0;

       while ( v.cameFrom != null )
       {
         v = v.cameFrom;
         path++;
       }

       return path;
    }