0

私は 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;
    }
}
 }

私は無限ループを取得しています...誰かが正確にどこが間違っているのか教えてもらえますか??

4

1 に答える 1

0

クロージングを間違え}ました。結果として、色が の場合にのみ次のエッジに移動し、 の色がで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
于 2013-03-21T08:52:49.097 に答える