从键盘输入图的邻接矩阵和一正整数m,计算结点两两之间长度为m的路的条数。C语言
时间: 2024-03-26 08:40:30 浏览: 110
计算图中两两结点路数为m的邻接矩阵
5星 · 资源好评率100%
好的,我知道了。以下是计算结点两两之间长度为m的路的条数的C语言代码,可以参考一下:
```c
#include <stdio.h>
#define MAXN 1000
int G[MAXN][MAXN]; // 图的邻接矩阵
int n; // 结点数
int dfs(int u, int m, int len, int *vis) {
if (len == m) return 1;
int cnt = 0;
for (int v = 0; v < n; ++v) {
if (G[u][v] && !vis[v]) {
vis[v] = 1;
cnt += dfs(v, m, len + 1, vis);
vis[v] = 0;
}
}
return cnt;
}
int main() {
int m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &G[i][j]);
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int vis[MAXN] = {0};
vis[i] = 1;
ans += dfs(i, m, 0, vis);
}
printf("%d\n", ans / 2); // 由于计算双向边,所以最后要除以2
return 0;
}
```
这个代码的思路是,对于每个结点i,从它开始做深度优先搜索,找到长度为m的路径的数量。最后将所有结点的数量相加即可。
需要注意的一点是,由于是无向图,所以计算出来的数量会有重复的情况,因此最后要除以2。
阅读全文