【数据结构】06图-易微帮

图

1. 定义
2. 图的存储
3. 图的基本操作
4. 图的遍历
- 4.1 广度优先搜索(BFS)
- 4.2 深度优先搜索(DFS)

1. 定义

图（Graph）是一种比线性表和树更复杂的数据结构。在线性表中，数据元素之间是一对一的关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有明显的层次关系，上一层的数据元素（结点）和下一层的数据元素（结点）是一对多的关系。而在图形结构中，数据元素之间的关系是任意的，是多对多的关系。
在图中，数据元素通常称作顶点(Vertex)，简称V，是有穷非空的集合，记为 $V=\{v_1,v_2,...v_n\}$ ，|V|表示顶点个数。两个顶点之间的关系称作边(Edge)，简称E，是有穷的集合，记为 $E={(u,v)|u\in{V},v\in{V}}$ ,|E|表示边的条数。
图简称G，由顶点集V和边集E组成，记作G=(V,E)
在这里插入图片描述
第三幅图不是图的数据结构

1.1 无向图和有向图

在这里插入图片描述
图G1中，每条边是没有方向的（无向边），则图G1是无向图。
图中的边是顶点的无序对，例如顶点V1和V2之间的边，记作(V1,V2)或(V2,V1)都可以。
G1=（V1,E1）
V1={V1,V2,V3,V4,V5}
E1={(V1,V2),(V1,V3),(V2,V4),(V3,V5)}

图G2中，每一条边是有方向的(有向边)，则图G2是有向图
图中的边是顶点的有序对，例如顶点V2和V1之间的边只能记作<V2,V1>
G2={V2,E2}
V2={V1,V2,V3,V4,V5}
E2={<V2,V1>,<V1,V3>,<V3,V5>,<V5,V3>}
有向边也称为弧，<V2,V1>称为顶点V2到顶点V1的弧。V2是弧尾（初始点），V1是弧头（终端点）。顶点V2邻接到顶点V1。
简单图：不存在重复的边，不存在顶点到自身的边

1.2 度、入度和出度

无向图：

顶点的度：与该顶点关联的边的条数。图G1中，TD(V1)=2，TD(V2)=2…
无向图中全部顶点的度的和=边数X2

有向图：

入度：以该顶点为终点的边的条数：ID(V1) = 1,TD(V2)=0
出度：以该顶点为起点的边的条数：OD(V1)=1,OD(V2)=1
度：顶点的度是该顶点的入度和出度之和，TD(V1)=ID(V1)+OD(V1)=2
有向图中全部顶点的入度之和等于出度之和

1.3 图的若干定义

路径：从顶点Vx到Vy的顶点序列
回路：第一个顶点和最有一个顶点相同的路径成为回路或环
简单路径：在路径的序列中，顶点没有重复出现
简单回路：除第一个顶点和最后一个顶点外，其他顶点没有重复出现
路径长度：路径上边的条数
顶点到顶点的距离：顶点之间最短路径的长度，如果不存在路径，记为无穷 $\infin$
在无向图中，如果顶点Vx到顶点Vy有路径，表示Vx和Vy是连通的。
在有向图中，如果顶点Vx到顶点Vy和顶点Vy到顶点Vx都有路径，表示Vx和Vy是强连通的。
连通图：任意两个顶点都是连通的。
强连通图：任意两个顶点都是强连通的。
生成子图：生成子图包含了原图的全部顶点和若干条边
连通分量：无向图中，极大的连通子图称之为连通分量（是连通子图每个连通子图尽可能包含更多的顶点和边）
强连通分量：有向图中，极大的强连通子图称之为强连通分量（是强连通子图每个强连通子图金肯包含更多的顶点和边）
生成树：无向连通图中，生成树是指包含了全部顶点的极小连通子图（连通图全部顶点边最少）
带权图：在一个图中，边可以表示某种含义的数值，例如顶点之间的距离，该数值称为边的权值。如果图的边上带了权值，那么该图称为带权图，或网。带权图中，某条路径上全部边的权值之和，称为该路径的带权路径长度。

1.4 几种特殊的图

完全图
- 无向完全图：图中任意两个顶点都存在一条边
- 有向完全图：图中任意两个顶点都存在方向相反的两条边
稀疏图和稠密图：边很少的图称为稀疏图，反之称为稠密图
树：不存在回路的连通无向图
有向树：有且仅有一个结点的入度为0，除树根外的结点入度为1，从树根到任一结点有一条有向通路

2. 图的存储

图的存储方式有四种：邻接矩阵、邻接表、十字链表、邻接多重表

2.1 邻接矩阵-顺序存储（数组）

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
在这里插入图片描述

