数据结构:图的创建(通俗易懂版)
图中的信息:
- 顶点:A, B, C, D
- 边及权重:
- A - B: 权重为 1
- A - C: 权重为 2
- B - C: 权重为 3
- C - D: 权重为 4
- B - D: 权重为 5
邻接矩阵:
邻接矩阵是一个 4×44 \times 44×4 的矩阵,每个位置 [i][j][i][j][i][j] 存储的是从顶点 i 到顶点 j 的边的权重(如果没有边,则填 0 或无穷大)。根据你的图,邻接矩阵如下:
A B C D
A 0 1 2 0
B 1 0 3 5
C 2 3 0 4
D 0 5 4 0
c代码实现:
#include <stdio.h>
#define MAXV 100 // 最大顶点数
#define INF 0 // 用 0 表示没有连接的边
typedef struct {
int numVertices, numEdges; // 图的顶点数和边数
char VerticesList[MAXV]; // 顶点表
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
// 初始化图
void InitGraph(MGraph *G) {
G->numVertices = 4; // 顶点数
G->numEdges = 5; // 边数
// 顶点名称
G->VerticesList[0] = 'A';
G->VerticesList[1] = 'B';
G->VerticesList[2] = 'C';
G->VerticesList[3] = 'D';
// 初始化邻接矩阵,全部设置为0(无边)
for (int i = 0; i < G->numVertices; i++) {
for (int j = 0; j < G->numVertices; j++) {
G->Edge[i][j] = INF; // 无边
}
}
// 手动插入边及其权重
G->Edge[0][1] = 1; // A-B
G->Edge[1][0] = 1; // B-A(无向图)
G->Edge[0][2] = 2; // A-C
G->Edge[2][0] = 2; // C-A
G->Edge[1][2] = 3; // B-C
G->Edge[2][1] = 3; // C-B
G->Edge[2][3] = 4; // C-D
G->Edge[3][2] = 4; // D-C
G->Edge[1][3] = 5; // B-D
G->Edge[3][1] = 5; // D-B
}
// 打印邻接矩阵
void PrintGraph(MGraph G) {
printf("邻接矩阵:\n");
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
printf("%d ", G.Edge[i][j]);
}
printf("\n");
}
}
int main() {
MGraph G;
InitGraph(&G); // 初始化图
PrintGraph(G); // 打印邻接矩阵
return 0;
}