【数据结构周周练】029 判断无向图是否为一棵树算法原理详解及代码分享

喜欢ヅ旅行 2021-06-11 15:13 685阅读 0赞

## 一、题目 ##

设计一个算法，判断一个图G是否为一棵树，如果是，返回TRUE，否则，返回FALSE。

## 二、美丽的星座 ##

星座真的好美好美。特别是当人类给它们赋予含义的那一刻，更美，仿佛有了灵魂一般。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_32_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFFFFF_t_70 1][]

是不是很美，是不是？你以为我是让你过来看星星的吗？你以为我是希望你以后能够好好学习天文学知识的吗？当然不仅仅是这样啦！细心的你应该知道星星多么像我们学的图啊！！！

## 三、分析 ##

**敲黑板！！！**

看题了嗨，学习完了我们可以一起畅游星空哈，现在回来我们的重心，看下面这两个星座,为了方便观看，研究其特性，我们放小一点，它们不仅仅是一个星座，同样它们也是一个图，同样它们也是一棵树，也就是说这两个图都是一棵树，那它们有什么特点呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_FFFFFF_t_70][] 该无向图是一棵树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFFFFF_t_70 2][]

第一个图有 7颗星星，相当于有三个顶点，星星之间有  6条连线，相当于有  6条边；

第二个图有11颗星星，相当于有11个顶点，星星之间有10条连线，相当于有10条边。

这是树的特性，**有n个顶点，就会有n-1条边，且每个顶点都有边相连**。即一个图是一棵树的条件是：**有n个顶点，就会有n-1条边****，且每个顶点都有边相连**。

所以我们的算法就在于判断当我们遍历完图之后，我们是否访问完所有的结点，并且，访问的结点的条数是结点个数-1。

当然，如果我们采用邻接表存储的图，那每一条边都会访问两次，也就是说，我们访问边的次数是边数的两倍。

**第一步，遍历图之前的操作**

我们遍历图，因为我们要做判断，判断结点是否被访问，被访问说明图中有环，就不是树，所以我们需要定义一个数组来保存结点访问情况，并设置所有值为false，当访问结点后，该结点对应的数组位置的元素改为true。

for (int i = 0; i < G.vexnum; i++) //将所有的访问状态设置为false，即未访问。
    	visited[i] = false;

并且我们要判断访问的边以及结点数量，如果结点访问的数量同图中结点数量一致，并且访问过的边的次数是顶点个数减一的两倍，说明是一棵树，所以我们还需要设置两个变量，用来存储访问结点次数以及访问边的次数。

int VNum = 0;//访问的顶点的数量
    int ENum = 0;//访问的边的数量

**第二步，遍历图**

遍历图我们采用递归算法，为了方便，我们单独写一个遍历算法DFS，即深度优先遍历图（Depth-First-Search）。遍历过程中，每遍历一次，将一个结点的访问改为true，顶点数目+1。

visited[v] = true;//做访问标记
    VNum++; //顶点计数+1

然后获取当前结点，即v结点的第一个邻接点，如果存在，说明有一条边存在，即需要边的数量+1，然后访问v结点的第一个邻接点，如果该邻接点未访问，则继续递归访问，如果访问过了，则访问下一个邻接点。

int w = FirstNeighbor(G, v);
    while (w!=-1)
    {
    	ENum++;
    	if (!visited[w])
    		DFS(G, v, VNum, ENum, visited);
    	w = NextNeighbor(G, v, w);
    }

第三步，做判断

如果满足遍历的定点数与图的顶点数相同并且访问的边数和等于顶点数-1的两倍，则说明是树，否则不是树。

if (VNum == G.vexnum&& ENum == 2 * (G.vexnum - 1))
    		return true;
    	else
    		return false;

## 四、全部代码 ##

刚才上面是分析，为了便于大家理解，我将分析对应的代码也写上去了，为了方便大家整体分析，接下来我将所有的代码分享一下。

bool GraphIsTree(Graph &G) {
    	for (int i = 0; i < G.vexnum; i++)
    	{
    		visited[i] = false;
    	}
    	int VNum = 0;
    	int ENum = 0;
    	
    	if (VNum == G.vexnum&& ENum == 2 * (G.vexnum - 1))
    		return true;
    	else
    		return false;
    }
    
    void DFS(Graph &G, int v, int &VNum, int &ENum, int visited[]) {
    	visited[v] = true;
    	VNum++;
    	int w = FirstNeighbor(G, v);
    	while (w!=-1)
    	{
    		ENum++;
    		if (!visited[w])
    			DFS(G, v, VNum, ENum, visited);
    		w = NextNeighbor(G, v, w);
    	}
    }

大家有什么问题在下面留言哦！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFFFFF_t_70]: /images/20210516/7dc56fb304bc4f4cb8e4d61a96b376fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_32_color_FFFFFF_t_70]: /images/20210516/333274e169a94208accbefce3386fe6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFFFFF_t_70 1]: /images/20210516/975419f49cd644f5b68d5e826cda91c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_36_color_FFFFFF_t_70]: /images/20210516/ef8d305bb3004a78bdf3d206a7c5d680.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_26_color_FFFFFF_t_70 2]: /images/20210516/dfe165a16e5942018d341dc6204d79b6.png