用c语言由邻接矩阵输出任意两个节点长度小于等于n的路径的数目
时间: 2024-02-22 22:55:04 浏览: 24
下面是用C语言实现的邻接矩阵输出任意两个节点长度小于等于n的路径的数目的代码:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100
int graph[MAXN][MAXN]; // 邻接矩阵
int n; // 节点数
int count_paths(int u, int v, int len) {
// 定义评估函数为0的路径数为1
if (len == 0) {
if (u == v) {
return 1;
} else {
return 0;
}
} else {
int count = 0;
for (int i = 0; i < n; i++) {
if (graph[u][i]) {
count += count_paths(i, v, len - 1); // 递归计算长度为len-1的路径数
}
}
return count;
}
}
int main() {
// 读入邻接矩阵
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
// 输出任意两个节点长度小于等于n的路径的数目
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int len = 1; len <= n; len++) {
ans += count_paths(i, j, len);
}
}
}
printf("%d\n", ans);
return 0;
}
```
这个算法的时间复杂度为$O(n^3)$,可以处理节点数比较小的图。如果节点数比较大,可以考虑使用其他更高效的算法,如Floyd算法或Dijkstra算法。
相关推荐
![](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)