确定无向图是否为树

Question

我对什么是有向图和无向图进行了研究。我的方法是使用DFS算法。我知道当visitedM[iVertices]为true或节点被访问两次时，这意味着它不是树。我还使用下面的定理来确定一个图是否是一棵树。

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

我的代码是通过从文件中读取顶点数和边数来初始化的，如下所示

6 7
1 2
1 5
1 6
2 5

正如您所看到的，每条边与源顶点和目标顶点列在一条线上。顶点从1开始。边是无向的，一旦以最小顶点id开始，将在文件中列出。例如，对于边2-5和5-2，文件将仅具有2-5。

我的问题是，我不知道是否应该分配节点内存，如何将节点插入到图中，如何从DFS代码中分辨出不是树。我还有void dfs作为一个int函数，返回访问顶点的计数<代码>整数dft（图形*g、整数iV、整数VisitedM[]）。该函数类似于myvoid DFS，但如果visitedM[iV]，则返回0，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);
            }
        }

Answer 1

让我给你一个稍微不同的方法来解决这个问题。

给定问题{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。

处理完所有边后，所有着色顶点都具有相同的颜色，因此图形是连接的。此外，边的数量比顶点的数量少一个。因此，图形是一棵树。