#include <iostream> #include <queue> using namespace std; const int MAXN = 1000; struct Edge { int to, next; } edges[MAXN]; int head[MAXN], tot; bool vis[MAXN]; void addEdge(int u, int v) { edges[++tot].to = v; edges[tot].next = head[u]; head[u] = tot;}void dfs(int u) { vis[u] = true; cout << char(u + 'A') << " "; for (int i = head[u]; i != 0; i = edges[i].next) { int v = edges[i].to; if (!vis[v]) { dfs(v); } } } void bfs(int u) { queue<int> q; q.push(u); vis[u] = true; while (!q.empty()) { int x = q.front(); q.pop(); cout << char(x + 'A') << " "; for (int i = head[x]; i != 0; i = edges[i].next) { int v = edges[i].to; if (!vis[v]) { q.push(v); vis[v] = true; } } } } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { char u, v; cin >> u >> v; addEdge(u - 'A', v - 'A'); addEdge(v - 'A', u - 'A'); } dfs(0); cout << endl; for (int i = 0; i < n; i++) { vis[i] = false; } bfs(0); cout << endl; return 0; }运行之后输出结果实例

假设输入的是如下图所示的无向图：

    A -- B
   / \    |
  /   \   |
 C     D  E

则程序的运行结果为：

DFS遍历结果：A C D B E 
BFS遍历结果：A B C D E 

其中DFS遍历的路径为A-C-D-B-E，BFS遍历的路径为A-B-C-D-E。注意，由于输入的是无向图，因此在建立邻接表时需要同时添加两条边，即addEdge(u - 'A', v - 'A')和addEdge(v - 'A', u - 'A')。