列出连通集
给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0 < N ≤ 10)和E,分别是图的顶点数和边数。随后E行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照"{ v1 v2 ... vk }"的格式,每行输出一个连通集。先输出DFS的结果,再输出BFS的结果。
输入样例:
8 6 0 7 0 1 2 0 4 1 2 4 3 5
输出样例:
{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }
解题思路
DFS和BFS模板题,下面代码的存图用的是邻接矩阵。
AC代码:
1 #include <cstdio> 2 #include <iostream> 3 #include <queue> 4 5 const int MAXN = 10; 6 bool vis[MAXN]; 7 8 struct MGraph { 9 int G[MAXN][MAXN]; 10 int verN, edgeN; 11 }; 12 13 MGraph *createMGraph(); 14 void ListComponents(MGraph *graph, void (*graphTraversal)(MGraph*, int)); 15 void DFS(MGraph *graph, int v); 16 void BFS(MGraph *graph, int v); 17 18 int main() { 19 MGraph *graph = createMGraph(); 20 ListComponents(graph, DFS); 21 ListComponents(graph, BFS); 22 23 return 0; 24 } 25 26 MGraph *createMGraph() { 27 int n, m; 28 scanf("%d %d", &n, &m); 29 MGraph *graph = new MGraph; 30 graph->verN = n; 31 graph->edgeN = m; 32 std::fill(*graph->G, *graph->G + MAXN * MAXN, 0); 33 34 for (int i = 0; i < m; i++) { 35 int v, w; 36 scanf("%d %d", &v, &w); 37 graph->G[v][w] = graph->G[w][v] = 1; 38 } 39 40 return graph; 41 } 42 43 void ListComponents(MGraph *graph, void (*graphTraversal)(MGraph*, int)) { 44 std::fill(vis, vis + graph->verN, false); 45 for (int v = 0; v < graph->verN; v++) { 46 if (!vis[v]) { 47 printf("{ "); 48 graphTraversal(graph, v); 49 printf("}\n"); 50 } 51 } 52 } 53 54 void DFS(MGraph *graph, int v) { 55 vis[v] = true; 56 printf("%d ", v); 57 for (int w =0; w < graph->verN; w++) { 58 if (!vis[w] && graph->G[v][w]) DFS(graph, w); 59 } 60 } 61 62 void BFS(MGraph *graph, int v) { 63 std::queue<int> q; 64 q.push(v); 65 vis[v] = true; 66 printf("%d ", v); 67 68 while (!q.empty()) { 69 int v = q.front(); 70 q.pop(); 71 72 for (int w = 0; w < graph->verN; w++) { 73 if (!vis[w] && graph->G[v][w]) { 74 q.push(w); 75 vis[w] = true; 76 printf("%d ", w); 77 } 78 } 79 } 80 }