无向图的遍历c++
时间: 2023-11-30 08:42:13 浏览: 59
无向图的遍历有两种方法:深度优先搜索(DFS)和广度优先搜索(BFS)。下面是两种方法的C++代码实现:
1.深度优先搜索(DFS)
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N], e[N], ne[N], idx;
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
int main()
{
memset(h, -1, sizeof h); int n, m;
cin >> n >> m;
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
int cnt = 0;
for (int i = 1; i <= n; i ++ )
if (!st[i])
{
cnt ++ ;
dfs(i);
}
cout << cnt << endl;
return 0;
}
```
2.广度优先搜索(BFS)
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N], e[N], ne[N], idx;
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs(int u)
{
queue<int> q;
q.push(u);
st[u] = true;
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
int n, m;
cin >> n >> m;
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
int cnt = 0;
for (int i = 1; i <= n; i ++ )
if (!st[i])
{
cnt ++ ;
bfs(i);
}
cout << cnt << endl;
return 0;
}
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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_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)