11.
24 20:30
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// 图的邻接表表示
vector<vector<int>> graph = {
{1, 2, 3}, // A
{0}, // B
{0, 4}, // C
{0, 4, 5}, // D
{1, 5}, // E
{2, 5}, // F
{3, 5}, // G
{4}, // H
{6}, // I
{7}, {8}, // J
{9, 10}, // K
{9}, {10}, // L
{11}, {11} // M, N, O 只有一个节点，所以可以合并为一个
};
// 深度优先搜索
void DFS(int node, unordered_set<int>& visited) {
visited.insert(node);
cout << "Visited: " << node << endl;
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
DFS(neighbor, visited);
}
}
}
// 广度优先搜索
void BFS(int start) {
unordered_set<int> visited;
queue<int> q;
visited.insert(start);
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << "Visited: " << node << endl;
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
}
int main() {
unordered_set<int> visitedDFS;
unordered_set<int> visitedBFS;
// 深度优先搜索
cout << "DFS:" << endl;
for (int i = 0; i < graph.size(); ++i) {
if (visitedDFS.find(i) == visitedDFS.end()) {
DFS(i, visitedDFS);
}
}
// 广度优先搜索
cout << "\nBFS:" << endl;
for (int i = 0; i < graph.size(); ++i) {
if (visitedBFS.find(i) == visitedBFS.end()) {
BFS(i);
}
}
return 0;
}
