C 中的 BFS 实现不会终止

Question

这是我在 C 中实现的 BFS

void bfs(int* vertices, Edge* edges, int num_vertices, int num_edges){

    int level = 0;
    int modified;

    //continue looping till all vertices have not been updated
    do{
        modified = 1;
        for (int i = 0; i < num_edges; ++i)
        {

            int first = edges[i].first;
            int second = edges[i].second;

            if ((vertices[first] == level) &&(vertices[second] == -1))
            {
                vertices[second] = level + 1;
                modified = 0;

            }else if (vertices[second]== level && (vertices[first] == -1))
            {
                vertices[first] = level + 1;
                modified = 0;

            }

        }//end of for
        level++;
    }while(modified != 0);


}

代码应该写入对应于顶点数组中的起始顶点的每个顶点的级别。使用此函数初始化数组。

void initialize_vertices(int* vertices, int size, int start_vertex){

    for (int i = 0; i < size; ++i)
    {
        if(i == start_vertex){
            vertices[i] = 0;
        }else{
            vertices[i] = -1;
        }

    }

}

一条边定义如下

    typedef struct Edge{
        int first;
        int second;
    }Edge;

这是我调用的主函数。

int main(int argc, char** argv){

    const int NUM_VERTICES = 128;
    const int NUM_EDGES = 128;
    const int START_VERTEX = 25;


    clock_t begin, end;
    double time_spent;

    int vertices[NUM_VERTICES];
    Edge edges[NUM_EDGES];



    //data set
    for (int i = 0; i < NUM_EDGES; ++i)   
    {
        edges[i].first = (rand() % (NUM_VERTICES+1));
        edges[i].second = (rand() % (NUM_VERTICES+1));
    }



    initialize_vertices(vertices, NUM_VERTICES, START_VERTEX);


    begin = clock();
    bfs(vertices, edges, NUM_VERTICES, NUM_EDGES);
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("Time taken: %f\n", time_spent);

    for (int i = 0; i < NUM_VERTICES; ++i)
    {
        printf("%d : %d", i, vertices[i]);
        printf(((i % 4) != 3) ? "\t":"\n");
    }

    return 0;

}

问题是代码永远不会终止。我做错了什么，感谢任何帮助。

Answer 1

如果您不修改任何内容，请重新进入循环。这似乎是你的问题。

您在循环开始时设置了 modified = 1，只有在发生变化时才将其更改为 0。当你最后问 modified != 0 它会 return true 当且仅当没有变化时。

Answer 2

你的 modified 逻辑有问题。

默认情况下，您将 modified 设置为 1，我猜这意味着某些内容已被修改。

然后

}while(modified != 0);

如果有任何修改，则正确循环。

您想将 modified 初始设置为 0 并在内部 if.

中将其更改为 1

C 中的 BFS 实现不会终止

BFS implementation in C doesn't terminate

c

breadth-first-search