c++图的遍历深度和广度
时间: 2023-12-11 07:21:55 浏览: 41
C++中实现图的遍历可以使用深度优先搜索(DFS)和广度优先搜索(BFS)两种算法。
深度优先搜索(DFS):
```
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void DFS(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
stack<int> s;
s.push(start);
while (!s.empty()) {
int node = s.top();
s.pop();
if (!visited[node]) {
visited[node] = true;
cout << node << " ";
for (int i = graph[node].size() - 1; i >= 0; i--) {
int neighbor = graph[node][i];
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>());
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
DFS(graph, 0);
return 0;
}
```
广度优先搜索(BFS):
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void BFS(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
queue<int> q;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
if (!visited[node]) {
visited[node] = true;
cout << node << " ";
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i];
if (!visited[neighbor]) {
q.push(neighbor);
}
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>());
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
BFS(graph, 0);
return 0;
}
```
其中,graph是一个邻接表表示的无向图,n表示节点数,m表示边数,start表示遍历的起点。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)