那怎么通过上面输入的邻接矩阵建立无向图呢?使用邻接矩阵表示法
时间: 2024-11-18 12:14:59 浏览: 26
使用邻接矩阵来构建无向图,主要是基于给定的二维数组(邻接矩阵)。对于每个顶点对 `(u, v)`,如果矩阵 `matrix[u][v]` 或者 `matrix[v][u]` 中有一个元素为非零(通常假设为1或true,表示存在边),那么就可以认为这两个顶点是相连的。下面是一种直观的方法:
1. 初始化顶点集合:先创建一个包含所有顶点的集合(例如,如果你的顶点编号范围是0到n-1,那么集合可以是整型数组或结构体数组`vertices`)。
2. 填充矩阵:遍历邻接矩阵,对于每个非零元素 `(i, j)`,添加一条边连接顶点 `i` 到 `j`。由于这是无向图,还需要添加另一条边连接 `j` 到 `i`,即添加 `vertices[j]` 到 `vertices[i]` 的连接。
```c
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j]) {
vertices[i].adjacent_vertices.push_back(j); // 添加j到i的边
vertices[j].adjacent_vertices.push_back(i); // 添加i到j的边
}
}
}
```
这里的`adjacent_vertices`是顶点对象的一个成员,用于存储该顶点相邻的所有顶点。
相关问题
如何用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` 格式化符号。如果顶点使用其他类型表示,需要相应更改输入和打印的代码。
邻接矩阵表示法创建无向图
邻接矩阵是一种表示图的方式,适用于有限的、大小固定的图。创建无向图的邻接矩阵表示法可以按照以下步骤进行:
1. 确定图的规模,即节点的个数。
2. 创建一个规模为n * n的矩阵A,其中n为节点个数。
3. 对于每个节点i,将矩阵A的第i行和第i列置为0。
4. 对于每条边(i, j),将矩阵A的第i行第j列和第j行第i列标记为1,表示i和j之间有一条边。
5. 如果希望对图进行权重的计算,可以将矩阵A的对应位置改为边的权重。
创建完邻接矩阵后,就可以方便地进行图的遍历、查找、修改等操作。同时,邻接矩阵也适用于稠密图,但对于稀疏图会浪费空间。
阅读全文