检查图形是否使用BFS连接并打印MST

Question

我在邻接列表中存储了一个包含节点1,2,3,4 ...的图形。 我写了这段代码来做广度优先搜索（BFS）。 BFS的工作原理非常完美，但我不知道程序是查找图形是连接还是断开连接，然后打印图形的最小生成树（如果连接的话）？ 我存储在邻接表图的一个例子：对BFS

1 3 4 
2 4 
3 1 4 
4 2 1 3 

，代码：

int visit[999] = { 0 }; 
Q.enqueue(0); 
while (!Q.isEmpty()) 
    { 
      y = Q.dequeue(); 

      traverse = g[y]; 

      while (traverse->link != 0) 
      { 

       if (visit[traverse->data-1] == 0) 
       { 

        visit[traverse->data-1] = 1; 
        parent = traverse->data; 
        Q.enqueue(traverse->data-1); 
       } 
       traverse = traverse->link; 


      } 

      if (visit[traverse->data - 1] == 0) 
      { 

       visit[traverse->data - 1] = 1; 
       parent = traverse->data; 
       Q.enqueue(traverse->data - 1); 
      } 

    } 

Answer 1

所以我理解了它，并把它作为其他基准:)

int parent = 1; 
    gcounter++; 
    p = 0; 
    int visit[999] = { 0 }; 
    int c[999] = { 0 }; 
    int k = 0; 
    int z = 0; 
    Queue Q; 
    Q.enqueue(0); 
    while (!Q.isEmpty()) 
    { 
      y = Q.dequeue(); 
      traverse = g[y]; 

      while (traverse->link != 0) 
      { 

       if (visit[traverse->data-1] == 0) 
       { 

        if (y + 1 != traverse->data) 
        { 
         c[z] = y + 1;z++; 
         c[z] = traverse->data; z++; 

        } 
        p++; 
        visit[traverse->data-1] = 1; 
        parent = traverse->data; 
        Q.enqueue(traverse->data-1); 
       } 
       traverse = traverse->link; 


      } 

      if (visit[traverse->data - 1] == 0) 
      { 

       if (y + 1 != traverse->data) 
       { 
        c[z] = y + 1; z++; 
        c[z] = traverse->data; z++; 
       } 
       p++; 
       visit[traverse->data - 1] = 1; 
       parent = traverse->data; 
       Q.enqueue(traverse->data - 1); 
      } 

    } 



     if (p < lcounter) //lcounter-> the lines -> total number of nodes 
     { 
      writeFile << "The Graph is disconnected" << endl; 


     } 
     else 
     { 
      writeFile << "The Graph is connected and it's MST is: "; 
      for (z = 0; c[z+1] != 0; z++) 
      { 
       writeFile << "(" << c[z] << "," << c[z + 1] << ") "; 
       z++; 
      } 
      writeFile << endl; 

     }