檢查圖形是否使用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; 

     }