*) 计算两点之间长度为m的路的条数 (1)熟悉邻接矩阵和两点之间长度为m的通路或回路的条数的关系 (2)从键盘输入图的邻接矩阵和一正整数m,计算结点两两之间长度为m的路的条数。
时间: 2024-04-04 22:34:27 浏览: 91
求两个点之间最短路径C++源码.zip
5星 · 资源好评率100%
计算两点之间长度为m的路的条数的C语言代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INF 999999 // 无穷大
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存储顶点信息
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值,若为0则表示无边相连
int vertex_num, edge_num; // 顶点数和边数
} Graph;
// 初始化图
void init_graph(Graph *G) {
int i, j;
G->vertex_num = G->edge_num = 0;
for (i = 0; i < MAX_VERTEX_NUM; ++i) {
G->vertex[i] = 0;
for (j = 0; j < MAX_VERTEX_NUM; ++j) {
G->edge[i][j] = INF;
}
}
}
// 添加顶点
void add_vertex(Graph *G, int v) {
if (G->vertex_num >= MAX_VERTEX_NUM) {
printf("超过最大顶点数限制!\n");
return;
}
G->vertex[G->vertex_num++] = v;
}
// 添加边
void add_edge(Graph *G, int v1, int v2, int weight) {
if (v1 >= G->vertex_num || v2 >= G->vertex_num) {
printf("顶点编号超出范围!\n");
return;
}
G->edge[v1][v2] = weight;
G->edge_num++;
}
// 计算邻接矩阵G的m次方
void matrix_power(Graph *G, int m, int result[][MAX_VERTEX_NUM]) {
int i, j, k;
int temp[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
for (i = 0; i < G->vertex_num; ++i) {
for (j = 0; j < G->vertex_num; ++j) {
result[i][j] = G->edge[i][j];
}
}
for (k = 2; k <= m; ++k) {
for (i = 0; i < G->vertex_num; ++i) {
for (j = 0; j < G->vertex_num; ++j) {
temp[i][j] = 0;
for (int l = 0; l < G->vertex_num; ++l) {
temp[i][j] += result[i][l] * G->edge[l][j];
}
}
}
for (i = 0; i < G->vertex_num; ++i) {
for (j = 0; j < G->vertex_num; ++j) {
result[i][j] = temp[i][j];
}
}
}
}
int main() {
Graph G;
int result[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int m, i, j, k, count;
init_graph(&G);
// 从键盘输入邻接矩阵
printf("请输入邻接矩阵:\n");
for (i = 0; i < 5; ++i) {
add_vertex(&G, i);
for (j = 0; j < 5; ++j) {
scanf("%d", &k);
add_edge(&G, i, j, k);
}
}
// 从键盘输入m
printf("请输入m的值:\n");
scanf("%d", &m);
// 计算邻接矩阵的m次方
matrix_power(&G, m, result);
// 计算长度为m的路的条数
count = 0;
for (i = 0; i < G.vertex_num; ++i) {
for (j = 0; j < G.vertex_num; ++j) {
if (result[i][j] != 0 && result[i][j] != INF) {
count += result[i][j];
}
}
}
count /= 2;
// 输出结果
printf("长度为%d的路的条数为:%d\n", m, count);
return 0;
}
```
这段代码首先从键盘输入图的邻接矩阵和正整数m,然后使用`matrix_power()`函数计算邻接矩阵的m次方,存储在`result`数组中。最后,我们遍历`result`数组,计算长度为m的路的条数。注意,由于是无向图,我们需要将结果除以2。
阅读全文