图的表示与基础操作：邻接矩阵与邻接表的C语言实现 |
您所在的位置：网站首页 › 有向图的邻接矩阵表示法 › 图的表示与基础操作：邻接矩阵与邻接表的C语言实现 |
图的表示与基础操作：邻接矩阵与邻接表的C语言实现
|
在计算机科学中，图是一种重要的非线性数据结构，广泛应用于网络、工程、算法等多个领域。本文将探讨如何使用C语言实现图的两种经典存储结构——邻接矩阵和邻接表，并通过实例代码来展示它们的创建等基本操作。 一、引言图由顶点集和边集构成，边可以是有向或无向的，且可带有权重。根据图的特性选择合适的存储结构至关重要，这直接影响到图的各种操作（如遍历、查找最短路径等）的效率。本文只对于代码做简单分享，不对代码的逻辑做深层解释，如果读者想知道代码的实现逻辑，请详细阅读代码中的注释部分。 二、邻接矩阵定义：邻接矩阵是一种使用二维数组来表示图的结构，数组的每个元素表示两个顶点之间是否存在边以及边的权重。对于无向图，矩阵是对称的；对于有向图，则不必如此。 函数 getPos_Matrix：通过顶点名称查找其在顶点数组中的索引。函数 createMatrixGraph：初始化一个图，用户需提供边数和顶点数，然后通过标准输入读取顶点信息和边的信息，构建邻接矩阵。函数 printfMatrix：以易于阅读的格式打印邻接矩阵和顶点信息。 1.结构体以及函数的声明代码： #pragma once #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define MAX_VERTICES 100 //最大顶点数目 #define INFINITY 0 //用0记作无穷 #define VertexLength 10 //节点的内容长度 /*----------------------------------------------------------------------------*/ //邻接矩阵存储图结构 typedef char DataType; typedef struct GraphMatrix { //图中实际存入顶点数和边数 int arcnum; int vexnum; //邻接矩阵 int matrix[MAX_VERTICES][MAX_VERTICES]; //顶点信息(创建一个字符串数组) DataType vertex[VertexLength][MAX_VERTICES]; //带权图 填入权值 }MatrixGraph; //获取矩阵下标 int getPos_Matrix(MatrixGraph* graph, char* v); //创建邻接矩阵 MatrixGraph* createMatrixGraph(int arcnum, int vexnum); //打印邻接矩阵 void printfMatrix(MatrixGraph* graph); 2.函数实现： #include"graph.h" //从节点信息中获取位置 int getPos_Matrix(MatrixGraph*graph, char *v) { for (int i = 0; i < graph->vexnum; i++) { if (!strcmp(graph->vertex[i], v)) { return i; } } return -1; } //创建一个表，给出边数和点数 MatrixGraph* createMatrixGraph(int arcnum, int vexnum) { MatrixGraph* graph = (MatrixGraph*)malloc(sizeof(MatrixGraph)); assert(graph); //数据初始化 graph->arcnum = arcnum; graph->vexnum = vexnum; //将全部都初始化为无穷 for (int i = 0; i < graph->vexnum; i++) { for (int j = 0; j < graph->vexnum; j++) { graph->matrix[i][j] = INFINITY; } } //获取顶点名称 printf("输入顶点信息：\n"); for (int i = 0; i < graph->vexnum; i++) { scanf("%s", graph->vertex[i]); } //获取边的信息 printf("输入边的信息：\n"); for (int k = 0; k < graph->arcnum; k++) { //临时变量接受数据 char v1[VertexLength]; char v2[VertexLength]; int weight; scanf("%s %s %d", v1, v2, &weight); //根据点的信息获得下标信息 int row = getPos_Matrix(graph, v1); int col = getPos_Matrix(graph, v2); //判断是否找到 if (row == -1 | col == -1) { printf("输入错误，请重新输入\n"); k--; } else { //注意这里，此处做的是有向带权图，只需要做一次插入即可 // 如果是无向图，需要将对称的位置也插入相应的权值 //将矩阵中对应位置 置为接受到的权值 graph->matrix[row][col] = weight; } } return graph; } //矩阵打印 void printfMatrix(MatrixGraph* graph) { //打印第一行表头 printf("\t"); for (int i = 0; i < graph->vexnum; i++) { printf("%s\t", graph->vertex[i]); } printf("\n"); //打印矩阵中内容 for (int i = 0; i < graph->vexnum; i++) { printf("%s\t", graph->vertex[i]); for (int j = 0; j < graph->vexnum; j++) { printf("%d\t", graph->matrix[i][j]); } printf("\n"); } } 3.代码测试： int main() { int i, j; printf("请输入边数和点数：\n"); scanf("%d %d", &i, &j); MatrixGraph* graph = createMatrixGraph(i,j); printf("邻接矩阵如下：\n"); printfMatrix(graph); return 0; } /*测试样例： 请输入边数和点数： 4 5 输入顶点信息： A B C D E 输入边的信息： A A 1 A B 2 A C 3 A D 4 */ 4.测试结果：
定义：邻接表利用链表结构来表示图，每个顶点都有一个链表，链表中的每个节点代表与该顶点直接相连的其他顶点及其边的权重。 1.邻接表的结构体声明： //邻接表存储图结构 //arc 弧，创建arcNode（弧结点） typedef struct arcNode { //数组下标 int index; //弧的权重 int weight; //下一个弧结点指针 struct arcNode* next; }arcNode; //头节点 typedef struct vertexHead { //顶点的信息 char vertex[VertexLength]; //下一个节点的信息 arcNode* next; }vertexHead; typedef struct GraphList { //用数组封装顶点信息 vertexHead *arrVertex[MAX_VERTICES]; //图中实际存入顶点数和边数 int arcnum; int vexnum; }GraphList; //创建顶点和弧节点 vertexHead* createHead(char* vertex); arcNode* createNode(int index, int weight); //在顶点后插入关联节点 void createList(vertexHead* head, arcNode* newNode); int getPos_list(GraphList* graph, char* v); //创建图 GraphList* createListGraph(int arcnum, int vexnum); //打印邻接表 void printfListGraph(GraphList* graph); arcNode 结构体这个结构体代表了邻接表中的边节点，用于存储与某个顶点相连的所有边的信息。 index: 表示该边所指向的目标顶点在顶点数组中的索引位置。这是为了快速定位边的终点。weight: 存储边的权重，对于无权图，此字段可能不需要。next: 指针类型，指向链表中的下一个arcNode，形成了以顶点为中心的边的链式结构。如果这是链表中的最后一个节点，next应为NULL。 vertexHead 结构体这个结构体作为顶点的头部节点，每个顶点在邻接表中都有这样一个头节点。 vertex[VertexLength]: 用来存储顶点的标识符或信息，比如顶点的名字。next: 指向与该顶点相邻的第一个边节点的指针。如果该顶点没有出边，那么next也是NULL。 GraphList 结构体这是整个邻接表的封装，包含了图的基本信息和所有顶点的头节点。 arrVertex[MAX_VERTICES]: 是一个顶点头节点的数组，数组的索引对应顶点的编号，方便快速访问每一个顶点的邻接链表。arcnum: 记录图中边的数量。vexnum: 记录图中顶点的数量。从图上理解
注意，这里打印的括号中的是从顶点到该点的权重，比如V0->V4(6)表示有一条从V0->V4的边，该边的权重为6。 四、总结邻接矩阵适合稠密图（边的数量接近于顶点数量的平方），因为可以快速判断两点间是否存在边，但空间开销较大。而邻接表则更适合稀疏图，它能有效节省空间，但在查询两点间是否存在边时效率较低。 本篇文章通过C语言实现了图的这两种存储方式，并提供了基础的操作函数，为后续进行更复杂图算法的实现奠定了基础。理解这些基础结构和操作，是深入学习图论算法的关键一步。 |
【本文地址】
今日新闻 |
推荐新闻 |