博客

/**
 * 王道书 P217 T02 + 拓展 ：判断无向连通图是否有环
 *
 * ①算法思想
 * 若是一棵树，首先是连通的，判断连通的方法：
 * 1° 如果只调用了一次Traverse里面的DFS()或者BFS()，说明是连通的。
 * 2° 统计顶点个数，如果经过一次遍历之后，涉及到的顶点个数和给的图G的顶点个数相等、
 *    且统计边数，如果涉及到的边数是（顶点的个数 - 1） * 2，
 *    则说明是一棵树。
 * 拓展：
 * 无向连通图，如果有环则一定不是树，无环则一定是树。
 *
 * ②算法设计
 */

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <malloc.h>
#include <cstdlib>
#define MaxSize 20
#define INF 999999


//王道书 P217 T02 判断无向图是否是一棵树（用邻接表表示）
//拓展：判断无向连通图是否有环（最后返回的true和false颠倒一下）
//如果是非连通图，那么就对几个子部分分别进行判断
struct ArcNode{
    int adjvex;
    struct ArcNode *next;
    int weight;
};
struct VNode{
    char value;
    struct ArcNode *first;
};
struct AdGraph{
    VNode vertices[MaxSize];
    int vexnum,arcnum;
};
void DFS(AdGraph G,int v,int &nodenum,int &edgenum,int *visited){//v是起点顶点的下标，对顶点数（nodenum）和边数（edgenum）进行修改，用&最后可以带回
    visited[v] = 1;
    nodenum++;
    ArcNode *p = G.vertices[v].first;
    while(p){//递归
        edgenum++;
        if(!visited[p -> adjvex])
            DFS(G,p -> adjvex,nodenum,edgenum,visited);
        p = p -> next;
    }
}
bool IsTree(AdGraph G){
    int visited[MaxSize];
    for (int i = 0; i < G.vexnum; ++i) {//初始化
        visited[i] = 0;
    }
    int nodenum = 0,edgenum = 0;
    DFS(G,0,nodenum,edgenum,visited);
    if(nodenum == G.vexnum && 2 * (G.vexnum - 1) == edgenum)
        //如果遍历一次之后，涉及到的顶点的个数=图G所有的顶点数
        //并且涉及到的边数 = （顶点数 - 1） * 2  （注：因为是在无向图中，所以所有的的边被遍历的2遍，所以要*2）
        return true;
    else
        return false;
}