以邻接矩阵或邻接表定义无向图,其中每个元素的数据类型为int。实现图的深度优先或者广度优先遍历,打印所有的节点。
时间: 2024-05-14 14:20:00 浏览: 100
以下是邻接表实现的深度优先遍历代码:
```c++
#include<iostream>
#include<list>
#include<vector>
#include<stack>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void addEdge(int v, int w) {
adj[v].push_back(w);
}
void DFS(int s) {
vector<bool> visited(V, false);
stack<int> stack;
stack.push(s);
while (!stack.empty()) {
s = stack.top();
stack.pop();
if (!visited[s]) {
cout << s << " ";
visited[s] = true;
}
for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
if (!visited[*i])
stack.push(*i);
}
}
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal (starting from vertex 2) \n";
g.DFS(2);
return 0;
}
```
输出结果为:
```
Following is Depth First Traversal (starting from vertex 2)
2 3 0 1
```
以上代码实现了邻接表的深度优先遍历。如果要实现邻接矩阵的深度优先遍历,只需将代码中的 `list<int>` 改为 `int**`,并相应修改代码即可。广度优先遍历也类似,只需将代码中的 `stack<int>` 改为 `queue<int>`,并相应修改代码即可。
阅读全文