C++实现有向无权图最长路径
时间: 2023-10-20 10:13:56 浏览: 46
有向无权图最长路径问题可以使用BFS算法来解决,以下是C++实现的示例代码,假设有n个结点和m条有向边:
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs(int start) {
memset(dist, -1, sizeof dist);
dist[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] == -1) {
dist[j] = dist[t] + 1;
q.push(j);
}
}
}
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, dist[i]);
return res;
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
int res = bfs(1);
printf("%d\n", res);
return 0;
}
```
其中,add函数用于添加一条有向边,bfs函数用于求解最长路径,即使用BFS算法计算从起点开始到每个结点的最短路径,然后返回其中的最大值。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![](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)