无向图的搜索树和森林

缘起

在【1】中，我们论述了图的连通性以及连通分支的概念. 而这里将给出生成树的概念. 无向图的连通分支的生成树是一个极小连通子图. 它包含连通分支所有的顶点，但是只有连通分支顶点个数-1条边. 对于无向图是可以很方便的使用遍历得到其连通分支的生成树的. 因为沿着无向图进行dfs或bfs的话, 得到的就是相应连通分支的生成树。 因为无向图未必连通, 所以我们会得到搜索树构成的森林. 我们可以使用【2】给出的方法将森林转换为树.

所以本文的程序是为了给出图的dfs搜索森林和bfs搜索森林的算法. 注意, 讨论无向图的dfs给出搜索树的目的是为了得到其连通分量（或者叫分支）的生成树. 所以站在生成树的角度讨论有向图的搜索树是无意义的.

分析

通过dfs得到深度优先生成森林

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错
#include <vector>

#define LOCAL
using namespace std;
const int MAX_VERTEX_NUM = 20;
typedef vector<int>::iterator it;


typedef struct BTreeNode  // 二叉树节点
{
	int data;
	BTreeNode *firstchild, *sibling;
	BTreeNode(int data):data(data),firstchild(NULL),sibling(NULL){}
}*BTree;

struct Graph
{
	vector<int> vertex[MAX_VERTEX_NUM];
	int n; // 无向图的顶点的个数

	Graph()
	{
		puts("输入顶点的个数");
		scanf("%d", &n);
		int start, end;
		puts("输入边,不同边换行");
		while(~scanf("%d%d",&start,&end))
		{
			vertex[start].push_back(end);
			vertex[end].push_back(start);
		}
	}

	int cnt; // 连通分量的个数(亦即生成树的棵数)
	bool isvisited[MAX_VERTEX_NUM];

	BTree *buildForest() // 构造森林
	{
		memset(isvisited, 0, sizeof(isvisited));
		cnt = 0;
		BTree *forest = new BTree[MAX_VERTEX_NUM];
		for (int i = 0; i<n;i++)
		{
			if (!isvisited[i])
			{
				isvisited[i] = true;
				BTree root = new BTreeNode(i);
				forest[cnt++] = root;
				dfs(root);
			}
		}
		return forest;
	}

private:
	void dfs(BTree cur) // 深搜， cur是当前根节点
	{
		for (it x = vertex[cur->data].begin(); x!=vertex[cur->data].end(); x++)
		{
			if (!isvisited[*x])
			{
				isvisited[*x] = true;
				BTree child = new BTreeNode(*x);
				if (!cur->firstchild) // 如果是长子
				{
					cur->firstchild = child;
				}
				else // 兄弟， 头插法
				{
					child->sibling = cur->firstchild->sibling;
					cur->firstchild->sibling = child;
				}
				dfs(child);
			}
		}
	}

};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Graph g;
	BTree *forest =  g.buildForest();
	printf("一共%d个连通分支\n", g.cnt);
	return 0;
}
/*
测试数据
13
0 1
0 2
0 5
1 12
11 12
11 9
9 12
0 11
3 4
8 6
10 6
6 7
7 10
*/

通过 bfs 得到广度优先生成森林

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错
#include <vector>
#include <queue>

#define LOCAL
using namespace std;
const int MAX_VERTEX_NUM = 20;
typedef vector<int>::iterator it;


typedef struct BTreeNode  // 二叉树节点
{
	int data;
	BTreeNode *firstchild, *sibling;
	BTreeNode(int data):data(data),firstchild(NULL),sibling(NULL){}
}*BTree;

struct Graph
{
	vector<int> vertex[MAX_VERTEX_NUM];
	int n; // 无向图的顶点的个数

	Graph()
	{
		puts("输入顶点的个数");
		scanf("%d", &n);
		int start, end;
		puts("输入边,不同边换行");
		while(~scanf("%d%d",&start,&end))
		{
			vertex[start].push_back(end);
			vertex[end].push_back(start);
		}
	}

	int cnt; // 连通分量的个数(亦即生成树的棵数)
	bool isvisited[MAX_VERTEX_NUM];

	BTree *buildForest() // 构造森林
	{
		memset(isvisited, 0, sizeof(isvisited));
		cnt = 0;
		BTree *forest = new BTree[MAX_VERTEX_NUM];
		for (int i = 0; i<n;i++)
		{
			if (!isvisited[i])
			{
				isvisited[i] = true;
				BTree root = new BTreeNode(i);
				forest[cnt++] = root;
				bfs(root); // dfs和bfs唯一不同的地方
			}
		}
		return forest;
	}

private:
	void bfs(BTree root)
	{
		queue<BTree> q;
		q.push(root);
		isvisited[root->data] = true;
		while(!q.empty())
		{
			BTree front = q.front();
			q.pop();
			for (it x = vertex[front->data].begin(); x!=vertex[front->data].end(); x++)
			{
				if (!isvisited[*x])
				{
					isvisited[*x] = true;
					BTree child = new BTreeNode(*x);
					q.push(child);
					if (!front->firstchild) // 长子
					{
						front->firstchild = child;
					}
					else // 兄弟
					{
						child->sibling = front->firstchild->sibling; // 头插法
						front->firstchild->sibling = child;
					}
				}
			}
		}
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Graph g;
	BTree *forest =  g.buildForest();
	printf("一共%d个连通分支\n", g.cnt);
	return 0;
}

参考

【1】https://yfsyfs.github.io/2019/05/22/%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E6%94%AF/

【2】https://yfsyfs.github.io/2019/05/23/%E6%A0%91%E5%92%8C%E6%A3%AE%E6%9E%97%E4%B9%8B%E9%97%B4%E7%9A%84%E8%BD%AC%E6%8D%A2/