2

这是我的 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;   
    }

任何和所有的帮助表示赞赏。如果您需要更多课程/方法，请告诉我

编辑

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

}
4

2 回答 2

2

在您的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;
    }
于 2012-04-08T04:06:55.120 回答
1

在这个例子中，边的数量就是search. 队列。

编辑：

一种可能的解决方案是逐层进行。假设您询问顶点 A，F 之间的距离

图表看起来像：

A
|\
B C
|
D
|\
E F

首先计算A和B，C之间的距离（这很容易，因为B和C是A的直接邻居。然后计算A和D之间的距离（这很容易，因为D是B的直接邻居，然后是A和E， F. 将距离存储在 A 顶点节点中。现在运行 BFS 并确定搜索结果后，您可以简单地询问距离。看这个可视化图表。

于 2012-04-08T03:47:29.940 回答