数据结构学习笔记11——图

1.图的认知1.1图的定义1.2图的逻辑结构应用1.3无向图与有向图1.3.1无向图1.3.2有向图 1.4简单图与多重图1.4.1简单图1.4.2多重图 1.5度1.5.1无向图的度1.5.2有向图的度 1.6 顶点之间的关系1.7连通图与强连通图1.8子图1.9连通分量1.10生成树与生成森林1.11带权图(网)1.12其他特殊图 2图的存储2.1邻接矩阵法2.1.1邻接矩阵2.1.2 邻接矩阵的性质2.1.3邻接矩阵代码实现 2.2邻接表法2.2.1理解邻接表2.2.2 邻接表代码实现 2.3十字链表2.3.1理解十字链表2.3.2 十字链表代码实现 2.4邻接多重表 3.图的操作与遍历3.1基本操作3.2图的遍历

1.图的认知

1.1图的定义

图G(Graph)由顶点集V(Vertex)和边集E(Edge)组成，记为G=(V,E)，V(G)表示图G中顶点的有限非空集：E(G)表示图G中顶点之间的关系（边）集合。若V={v1,v2,…vn}，则 |V| 表示图G中顶点的个数，也称为图的阶，E={(u,v)|u∈V,v∈V}，用|E|表示图G中边的条数。

注：线性表可以是空表，树可以是空树，但是图不能是空图。

顶点与边的关系：可以有顶点没有边，但是不能有边无顶点

1.2图的逻辑结构应用

图在现实生活中具有许多逻辑应用

铁路网，V：车站,E：铁路

好友关系，V：英雄，E：战友，队长…

知识关系：V：知识点,E：联系

1.3无向图与有向图

1.3.1无向图

若E是无向边(简称边)的有限集合时，则称图G为无向图。边是顶点的无序对，记作（v,w）或（w,v）,对无向图来说（v,w）=（w,v），其中v，w为顶点，v,w也互为邻接点。边（v,w）与顶点w和v相关联。

1.3.2有向图

若E是有向边(简称弧)的有限集合时，则称图G为有向图。弧是顶点的有序对，记作<v,w>,其中v，w为顶点，w称为弧头，v称为弧尾，<v,w>称为从顶点v到顶点w的弧。<v,w>≠<w,v>。

1.4简单图与多重图

1.4.1简单图

简单图的定义：

不存在重复的边。不存在顶点到自身的边。

1.4.2多重图

多重图的定义:

存在重复边存在顶点到自身的边

1.5度

1.5.1无向图的度

对于无向图来说，顶点v的度是指与该顶点连接的边的条数，记作TD(v)。 通常称度为1的节点为悬挂点,与悬挂点关联的边为悬挂边。如下图的A和(A,D)

图的总度数=边的数量x2 $$\sum _{i=1}^{n}TD(v_i)=2|E|$$

1.5.2有向图的度

对于有向图来说，具有出度和入度。 入度是以顶点v为终点的有向边的数目，记作ID(v)。(即弧头(箭头)所指的顶点) 出度是以顶点v为起点的有向边的数目，记作OD(v)。（即弧尾所在的顶点，或理解为射线的起始位置） 有向图顶点的度指的是入度和出度之和。 $$TD(v_i)=ID(v_i)+OD(v_i)$$ 对有向图来说，入度之和=出度之和=边的数量 $$\sum _{i=1}^{n}ID(v_i)=\sum _{i=1}^{n}OD(v_i)=|E|$$

1.6 顶点之间的关系

例图1

例图2

路径：顶点Vp到顶点Vq之间的路径，如A到E：（A,B,E）,(A,B,D,E)，注意：有向图路径也是有向的

回路：第一个顶点和最后一个顶点相同的路径称为回路(或称为环)，如例图2中<A,B,E,C,A>

简单路径 ：顶点不重复出现的路径即为简单路径，如例图1中的(A,D,C,E)

简单回路：除首尾顶点外，其他顶点不重复的回路。

路径长度：路径上边的数目，如例图1中(A,D,C,E)经过3条边，则路径长度为3。

