无向图的连通分支之搜索解法

缘起

无向图的连通分支定义在【1】中给出. 本文将基于搜索方法得到无向图的连通分支. 使用的搜索方法是深搜. 宽搜是一样的.

分析

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
#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;

struct Graph
{
	vector<int> vertex[MAX_VERTEX_NUM]; // 邻接链表
	vector<int> cc[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];

	void dfs()
	{
		memset(isvisited, 0, sizeof(isvisited));
		cnt = 0;
		for (int i = 0; i<n; i++)
		{
			if (!isvisited[i])
			{
				isvisited[i] = true;
				subdfs(i);
				cnt++;
			}
		}

	}

private:
	void subdfs(int cur)
	{
		cc[cnt].push_back(cur);
		for (it x = vertex[cur].begin(); x!=vertex[cur].end(); x++)
		{
			if (!isvisited[*x])
			{
				isvisited[*x] = true;
				subdfs(*x);
			}
		}
	}

};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Graph g;
	g.dfs();
	printf("一共%d个连通分支\n", g.cnt);
	for (int i = 0; i<g.cnt; i++) for (it x = g.cc[i].begin(); x!=g.cc[i].end(); x++) cout << *x; // 打印所有无向图的连通分支
	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
*/

参考

【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/