致力于为邻接矩阵做一个 bfs,它被构建为一个链表数组。
这是我的 bfs 方法,接收链表数组和起始位置:
public static int bfs(List<Integer>[] smallWorld, int start){
int distance = 0;
int size = smallWorld.length;
//for each location in smallWorld do a bfs to every other location
int u;
int white = 0, grey = 1, black = 2;
int [] color, d, pie;
Queue <Integer> q = new <Integer> LinkedList();
color = new int [size];
d = new int [size];
pie = new int [size];
for( int x = 0; x < size; x++){
color[x] = white;
d[x] = -1;
pie[x] = -1;
}
color[start] = grey;
d[start] = 0;
pie[start] = -1;
q.addAll(smallWorld[start]); //enqueue the adjacent items
while(!q.isEmpty()){
u = q.remove();
for(int v = 0; v < smallWorld[u].size(); v++){ //for every vertex u is adjacent to
if(color[v] == white){
color[v] = grey;
d[v] = d[u] + 1;
pie[v] = u;
q.addAll(smallWorld[v]);
}
}
color[u] = black;
}
int x = 0;
while(d[x] != -1){
distance = distance + d[x];
x++;
}
实际上 smallWorld 的长度为 500,但出于测试目的,我只是对数组中的第一个索引执行 bfs。 (你知道 bfs 应该返回数组中 2 个索引之间的最短路径)。我的现在已经运行了大约 14 分钟,我不确定为什么,我的意思是我假设它是因为 !isEmpty() 但是如果它迟早会用完,那只会向队列中添加东西。
已编辑。解决了无限循环问题,但 BFS 方法仍然不是 100%
知道为什么它不起作用吗?我的意思是我按照算法到了 T,但算法通常不是指链表数组。
解决这个问题的任何想法
最佳答案
问题可能出在这个 while 循环中。你没有递增 x。
int x = 0;
while(d[x] != -1){
distance = distance + d[x];
}
关于java - 广度优先搜索 100% 无效,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15918751/