本文写于 2020 年 4 月 1 日,2022 年 3 月 20 日重新整理
图是一种表示多对多关系的数据结构,它包含一组顶点 (Vertex)
和顶点之间的连接关系(称为边 (Edge)
)。
对于节点 vi 和 vj ,一般用 <vi,vj> 表示由 vi 指向 vj 的边。图中的相同节点对一般只考虑一条边,不考虑重复的边和指向自己的边,根据边的单向双向,带权不带权,图可以分为 无向无权图,无向带权图,有向无权图,有向带权图
图的操作集
1 2 3 4 5 6 7
| Graph *create(int vertexCnt); void insertVertex(Graph *graph, Vertex *vertex); void insertEdge(Graph *graph, Edge *edge); void depthFirstSearch(Graph *graph, Vertex *vertex); void breadthFirstSearch(Graph *graph, Vertex *vertex); void shortestPath(Graph *graph, Vertex *vertex, int dist[]); void minSpanningTree(Graph *graph);
|
图的建立实现在后文给出
如何表示一个图
邻接矩阵
使用一个二维矩阵可以描述一个图。对于有 n
个顶点的图,可以用一个 n*n
大小的矩阵 G[n][n]
来表示。
首先给顶点编号 0 - n-1
,矩阵的值 G[i][j]=1 (若 <vi,vj> 存在) ,G[i][j]=0 若 <vi,vj> 不存在 。对于带权图,矩阵的值一般是边的权重。
如下面的有向带权图:
其邻接矩阵为:
|
v0 |
v1 |
v2 |
v3 |
v4 |
v0 |
0 |
2 |
0 |
0 |
0 |
v1 |
0 |
0 |
2 |
2 |
3 |
v2 |
0 |
0 |
0 |
0 |
0 |
v3 |
0 |
0 |
0 |
0 |
0 |
v4 |
0 |
0 |
0 |
0 |
0 |
对于无向图,他们的邻接矩阵一般是对称的:
邻接矩阵为:
|
v0 |
v1 |
v2 |
v3 |
v4 |
v0 |
0 |
1 |
0 |
1 |
0 |
v1 |
1 |
0 |
1 |
1 |
0 |
v2 |
0 |
1 |
0 |
0 |
1 |
v3 |
1 |
1 |
0 |
0 |
0 |
v4 |
0 |
0 |
1 |
0 |
0 |
因此,对于无向图,可以使用一个长度为 N(N+1)/2 的序列储存,这样可以节省一半的空间。例如取上述矩阵的下半部分:
|
v0 |
v1 |
v2 |
v3 |
v4 |
v0 |
0 |
|
|
|
|
v1 |
1 |
0 |
|
|
|
v2 |
0 |
1 |
0 |
|
|
v3 |
1 |
1 |
0 |
0 |
|
v4 |
0 |
0 |
1 |
0 |
0 |
将上述数据按行优先顺序储存在一个数组里,数组的长度为 N(N+1)/2 。要访问节点 i,j(i行,j列)
之间的连接,可以访问数组的 i∗(i+1)/2+j 位置。
邻接矩阵是一种较为直观的表示方法,它的好处有:
- 方便检查任意一对节点之间是否存在边
- 方便查找所有与某一结点直接相连的节点
- 方便计算节点的度(指向节点的边个数叫入度,从节点指向别的节点的边个数叫出度)。
它的缺点也很明显:对较为稀疏的图(点多边少)而言,空间利用效率不高,计算图的总边数是时间效率不高。
邻接表
使用一个长度为 n
(节点个数)的链表数组 G[n]
储存图。数组的元素 G[i]
表示编号为 i
的节点, G[i]
后接它指向的所有节点指针。
如:
上图的邻接表为:
v0 |
3 |
1 |
|
v1 |
0 |
2 |
3 |
v2 |
1 |
4 |
|
v3 |
1 |
1 |
|
v4 |
2 |
|
|
这样的表示方法不会储存没有连接的无效信息,但是它把每条边都储存了两遍。对于稀疏的图而言,它的空间利用率较高,但是较为稠密的图会浪费较多空间。
邻接表可以方便的查找一个节点的所有直接相连节点,如果储存的图是无向图,它也可以方便的计算出节点的度。但是如果储存的是有向图,邻接表将无法方便的计算出节点的入度,同时它也无法方便地判断出给定节点对之间是否存在边。
图的建立
邻接矩阵
首先给出图的原型:
1 2 3 4 5 6 7
| typedef struct graph { int vertexCount; int edgeCount; WeightType graphMat[MaxSize][MaxSize]; DataType data[MaxSize]; } Graph;
|
图的建立首先需要建立一个只有节点没有边的图:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| Graph *create(int vertexCnt) { Graph *graph = (Graph *)malloc(sizeof(Graph)); graph->vertexCount = vertexCnt; graph->edgeCount = 0; for (int i = 0; i < graph->vertexCount; ++i) { graph->data[i] = 0; for (int j = 0; j < graph->vertexCount; ++j) { graph->graphMat[i][j] = 0; } } return graph; }
|
然后把边插入到图中,边应该保存起点和终点以及权重数据:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| typedef int Vertex; typedef struct edge { Vertex start; Vertex end; WeightType weight; } Edge;
void insertEdge(Graph *graph, Edge *edge) { if (graph == NULL) return NULL; if (edge->start >= graph->vertexCount || edge->end >= graph->vertexCount) return NULL; graph->graphMat[edge->start][edge->end] = edge->weight; graph->graphMat[edge->end][edge->start] = edge->weight; }
|
对于给定的边的集合 Edge edges[someNumber]
只要对其中每个边调用插入函数就可以了
1 2 3 4 5
| Edge edges[cnt]; for(int i = 0;i < cnt;++i) { insertEdge(graph,edges[i]); }
|
邻接表
邻接表表示的图原型有所不同,首先建立节点的原型,根据邻接表的结构,节点应该是一个链表。
1 2 3 4 5 6
| typedef struct lnode { int vertexPosition; WeightType weight; LVertex *next; } LVertex;
|
邻接表应该是一个指针数组,数组元素是链表指针:
邻接表应该是一个指针数组,数组元素是链表指针:
1 2 3 4
| typedef struct table { LVertex *firstVertex; } LTable;
|
根据上面两个结构实现图的结构原型:
1 2 3 4 5 6
| typedef struct lgraph { int vertexCount; int edgeCount; LTable graphTable[MaxSize]; } LGraph;
|
邻接表实现的图建立第一步仍然是建立一个一定数量节点的空图:
1 2 3 4 5 6 7 8 9 10 11
| LGraph *createGraph(int vertexCount) { LGraph *graph = (LGraph *)malloc(sizeof(LGraph)); graph->edgeCount = 0; graph->vertexCount = vertexCount; for (int i = 0; i < graph->vertexCount; ++i) { graph->graphTable[i].firstVertex = NULL; } return graph; }
|
然后将边插入,由于邻接表中只保存了头节点,因此插入方式采用头插法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void insertLEdge(LGraph *graph, Edge *edge) { LVertex *vertex = (LVertex *)malloc(sizeof(LVertex)); vertex->vertexPosition = edge->end; vertex->weight = edge->weight;
vertex->next = graph->graphTable[edge->start].firstVertex; graph->graphTable[edge->start].firstVertex = vertex;
LVertex *sVertex = (Vertex *)malloc(sizeof(Vertex)); sVertex->vertexPosition = edge->start; sVertex->weight = edge->weight;
sVertex->next = graph->graphTable[edge->end].firstVertex; graph->graphTable[edge->end].firstVertex = sVertex; }
|
通过给定边数据建立完整图的过程与邻接矩阵无异。