点到点的距离：顶点U出发到顶点V的最短路径(若存在)，则称为从U到V的距离，若不存在，则称为∞。

连通：无向图中，若顶点v到w的路径存在，则称v和w是连通的，反之为不连通的。

强连通：有向图中，若顶点v到w的路径存在，顶点w到v的路径也存在，称顶点v和w是强连通的。

1.7连通图与强连通图

连通图 若图中任意两个顶点都是连通的，则称图G为连通图，反之则为非连通图。

强连通图 若图中任何一对顶点都是强连通的，则称图G为强连通图。

性质 对于n个顶点的无向图G1：若G1是连通图，最少有n-1条边；若G1是非连通图，边数最多有$$C_{n-1}^2$$ 对于n个顶点的有向图G2，若G2是强连通图，最少有n条边（形成回路）。

1.8子图

两个图中，图G1=(V1,E1)和G2=(V2,E2)，若V2是V1的子集，E2是E1的子集，则称G2是G1的子图。

若子图G3中包含G1的所有顶点(即V(G1)=V(G3))，则称G3为G1的生成子图(对边无要求)。有向图亦是如此。

1.9连通分量

无向图中的极大连通子图称为连通分量。

极大连通子图要求子图必须连通，并且包含尽可能多的顶点和边。

通俗理解：G2为大陆铁路网，G3为韩国铁路网，G4为日本铁路网

有向图的极大强连通子图称为强连通分量。

1.10生成树与生成森林

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图(即边尽可能少)。 如果图的顶点数为n，则图的生成树则有n-1条边。对生成树来说，少一条边则会变成非连通图，加上一条边则会形成回路。

生成森林 在非连通图中，连通分量的生成树构成了非连通图的生成森林。

无向图 - 连通分量 - 生成森林 将三个连通分量化为极小连通子图则为生成森林。

1.11带权图(网)

边的权：在图G中，每条边都可以标上具有某种含义的数值，该数值称为边的权值。 带权图：边上带有权值的图称为带权图，或网。

1.12其他特殊图

无向完全图:任意两个顶点都存在边，边的总数为 $$C_n^2$$ 图如下：

有向完全图：任意两个顶点之间都存在方向相反的两条弧。 边的总数为 $$2C_n^2$$ 图如下：

稀疏图：边数很少的图

稠密图

树：不存在回路，且连通的无向图。n个顶点的数，必有n-1条边。

有向树：一个顶点的入度为0，其余顶点都为1的有向图。

2图的存储

2.1邻接矩阵法

2.1.1邻接矩阵

无向图

由例图可得图G1的邻接矩阵：

从中可知，若要求B的度，则将B的行（或列）相加，也即遍历行或者列就可以得到某个顶点的度。 注意，无向图邻接矩阵关于对角线对称。

$$第i个节点的度=第i行(或列)的非零元素个数.$$

有向图(网) 在有向图的基础上，再加上每条边的权值便形成了带权图(或称网)

由例图可得图G2的邻接矩阵：

对于网来说，不能到达的顶点距离为无穷。

2.1.2 邻接矩阵的性质

以如下不带权的无向图G3为例，

设图G3的邻接矩阵为A3，则A3^n 的元素 ：A3^n[i][j]=顶点 i 到顶点 j 的长度为 n 的路径数目。 例： $$A_{}^2=\left(\begin{array}{cccc}{0}_{}& 1_{}& 0_{}& 0_{}\\ 1_{}& 0_{}& 1_{}& 1_{}\\ 0_{}& 1_{}& 0_{}& 1_{}\\ 0_{}& 1_{}& 1_{}& 0_{}\end{array}\right)\left(\begin{array}{cccc}{0}_{}& 1_{}& 0_{}& 0_{}\\ 1_{}& 0_{}& 1_{}& 1_{}\\ 0_{}& 1_{}& 0_{}& 1_{}\\ 0_{}& 1_{}& 1_{}& 0_{}\end{array}\right)$$ 则有： $$A_{}^2[1][4]=a_{11}{a}_{14}+a_{12}{a}_{24}+a_{13}{a}_{34}+a_{14}{a}_{44}=1$$ a11a14代表从顶点A->A再从A->D的路径 a12a24代表从顶点A->B再从B->D的路径 以此类推，a13a34=A->C,C->D；a14a44=A->D,D->D 从而可知上式代表从A到D，路径长度为2仅有1条路。 $$A_{}^3[1][4]：求从A到D长度为3的路径有几条，需3个矩阵相乘$$ 注：邻接矩阵的方式适合用于存储稠密图，对于稀疏图来说，会造成极大的空间浪费。其空间复杂度为O(|V|^2)。

