Determine if an undirected Graph is a tree

Question

I had made my research about what are directed and undirected graphs. My approach is to use DFS algorithm. I know when visitedM[iVertices] is true or the node is visited twice it means it is not a tree. I also determine whether a graph is a tree I use the following theorem.

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

My code is initialize by reading from a file the number of vertices and number of edges as below

As you can see each edge is listed on one line with source vertex and destination vertex. Vertices start at 1. Edges are undirected and will be listed on the file once starting with the smallest vertex id. For example, for edges 2-5 and 5-2 the file will only have 2-5.

My problem is that I have no idea if i should allocate the node memory, how do I insert the node into the graph, how do I tell back my from DFS code is not a tree. I also have the void dfs as an int function that returns the count of visited vertices. int dft(grapg *g, int iV, int VisitedM[]). the function is similar to my void DFS, but it returns 0 if visitedM[iV], visitedM[iV] = TRUE, and returns iCount. I also presume my data structure is messy.

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

user3386109 user3386109 · Accepted Answer · 2016-04-23T21:55:35

Let me give you a slightly different approach to the problem.

Given the set of edges in the question {{6,7}, {1,2}, {1,5}, {1,6}, {2,5}}, there are 5 vertices {1,2,5,6,7} and 5 edges. We immediately conclude that the graph cannot be a tree, since according to the theorem, a graph with 5 vertices must have 4 edges.

To make the problem a little harder, remove one of the edges, leaving {{6,7}, {1,2}, {1,6}, {2,5}}. Now we have the correct number of edges, so according to the theorem, we just need to prove that the graph is connected. This can be done by coloring the graph.

To color a graph, implement these three rules

if an edge connects two uncolored vertices, give those vertices a new color
if an edge connects a colored vertex to an uncolored vertex, assign the color to the uncolored vertex
if an edge connects two differently colored vertices, then merge those colors into a single color

If every vertex ends up with the same color, then the graph is connected.

The following table shows how the color assignments change over time as each edge is processed.

       |     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

At the start, all of the vertices are uncolored, indicated by the number 0. The first edge {6,7} assigns a new color to vertices 6 and 7. The second edge {1,2} assigns a new color to vertices 1 and 2. The third edge {1,6} connects vertices that have different colors, so all vertices with color 2 are changed to color 1. The final edge {2,5} connects a colored vertex with an uncolored vertex, so color 1 is assigned to vertex 5.

After all the edges are processed, all of the colored vertices have the same color, so the graph is connected. Also, the number of edges is one less than the number of vertices. Therefore the graph is a tree.

Determine if an undirected Graph is a tree

1 Answers