gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 05:50:56 25 4
gpt4 key购买 nike

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

}

最佳答案

在您的 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;
}

关于java - 计算广度优先搜索中遍历的边数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10060144/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com