2.1.3邻接矩阵代码实现

以2.1.1无向图G1为例，实现邻接矩阵代码如下：

#include <stdio.h> #include <stdlib.h> #define ZERO 0 #define MAXVECNUM 15 //最大顶点数 #define INFINITY 65535//无穷 //注意，指向自身的边有时候也会定义为无穷 typedef char VertexType;//顶点类型 typedef int EdgeType;//边上的权值，带权图使用， //邻接矩阵 Adjacency Matrix Graph typedef struct { VertexType Vex[MAXVECNUM];//顶点表 EdgeType Edge[MAXVECNUM][MAXVECNUM];//邻接矩阵 int vexNum, edgesNum;//图的顶点数，边(弧)的数目 }MGraph, * MG; //创建邻接矩阵 void CreateMGraph(MG G) { int i, j, k, w; printf("请输入顶点数目和边的数目:\n"); //scanf("%d%d", &G->vexNum, &G->edgesNum); G->vexNum = 6;//测试用数据 G->edgesNum = 7;//测试用数据 //遍历读取顶点，建立顶点表 printf("输入所有顶点:"); for (i = 0; i < G->vexNum; i++) { scanf("%s", &G->Vex[i]); } //邻接矩阵初始化 for (i = 0; i < G->vexNum; i++) { for (j = 0; j < G->vexNum; j++) { //G->Edge[i][j] = INFINITY;//网的初始化 G->Edge[i][j] = 0;//不带权无向图初始化 } } for (k = 0; k < G->edgesNum; k++) { printf("请输入边(vi,vj)的下标(i,j)和权重w\n");//无向图权值(w)默认为1; //scanf("%d%d", &i, &j); scanf("%d%d%d", &i, &j, &w); G->Edge[i][j] = 1; G->Edge[j][i] = G->Edge[i][j];//无向图的邻接矩阵关于对角线对称 } } /打印邻接矩阵 void printGraph(MG G) { int i, j, k; printf("\t"); for ( i = 0; i < G->vexNum; i++) { printf("%c\t", G->Vex[i]); } printf("\n"); for (i = 0; i < G->vexNum; i++) { for (j = i; j <= i; j++) { printf("%c\t",G->Vex[j]); for ( k = 0; k < G->vexNum; k++) { printf("%d\t", G->Edge[i][k]); } printf("\n"); } } } int main() { MG g = (MG)malloc(sizeof(MGraph)); CreateMGraph(g); printGraph(g); system("pause"); return 0; }

运行结果如下：

2.2邻接表法

2.2.1理解邻接表

无向图 仍以无向图G1为例，则获得邻接表如下： 有向图

邻接表法采用数组与链表结合的方式来实现图的数据结构。 邻接表较为适合存储稀疏图。 对于无向图，邻接表法整体空间复杂度为O(|V|+2|E|)。 对于有向图，整体空间复杂度为O(|V|+|E|)。

2.2.2 邻接表代码实现

同样以无向图G1为例，实现代码如下：

