c - 确定无向图是否为树

我研究了什么是有向图和无向图我的方法是使用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[])。函数与myvoid DFS类似，但返回0
如果visitedM[iV]，visitedM[iV] = TRUE，则返回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);
            }
        }

最佳答案

让我给你一个稍微不同的方法来解决这个问题。
给定问题中的边集{{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。
处理完所有边后，所有着色的顶点都具有相同的颜色，因此图是连接的此外，边的数量比顶点的数量少一个因此图是一棵树。