对于图：结点之间有连接则边表中对应项记为1，无连接则记为0。但是无向图是A-C和C-A都有，然而有向图则只有C-A没有A-C，需要看清方向。
在无向图的邻接矩阵中，顶点的度为该顶点所在行或列中非零元素的个数。
在有向图的邻接矩阵中，顶点的出度为该顶点所在行中的非零元素的个数，入度为该顶点所在列中的非零元素个数。顶点的度=出度+入度
对于A顶点：无向图的度=3，有向图的度=1+2=3
对于带权图，把每条边的权值存入邻接矩阵，如果顶点之间不存在边存入无穷表示

// 利用邻接矩阵存储图
typedef char VertType; // 定义顶点的数据类型
typedef int EdgeType; // 定义边权的数据类型
#define MAXVNUM 100 // 顶点的最大数值
#define INFINITY 65536 // 无穷常量，也可以用边的权值不可能出现的值

struct MGraph
{
	VertType vexs[MAXVNUM]; // 顶点表
	EdgeType edges[MAXVNUM][MAXVNUM]; // 带权边表，邻接矩阵
	int vexnum, arcnum; // 顶点数|V|和边数|E|
};

2.2 邻接表-顺序存储+链式存储（数组+链表）

顶点的信息存放在一维数组中，每个顶点的边的信息存放在边链表中。
在这里插入图片描述

// 边链表结构体
struct ENode
{
	int adjvex; // 邻接点域，存储该顶点对应的下标
	EdgeType info; // 存储权值
	ENode* next; // 指针域，指向下一个邻接顶点
};
// 顶点结构体
struct VNode 
{
	VertType data; // 数据域，存储顶点信息
	ENode* first; // 边表头指针
};
// 图的结构体
struct AdjListGraph
{
	VNode vexs[MAXVNUM]; //顶点数组
	int vexnum,arcnum; // 顶点数和边数
};

2.3 十字链表-适用于有向图

十字链表就是有两个边链表的邻接表。
在这里插入图片描述

2.4 邻接多重表-适用于无向图

1）边链表结点有冗余，无向图中对于A-B之间的边，在A的边链表中有B，在B的边链表中有A，只需要一个就能表达含义了。
2）删除边和顶点操作很麻烦，时间复杂度高。
在这里插入图片描述

3. 图的基本操作

EdgeExist(G,v,w)

判断图G中是否存在从顶点v到顶点w的边，(v,w)或<v,w>，如(G,C,D)。

邻接矩阵：检查C行D列是否为1。
邻接表中：检查C顶点的边链表中是否有顶点D。

AllAdjVex(G,v)

列出图G中与顶点v邻接的边，如(G,C)
对于无向图：

邻接矩阵：检查C整（行）列，输出为1对应的顶点
邻接表：检查顶点C的边链表，输出顶点。

对于有向图：邻接的边包括出边和入边

邻接矩阵：检查C整行，输出为1对应的顶点（出边）；检查C整列，输出为1对应的顶点（入边）。
邻接表：访问顶点C对应的边链表，输出顶点（出边）；依次访问每个顶点（除C自身）的边链表，如果有C，则输出该顶点（入边）。

InsertVex(G,v)

在图G中插入顶点v，此时不需要插入边，只用插入顶点。

DeleteVex(G,v)

从图G中删除顶点v，如(G,C)。删除顶点C。（真删除和伪删除）
对于无向图：

邻接矩阵：删除顶点表中的C，后续元素前移；邻接矩阵中删除C对应的行列，并移动元素
邻接表：删除顶点表中的C，以及对应的边链表。还要遍历其他顶点，删除边链表中的C

InsertEdge(G,v,w)

在图G中插入一条从顶点v到w的边。如(G,C,D)
无向图

邻接矩阵：C行D列和D行C列都需要置为1
邻接表：顶点C的边链表中插入新结点D；顶点D的边链表中插入新结点C。
有向图：
邻接矩阵：C行D列置为1
邻接表：顶点C的边链表中插入新结点D

4. 图的遍历

4.1 广度优先搜索(BFS)

图的广度优先搜索类似于树的层次遍历，需要使用一个辅助队列和辅助数组（用于记录已经访问过的数组）来实现
在这里插入图片描述
图的遍历可以从任意一个结点开始，假设从顶点2开始。顶点2入队，并查找visited数组中对应的下标是否已经访问，没有置为true。

出队队头元素，并将其邻接点未访问顶点入队，包括5,6,3,1

出队队头元素，并将其邻接点未访问顶点入，5出队后没有入队，6出队后入队7
在这里插入图片描述出队队头元素，并将其邻接点未访问顶点入，3出队后没有元素入队，1出队后入队4

出队队头元素，并将其邻接点未访问顶点入，7出队后没有元素入队，4出队后入队8，9

出队队头元素，8，9。队列为空，遍历完成。