確定一個無向圖是否是樹

我已經對什麼是有向圖和無向圖進行了研究。我的方法是使用DFS算法。我知道當visitedM[iVertices]是true或節點被訪問兩次，這意味着它不是一棵樹。我還確定一個圖是否是一棵樹，我使用下面的定理。確定一個無向圖是否是樹

Theorem: Any connected graph with n vertices and n-1 edges is a tree

我的代碼是由從文件中讀取邊緣的頂點的數量和數量如下

正如你可以看到每個邊緣上列出與源頂點和目標頂點一行初始化。頂點從1開始。邊緣是無向的，一旦從最小的頂點ID開始，將在文件上列出。例如，對於邊緣2-5和5-2，文件只有2-5。

我的問題是，我不知道如果我應該分配節點內存，如何將節點插入圖中，我如何告訴我從DFS代碼不是一棵樹。我還將void dfs作爲int函數返回訪問頂點的數量。 int dft(grapg *g, int iV, int VisitedM[])。該函數與我的void DFS類似，但如果visitedM[iV]，visitedM[iV] = TRUE返回0 ，並且返回iCount。我也假設我的數據結構很混亂。

#define MAX_VERTICES 100 
typedef struct EdgeNode 
{ 
    int y; 
    int w;   //weight 
    int iVertex  //susbcript in vertexM for TO Vertex 
    struct EdgeNode *pNextEdge; 
}EdgeNode; 

typedef struct Vertex 
{ 
    char szLabel[100 +1 ]; 
    EdgeNode *successorList; 
}Vertex; 

typedef struct 
{ 
    int iNumVertices; 
    int iNumEdges; 
    int iDirected; 
    Vertex vertexM[MAX_VERTICES +1]; 

    int iParent[MAX_VERTICES + 1]; 
    int iVisitedM[MAX_VERTICES + 1]; 

    int degree[MAX_VERTICES + 1]; 
    EdgeNode *edge[MAX_VERTICES +1]; 
}GraphImp; 
typedef GraphImp *Graph; 


    int main(int argc, char *argv[]) 
    { 
     FILE *pFile; 
     Graph graph; 
     char szInputBuffer[100]; 
     int numEdges, numVertices; 
     pFile = fopen("a.txt","r"); 

     if(pFile == NULL) 
     { 
      printf("FILE DOES NOT EXIST \n"); 
      return; 
     } 
     //reads file until EOF 
     while(fscanf(pFile, "%d%d", &graph.iVertices, &graph.iEdges) != EOF) 
     { 
      //printf is to track the input from file 
      printf("num of vertices: %d \n num of edeges: %d \n",graph.iVertices, graph.iEdges); 
     } 

     fclose(pFile); 
    } 
      void dft(Graph *g, int iV, int visitedM[]) 
     { 
      EdgeNode *e; 
      if(visitedM[iV]) 
       return; 
      for(e = g->vertexM[iV].sucessorList; e!= NULL; e = e->pNextEdge) 
      { 
       dft(g, e->iVertex, visitedM); 
      } 
     }

來源

2016-04-23 Eduardo Juarez

讓我給你一個稍微不同的方法來解決這個問題。

給定問題{{6,7}, {1,2}, {1,5}, {1,6}, {2,5}}中的邊集，有5個頂點{1,2,5,6,7}和5個邊。我們馬上得出結論，該圖不能是樹，因爲根據該定理，具有5個頂點的圖必須具有4個邊。

爲了使問題變得更加困難，請刪除其中一條邊，並留下{{6,7}, {1,2}, {1,6}, {2,5}}。現在我們有正確的邊數，所以根據定理，我們只需要證明圖連接了。這可以通過爲圖表着色來完成。

顏色的圖形，實現這三個規則

如果邊緣連接兩個未着色頂點，給那些頂點的新顏色
如果邊緣着色頂點連接到未着色頂點，如果邊連接兩個不同顏色的頂點，然後將這些顏色合併爲單一顏色，將顏色分配給未着色頂點

如果每個頂點都以相同的顏色結束，則會連接該圖形。

下表顯示了處理每條邊時顏色分配隨時間變化的方式。

 |  color assignments 
vertex | start {6,7} {1,2} {1,6} {2,5} 
-------+------------------------------- 
    1 | 0  0  2  1  1 
    2 | 0  0  2  1  1 
    3 | 0  0  0  0  0 
    4 | 0  0  0  0  0 
    5 | 0  0  0  0  1 
    6 | 0  1  1  1  1 
    7 | 0  1  1  1  1

在開始時，所有頂點都未着色，由數字0第一邊緣{6,7-}指示分配一個新的顏色到頂點6和7第二邊緣{1,2}爲頂點1和頂點2分配一個新的顏色。第三條邊{1,6}連接具有不同顏色的頂點，因此所有具有顏色2的頂點都將更改爲顏色1.最終邊{2,5}將彩色頂點與未着色頂點連接起來，因此將顏色1分配給頂點5.

處理完所有邊後，所有彩色頂點都具有相同顏色，因此圖形已連接。另外，邊的數量比頂點的數量少一個。因此該圖是一棵樹。

來源

2016-04-23 21:55:35 user3386109

我明白你的方法。但是，在鄰接列表或鄰接矩陣之間實現此算法會更好嗎？ –

@EduardoJuarez都不是。每條邊只需要一次。所以代碼可以從文件中讀取邊緣，更新顏色信息並放棄邊緣。沒有必要存儲邊緣。 – user3386109

我需要分配內存嗎？ –

確定一個無向圖是否是樹

回答

相關問題