c - 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);


}

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

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，我猜这意味着某些内容已被修改。

然后

}while(modified != 0);

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

您希望最初将modified设置为0，并在内部if中将其更改为1。