c - 使用cormen给出的算法在c中进行广度优先搜索

Question

我尝试了 cormen 为 bfs 指定的算法，

代码是：

    bfs(int s){
     int i;
     int u,v;
     struct edge *e;
     graph[s].colour=1;
     graph[s].d=0;
     graph[s].pre=-1;

enqueue(s);
while (isempty()!=1){
    u=dequeue();
    printf("%d\t",u);
    e=graph[u].edgePtr;
    while(e!=NULL)
    {       
        v=e->vertexIndex;
        if(graph[v].colour==WHITE){
            graph[v].colour=GRAY;
            graph[v].d=graph[u].d+1;
            graph[v].pre=u;

            enqueue(v);
            e=e->edgePtr;
        }
        graph[u].colour=BLACK;
    }
}
 }

我得到一个无限循环......有人能告诉我我到底哪里出错了吗？

Answer 1

你搞混了你的收盘价}。因此，如果颜色为 ，则仅移动到下一条边，如果颜色为非WHITE，则在无限循环中停留在同一条边上。正确的形式应该是这样的：uWHITE

bfs(int s){
  // …
  while (isempty()!=1){
    u=dequeue();
    // …
    while(e!=NULL) {       
      v=e->vertexIndex;
      if (graph[v].colour==WHITE){
        graph[v].colour=GRAY;
        graph[v].d=graph[u].d+1;
        graph[v].pre=u;

        enqueue(v);
      } // end if WHITE
      e=e->edgePtr; // update e for all colours!
    } // end loop over all edges e
    graph[u].colour=BLACK;
  } // end loop while queue is not empty
} // end function