判断无向图G是否是一棵树

王道P221，综合应用题第二题

判断图是否是一棵树，需要两个条件

• G是连通图
• G的边数比顶点数少1，edge = vertex - 1

算法思路，对第一个顶点调用一次DFS，如果能一次访问完所有的结点，那么说明此图连通，在DFS的过程中，访问当前节点的下一个节点时候，说明有一条边，维护边数的Edgeum变量自增。最后 如果访问过的顶点数和实际的顶点数相同说明联通，同时如果边数等于节点数-1说明该就是树了。

这里有一个小细节要注意，无向图的邻接表中，结点a和b之间的边其实存放了两次，一次是a -> b，另一次是b -> a。比如可以看看综合应用题的第一题1到2有一条边，2到1也有一条边，因此最后总的边数需要除以2才是真正的边的数目。

bool visited[MaxVertexNum];
int EdgeNum = 0, VexNum = 0;

//DFS，可以返回一次遍历返回的边的数目和结点的数目
void DFS(ALGraph G, int i) {
    visited[i] = true;
    VexNum ++;

    ArcNode * p = G.vertices[i].first;
    while(p) {    
        EdgeNum ++;    //访问当前节点的下一个结点时，边数+1
        if(!visited[p -> adjvex]) {                      
            DFS(G, p -> adjvex);
        }
        p = p -> next;
    }
}

bool IsTree(ALGraph G) {    
    for(int i = 0; i < G.vertexnum; ++i) {
        visited[i] = false;
    }
    DFS(G, 0);
    if(VexNum == G.vertexnum && EdgeNum / 2 ==  (G.vertexnum - 1)) //如果连通并且边数 = 节点数 - 1，则说明是树
        return true;
    return false;
}

完整代码：

#include<iostream>
using namespace std;

#define MaxVertexNum 100
#define VertexType char

//边表结点
typedef struct ArcNode { 
    int adjvex;          //存储该结点在顶点表中的下标
    ArcNode * next;      //指向下一个边表
}ArcNode;

//顶点表结点
typedef struct VNode {  
    VertexType data;            //顶点信息
    ArcNode * first;             //指向边表
} VNode, AdjList[MaxVertexNum]; //顶点和顶点表

//图的存储结构
typedef struct {       
    AdjList vertices;  //邻接表
    int vertexnum, arcnum; //维护图的顶点数和边的个数
} ALGraph;


//找到结点x在顶点表中的位置
int LocateVex(ALGraph & G, VertexType x) {
    for(int i = 0; i < G.vertexnum; i ++) {
        if(x == G.vertices[i].data) 
            return i;
    }
    return -1;
}

void CreateALGrapha(ALGraph & G) {
    //cout << "输入顶点数和边数：";
    cin >> G.vertexnum >> G.arcnum;
    for(int i = 0; i < G.vertexnum; ++i) {
        //cout << "输入第" << i + 1 << "个顶点的信息：";
        cin >> G.vertices[i].data;
        G.vertices[i].first = NULL;
    }

    for(int i = 0; i < G.arcnum; ++i) {
        VertexType e1, e2;
        //cout << "输入第" << i + 1 << "条边的顶点：";
        cin >> e1 >> e2;
        ArcNode * e = new ArcNode;
        if(!e) {
            cout << "内存分配失败：" << endl;
            exit(0);
        }
        
        int vi = LocateVex(G, e1);
        int vj = LocateVex(G, e2);

        //e1和e2之间有一条边，先用头插法将e2的边表插到e1的顶点表后
        e -> adjvex = vj;
        e -> next = G.vertices[vi].first;
        G.vertices[vi].first = e;
		
        e = new ArcNode;
        if(!e) {
            cout << "内存分配失败：" << endl;
            exit(0);
        }        
        //再将e1的边表插到e2的顶点表
        e -> adjvex = vi;
        e -> next = G.vertices[vj].first;
        G.vertices[vj].first = e;
    }
}

bool visited[MaxVertexNum];
int EdgeNum = 0, VexNum = 0;

//DFS，可以返回一次遍历返回的边的数目和结点的数目
void DFS(ALGraph G, int i) {
    visited[i] = true;
    VexNum ++;

    ArcNode * p = G.vertices[i].first;
    while(p) {    
        EdgeNum ++;    
        if(!visited[p -> adjvex]) {                      
            DFS(G, p -> adjvex);
        }
        p = p -> next;
    }
}

bool IsTree(ALGraph G) {    
    for(int i = 0; i < G.vertexnum; ++i) {
        visited[i] = false;
    }
    DFS(G, 0);
    if(VexNum == G.vertexnum && EdgeNum / 2 ==  (G.vertexnum - 1)) //一条边会被两次访问,除2
        return true;
    return false;
}

int main() {
    ALGraph G;
    CreateALGrapha(G);
    if(IsTree(G)) {
        cout << "树" << endl;
    } else {
        cout << "图" << endl;
    }
    return 0;
}

/*
图的输入样例如下
5 7
a b c d e
a b
a e
b c
b d
b e
c d
d e
树的输入样例如下
5 4
a b c d e
a b
a c
a d
b e
*/