Bestimmen Sie, ob ein ungerichteter Graph ein Baum ist

Question

Ich hatte meine Forschung über was gerichtete und ungerichtete Graphen gemacht haben. Mein Ansatz ist es, den DFS-Algorithmus zu verwenden. Ich weiß, wenn visitedM[iVertices] ist true oder der Knoten zweimal besucht wird bedeutet, dass es kein Baum ist. Ich bestimme auch, ob ein Graph ein Baum ist. Ich verwende den folgenden Satz.

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

Mein Code wird durch das Lesen aus einer Datei, die Anzahl der Scheitelpunkte und Anzahl der Kanten, wie unten

6 7 
1 2 
1 5 
1 6 
2 5 

initialisieren Wie Sie jede Kante auf einer Linie mit Quellen Vertex und Ziel Vertex aufgeführt sehen . Scheitelpunkte beginnen bei 1. Kanten sind ungerichtet und werden in der Datei aufgeführt, sobald sie mit der kleinsten Scheitelpunkt-ID beginnen. Für die Kanten 2-5 und 5-2 hat die Datei beispielsweise nur 2-5.

Mein Problem ist, dass ich keine Ahnung habe, ob ich den Knotenspeicher zuweisen soll, wie füge ich den Knoten in das Diagramm ein, wie kann ich meinen DFS-Code zurückgeben, ist kein Baum. Ich habe auch die void dfs als int-Funktion, die die Anzahl der besuchten Ecken zurückgibt. int dft(grapg *g, int iV, int VisitedM[]). Die Funktion ist ähnlich wie meine void DFS, aber sie gibt 0 wenn visitedM[iV], visitedM[iV] = TRUE zurück und gibt iCount zurück. Ich nehme auch an, dass meine Datenstruktur unordentlich ist.

#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); 
      } 
     } 

Answer 1

Lassen Sie mich Ihnen einen etwas anderen Ansatz für das Problem geben.

Angesichts der Menge der Kanten in der Frage {{6,7}, {1,2}, {1,5}, {1,6}, {2,5}}, gibt es 5 Ecken {1,2,5,6,7} und 5 Kanten. Wir schließen sofort, dass der Graph kein Baum sein kann, da nach dem Theorem ein Graph mit 5 Ecken 4 Kanten haben muss.

Um das Problem ein wenig schwieriger zu machen, entfernen Sie eine der Kanten und lassen {{6,7}, {1,2}, {1,6}, {2,5}}. Jetzt haben wir die richtige Anzahl von Kanten, so müssen wir nach dem Theorem nur beweisen, dass der Graph verbunden ist. Dies kann durch Färbung des Graphen erfolgen.

---

Um ein Graphen Farbe, implementieren diese drei Regeln

• wenn eine Kante zwei ungefärbt Eckpunkte verbindet, liefert dem Eckpunkten eine neue Farbe
• wenn eine Kante einen farbigen Scheitel zu einem ungefärbten Vertex verbindet , weisen die Farbe auf die ungefärbte Vertex
• wenn eine Kante zwei unterschiedlich gefärbte Vertices verbindet, dann die Farben in eine einzelne Farb-merge

Wenn jeder Scheitelpunkt die gleiche Farbe hat, ist der Graph verbunden.

---

Die folgende Tabelle zeigt, wie sich die Farbzuordnungen im Laufe der Zeit ändern, wenn eine Kante bearbeitet wird.

 |  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 

Zu Beginn werden alle Scheitel ungefärbt, durch die Zahl 0. Der erste Rand angegeben {6,7} ordnet eine neue Farbe zu Eckpunkten 6 und 7. Die zweite Kante {1,2} weist den Scheitelpunkten 1 und 2 eine neue Farbe zu.Die dritte Kante {1,6} verbindet Scheitelpunkte, die unterschiedliche Farben haben, so dass alle Scheitelpunkte mit Farbe 2 in Farbe 1 geändert werden. Die letzte Kante {2,5} verbindet einen farbigen Scheitelpunkt mit einem ungefärbten Scheitelpunkt, also wird Farbe 1 zugewiesen Vertex 5.

Nachdem alle Kanten verarbeitet wurden, haben alle farbigen Scheitelpunkte die gleiche Farbe, sodass der Graph verbunden ist. Außerdem ist die Anzahl der Kanten um eins kleiner als die Anzahl der Ecken. Daher ist das Diagramm ein Baum.