#include <stdio.h> #include <stdlib.h> #define ZERO 0 #define MAXVECNUM 15 //最大顶点数 #define INFINITY 65535//无穷，注意，指向自身的边有时也会定义为无穷 //邻接表法 Adjacency List //弧表节点 typedef struct ArcNode { int adjVertex;//弧(边)指向哪个节点 struct ArcNode* pnext;//指向下一条弧(边) }ArcNode; //顶点节点 typedef struct VertexNode{ VertexType data;//顶点信息 ArcNode* firstEdge;//第一条弧(边) }VNode, AdjList[MAXVECNUM]; typedef struct { AdjList adj_list; int vexNum, arcNum;//图的节点数和弧数 }ALGraph; //函数1 建立邻接表 void CreateAdjListGraph(ALGraph *AG) { printf("请输入节点个数，边的个数：\n"); //scanf("%d%d", &AG->vexNum, &AG->arcNum); AG->vexNum = 6;//测试用 AG->arcNum = 7;//测试用 //建立顶点表 printf("请输入所有顶点:\n"); for (size_t i = 0; i < AG->vexNum; i++) { scanf("%s", &AG->adj_list[i].data); AG->adj_list[i].firstEdge = NULL; } //建立边表 int i, j; for (size_t m = 0; m < AG->arcNum; m++) { printf("请输入边(vi,vj)的顶点下标i,j\n"); scanf("%d%d", &i, &j); //建立顶点i到j的边 //1.申请边(弧)节点i并初始化 ArcNode *Ei = (ArcNode*)malloc(sizeof(ArcNode)); memset(Ei, 0, sizeof(ArcNode)); //2.定义邻接节点 Ei->adjVertex = j; //3.头插移动指针 if (NULL == AG->adj_list[i].firstEdge) { AG->adj_list[i].firstEdge = Ei; } else { Ei->pnext = AG->adj_list[i].firstEdge; AG->adj_list[i].firstEdge = Ei; } //申请节点j并初始化，下同 ArcNode* Ej = (ArcNode*)malloc(sizeof(ArcNode)); memset(Ej, 0, sizeof(ArcNode)); Ej->adjVertex = i;//对无向图来说,i,j互为各自的邻接节点 if (NULL == AG->adj_list[j].firstEdge) { AG->adj_list[j].firstEdge = Ej; } else { Ej->pnext = AG->adj_list[j].firstEdge; AG->adj_list[j].firstEdge = Ej; } } } //函数2 打印图的数据 void printALGraph(ALGraph *AG) { int i, j, k; printf("Data\tHead\n"); for (i = 0; i < AG->vexNum; i++) { for (j = i; j <= i; j++) { printf("%c\t", AG->adj_list[j]); int k = 0; ArcNode* Acur; Acur = AG->adj_list[i].firstEdge;//头节点 //遍历链表进行打印 while (k < AG->vexNum) { if (NULL == Acur) { printf("∞\t"); } else { printf("%d\t", Acur->adjVertex); Acur = Acur->pnext; } k++; } printf("\n"); } } } int main() { ALGraph G; CreateAdjListGraph(&G); printALGraph(&G); system("pause"); return 0; }

运行结果如下：

2.3十字链表

2.3.1理解十字链表

十字链表用于存储有向图，有向网。 如图D1

对于十字链表来说，分为顶点结点与弧节点两部分。

顶点节点 datafirstinfirstout

firstin：该顶点作为弧头的第一条弧。 firstout：该顶点作为弧尾的第一条弧。 如：

A<C,A><A,B> 弧节点 tailVexheadVexinfohlinktlink

tailVex：弧尾顶点编号。 headVex：弧头顶点编号。 info：权值 hlink：弧头相同的下一条弧。 tlink：弧尾相同的下一条弧。

由此可推出图D1的十字链表如下图所示： 注：^表示NULL，空间复杂度：O(|V|+|E|)

2.3.2 十字链表代码实现

