c语言邻接矩阵表示带权无向图
时间: 2023-08-31 22:09:07 浏览: 97
邻接矩阵是一种常见的表示图的方法,对于带权无向图,我们可以使用一个二维数组来表示邻接矩阵。具体来说,设图G的顶点数为n,邻接矩阵为matrix,则matrix[i][j]表示顶点i和顶点j之间的边的权值,如果i和j之间没有边,则matrix[i][j]的值为0。由于是带权图,所以matrix[i][j]的值可能为任意非负数,当然也可能为负数。如果图是有向图,则邻接矩阵不一定是对称的。在使用邻接矩阵表示图时,需要注意空间复杂度,如果图的顶点数很多,邻接矩阵可能会非常大,甚至超出计算机的内存限制。
相关问题
如何用c语言邻接矩阵表示法建立无向图
邻接矩阵是一种用于表示图的数据结构,其中矩阵中的每个元素表示两个顶点之间是否存在边。对于无向图而言,矩阵是对称的。
以下是使用C语言邻接矩阵表示法建立无向图的示例代码:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 20
// 邻接矩阵无向图结构体
typedef struct {
char vertices[MAX_VERTEX_NUM]; // 顶点表
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int edge_num; // 边数
} MGraph;
// 初始化无向图
void InitMGraph(MGraph *G) {
int i, j;
printf("请输入顶点数和边数:\n");
scanf("%d %d", &G->vertex_num, &G->edge_num);
fflush(stdin);
printf("请输入顶点信息:\n");
for (i = 0; i < G->vertex_num; i++) {
scanf("%c", &G->vertices[i]);
fflush(stdin);
}
// 初始化邻接矩阵
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
G->arcs[i][j] = 0;
}
}
// 构建邻接矩阵
printf("请输入每条边的起点和终点:\n");
for (i = 0; i < G->edge_num; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
G->arcs[v1][v2] = 1;
G->arcs[v2][v1] = 1;
}
}
// 打印无向图
void PrintMGraph(MGraph G) {
int i, j;
printf("邻接矩阵:\n");
for (i = 0; i < G.vertex_num; i++) {
for (j = 0; j < G.vertex_num; j++) {
printf("%d ", G.arcs[i][j]);
}
printf("\n");
}
}
int main() {
MGraph G;
InitMGraph(&G);
PrintMGraph(G);
return 0;
}
```
在上面的代码中,我们定义了一个 `MGraph` 结构体来表示邻接矩阵无向图。`InitMGraph` 函数用于初始化图,包括输入顶点数、边数、顶点信息以及每条边的起点和终点,并构建邻接矩阵。`PrintMGraph` 函数用于打印邻接矩阵。在 `main` 函数中,我们调用 `InitMGraph` 和 `PrintMGraph` 函数来构建并打印无向图。
注意,上面的代码中,我们假设顶点使用字符表示,因此在输入顶点信息时使用了 `%c` 格式化符号。如果顶点使用其他类型表示,需要相应更改输入和打印的代码。
创建带权无向图的邻接矩阵c语言
下面是一个简单的C语言代码示例,用于创建带权无向图的邻接矩阵:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int n; // 顶点数
void createGraph() {
int i, j, weight;
printf("请输入顶点数:");
scanf("%d", &n);
printf("请输入边的权值,如果两个顶点之间没有边,则输入0。\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("请输入顶点%d和顶点%d之间的权值:", i+1, j+1);
scanf("%d", &weight);
matrix[i][j] = weight;
}
}
}
void printGraph() {
int i, j;
printf("邻接矩阵为:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
createGraph();
printGraph();
return 0;
}
```
这个程序首先会要求用户输入顶点数,然后让用户逐个输入每条边的权值,最后输出邻接矩阵。注意,上面的代码没有对输入的数据进行任何错误检查,为了保证程序的健壮性,应该对输入进行适当的验证和异常处理。