PAT : 数据结构与算法题目集(中文)7-6 列出连通集
C++11:
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
class graph
{
private:
int N, E;
bool mat[10][10]{false};
bool book[10]{false};
vector<int> FSvec;
void mDFS(int);
void mBFS(int);
void print(void);
public:
graph(void)
{
cin >> N >> E;
while (E--)
{
int a, b;
cin >> a >> b;
mat[a][b] = mat[b][a] = true;
}
for (int i = 0; i < N; ++i)
mat[i][i] = true;
}
void DFS(void);
void BFS(void);
};
void graph::print(void)
{
cout << "{ ";
for (const auto &i : FSvec)
cout << i << " ";
cout << "}" << endl;
}
void graph::DFS(void)
{
memset(book, false, sizeof(book));
for (int i = 0; i < N; ++i)
{
if (book[i])
continue;
for (int j = 0; j < N; ++j)
{
if (mat[i][j])
{
FSvec.clear();
mDFS(i);
print();
break;
}
}
}
}
void graph::mDFS(int P)
{
FSvec.push_back(P);
book[P] = true;
for (int k = 0; k < N; ++k)
if (mat[P][k] && !book[k])
mDFS(k);
}
void graph::BFS(void)
{
memset(book, false, sizeof(book));
for (int i = 0; i < N; ++i)
{
if (book[i])
continue;
for (int j = 0; j < N; ++j)
{
if (mat[i][j])
{
FSvec.clear();
mBFS(i);
print();
break;
}
}
}
}
void graph::mBFS(int P)
{
book[P] = true;
queue<int> Q;
Q.push(P);
FSvec.push_back(P);
while (Q.empty() == false)
{
int top = Q.front();
for (int i = 0; i < N; ++i)
{
if(mat[top][i]&&book[i]==false)
{
book[i] = true;
FSvec.push_back(i);
Q.push(i);
}
}
Q.pop();
}
}
int main(int argc, char *argv[])
{
cin.sync_with_stdio(false);
graph A;
A.DFS();
A.BFS();
return EXIT_SUCCESS;
}
DFS/BFS遍历图需熟练~