《数据结构课程设计》图结构练习：List Component

7-1 List Components (30 分)

For a given undirected graph with N vertices and E edges, please list all the connected components by both DFS (Depth First Search) and BFS (Breadth First Search). Assume that all the vertices are numbered from 0 to N-1. While searching, assume that we always start from the vertex with the smallest index, and visit its adjacent vertices in ascending order of their indices.

Input Specification:

Each input file contains one test case. For each case, the first line gives two integers N (0 $<N \leq10) and E, which are the number of vertices and the number of edges, respectively. Then E lines follow, each described an edge by giving the two ends. All the numbers in a line are separated by a space.$

Output Specification:

For each test case, print in each line a connected component in the format {

Sample Input:

Sample Output:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

题目分析：考察图的深度优先遍历、广度优先遍历。由于题中给出了结点数N是小于等于10的，所以采用领接矩阵的方法来做。下面对输入输出样例做简要解释：

输入：结点数（N=8），边数（E=6）。接下来6行分别显示每条边的信息，即两个端点上的数字。注意这里是无向图。
    
输出：首先显示深度优先遍历的结果（DFS），然后显示广度优先遍历的结果（BFS）。注意，此处深度和广度优先遍历都出现了多行的情况。主要是因为图中不止一个连通分量。
    此外，一个结点同时连多个结点，按照结点data的大小升序输出。

代码如下：

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 
 5 #define MAXSIZE 10
 6 using namespace std;
 7 
 8 //深度优先遍历
 9 void DFS(int (*data)[MAXSIZE], int i, bool *visited)  
10 {
11     if (visited[i] == true)
12     {
13         return;
14     }
15     cout << i << " ";
16     visited[i] = true;
17 
18     for (int j = 0; j < MAXSIZE; j++)
19     {
20         if (data[i][j] == 1 && visited[j] == false)
21         {
22             DFS(data, j, visited);
23         }
24     }
25 }
26 
27 //广度优先遍历
28 void BFS(int (*data)[MAXSIZE], int i, bool *visited) 
29 {
30     if (visited[i] == true)
31     {
32         return;
33     }
34 
35     queue<int> myQueue;
36     myQueue.push(i);
37     visited[i] = true;
38 
39     while (myQueue.size() != 0)
40     {
41         int x = myQueue.front();
42         cout << x << " ";
43         myQueue.pop();
44         for (int i = 0; i < MAXSIZE; i++)
45         {
46             if (data[x][i] == 1 && visited[i] == false)
47             {
48                 visited[i] = true;
49                 myQueue.push(i);
50             }
51         }
52     }
53 }
54 
55 int main()
56 {
57     int data[MAXSIZE][MAXSIZE] = { 0 };
58     bool visitedDFS[MAXSIZE] = { false };
59     bool visitedBFS[MAXSIZE] = { false };
60 
61     int N, E;
62     cin >> N >> E;
63 
64     //用领接矩阵存储图
65     for (int i = 0; i < E; i++)
66     {
67         int a, b;
68         cin >> a >> b;
69         data[a][b] = 1;
70         data[b][a] = 1;
71     }
72 
73     //深度优先遍历，从数字最小的结点开始遍历
74     for (int i = 0; i < N; i++)
75     {
76         if (!visitedDFS[i])
77         {
78             cout << "{"<<" ";
79             DFS(data, i, visitedDFS);  //DFS定义中(*data),否则data处标记错误
80             cout << "}" << endl;
81         }
82     }
83 
84     //广度优先遍历，从数字最小的结点开始遍历
85     for (int i = 0; i < N; i++)
86     {
87         if (!visitedBFS[i])
88         {
89             cout << "{"<<" ";
90             BFS(data, i, visitedBFS);  //BFS定义中(*data),否则data处标记错误
91             cout << "}" << endl;
92         }
93     }
94 
95     return 0;
96 }

声明：仅作为个人学习记录，对其他代码有所参考，不作其他用途。