广度优先搜索不起作用100％

正在为作为链接列表数组构建的邻接矩阵做一个bfs。广度优先搜索不起作用100％

这是我的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应该返回数组中两个索引之间的最短路径）。我现在已经跑了大约14分钟了，我不知道为什么，我的意思是我假设它是因为！isEmpty（），但是如果它的白色迟早要用完，它只会增加队列中的东西。

EDITED。图出了无尽的循环问题，但BFS方法仍然不是100％

任何想法，为什么它不工作？我的意思是我遵循T的算法，但算法通常不是指一系列链表。

任何想法来解决这个问题

来源

2013-04-10 erp

您是否试图调试代码？或者只是打印sysouts atleast？ – 2013-04-10 06:45:34

是的，我正在打印输出，但想出了它为什么永远运行。但我的bfs方法仍然不起作用，也无法弄清楚。我遵循这个算法。 – erp 2013-04-10 07:08:10

问题可能是在这个while循环。你没有递增x。

int x = 0; 
while(d[x] != -1){ 
    distance = distance + d[x]; 
}

来源

2013-04-10 06:48:51 gkamal

哈哈是的，但事实证明，我的BFS方法仍然需要一些工作！感谢指出这一点！ – erp 2013-04-10 07:04:17

广度优先搜索不起作用100％

回答

相关问题