#include <stdio.h> #include <stdlib.h> #define ZERO 0 #define MAXVECNUM 15 //最大顶点数 #define INFINITY 65535//无穷，注意，指向自身的边有时候也会定义为无穷 typedef char VertexType;//顶点类型 typedef int EdgeType;//边上的权值，带权图使用 //十字链表法数据结构 Orthogonal List //顶点节点 typedef struct VexNode { VertexType data;//顶点信息 struct VexNode* firstIn, * firstOut;//顶点的第一条入边和出边 }VexNode, VexList[MAXVECNUM]; //弧节点 typedef struct ArcNd { int tailIndex, headIndex;//弧头弧尾的顶点编号 struct ArcNd* hLink, * tLink;//与弧头弧尾相同的下一条弧 EdgeType info;//权值 }*Arc,ArcNd; //封装十字链表结构 typedef struct { VexList Orth_list; int vexNum, arcNum;//顶点数量，弧的数量 }OrList; //获取弧头节点 Arc getArcNode(int tailIndex, int headIndex) { //初始化弧头节点 Arc Anew = (Arc)malloc(sizeof(ArcNd)); memset(Anew, 0, sizeof(ArcNd)); if (Anew) { Anew->headIndex = headIndex; Anew->tailIndex = tailIndex; } return Anew; } //获取弧节点数据 int getArcData(char data, OrList* G) { for (size_t i = 0; i < G->vexNum; i++) { if (G->Orth_list[i].data == data) { return i; } } return -1; } //创建十字链表 void CreatOrthList(OrList* G) { int i, vexDatai, vexDataj; printf("请输入图的顶点和弧的数量:\n"); scanf("%d%d", &G->vexNum, &G->arcNum); //读取顶点，建立顶点集 for ( i = 0; i < G->vexNum; i++) { printf("请输入第%d个顶点的值：", i + 1); scanf("%s", &G->Orth_list[i].data); G->Orth_list[i].firstIn = G->Orth_list[i].firstOut = NULL;//初始化指针，置为空 } //读取弧，建立顶点之间的关系 for ( i = 0; i < G->arcNum; i++) { char vex1, vex2; char t1, t2, t3, t4; printf("请逐个输入弧<Vi,Vj>："); scanf("\n%c,%c%*c", &vex1, &vex2); //初始化弧节点 vexDatai = getArcData(vex1, G); vexDataj = getArcData(vex2, G); Arc Atemp = getArcNode(vexDatai, vexDataj); //处理尾 Atemp->tLink = G->Orth_list[vexDatai].firstOut; Atemp->tailIndex = vexDatai; G->Orth_list[vexDatai].firstOut = Atemp; //处理头 Atemp->hLink = G->Orth_list[vexDataj].firstIn; Atemp->headIndex = vexDataj; G->Orth_list[vexDataj].firstIn = Atemp; } } int main() { OrList G; Arc A; CreatOrthList(&G); int i; for (i = 0; i < G.vexNum; i++) { printf("%c顶点的出度情况为：\n", G.Orth_list[i].data); A = G.Orth_list[i].firstOut; if (!A) { printf("NULL\n"); } while (A) { printf("<%d->%d>\n", A->tailIndex, A->headIndex); A = A->tLink; } printf("%c顶点的入度情况为：\n",G.Orth_list[i].data); A = G.Orth_list[i].firstIn; if (!A) { printf("NULL\n"); } while (A) { printf("<%d->%d>\n", A->tailIndex, A->headIndex); A = A->hLink; } printf("-------------------------------------------\n"); } }

以图D2测试，运行结果1： 以图D1为例，运行结果2：

2.4邻接多重表

邻接多重表常用于存储无向图。

提示：这里可以添加要学的

---

3.图的操作与遍历

3.1基本操作

Adjacent(G,x,y)：判断图是否存在边<x,y>或(x,y)。 Neighbors(G,x)：返回图G中与 x 节点相邻的边。 InsertVertex(G,x)：图G中插入顶点x。 DeleteVertx(G,x)：图G中删除顶点y。 AddEdge(G,x,y)：图G中增加边<x,y>或(x,y)。 RemoveEdge(G,x,y)：图G中删除边<x,y>或(x,y)。 FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若存在返回顶点号，若不存在返回 -1。 NextNeighbor(G,x,y)：假设图G中顶点x的邻接点是y。返回除y之外，顶点x的下一个邻接点的顶点号，若不存在下一个邻接点则返回-1。 GetEdgeValue(G,x,y)：获取图G中边<x,y>或(x,y)的权值。 SetEdgeValue(G,x,y)：设置图G中边<x,y>或(x,y)的权值。

3.2图的遍历

后续逐步更新