数据结构——图_数据结构 图的表示

一、图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为 G(V,E) ，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

注意: 线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

简单图——1. 不存在重复边，2. 不存在顶点到自身的边

1.1 图的术语

对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。（度为边数的2倍）

对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v); 出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

路径一一顶点v,到顶点v,之间的一条路径是指顶点序列。

回路——第一个顶点和最后一个顶点相同的路径称为回路或环。

简单路径一一在路径序列中，顶点不重复出现的路径称为简单路径。

简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

路径长度一一路径上边的数目。

点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷 ()。

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。

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

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，，则称这两个顶点是强连通的。

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

对于n个顶点的无向图G，若G是连通图，则最少有 n-1 条边；若G是非连通图，则最多可能有  条边。

对于个顶点的有向图G，若G是强连通图，则最少有n条边(形成回路)。

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

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

连通图的生成树是包含图中全部顶点的一个极小连通子图（即要求边最少）。

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

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值

带权图/网——边上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

无向完全图——无向图中任意两个顶点之间都存在边

有向完全图一一有向图中任意两个顶点之间都存在方向相反的两条弧

有向树——一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。

二、图的存蓄

2.1 邻接矩阵法

数组实现的顺序存储空间复杂度高，不适合存储稀疏图。

结点数为n的图 G=(V,E) 的邻接矩阵 A 是 n*n 的。将 G 的顶点编号为v1,v2,..., vn，则

2.2 邻接表法(顺序+链式存储)

2.3 十字链表法 

        以下图为例，有四个顶点A、B、C、D，对它们分别编号0~3。其中A顶点有两个出度，因此从绿色的小块弧尾出发到下一个顶点B，即从弧尾编号0到弧顶编号1，A还有一个出度到C，继续从弧尾相同的下一条弧（绿色小块）出发，指向顶点C，即从弧尾编号0到弧顶编号2。同时，A还有2个入度，从黄色的小块弧头相同的下一条弧指向顶点C，即从弧尾编号2到弧顶编号0，继续从弧头相同的下一条弧（黄色小块）指向顶点D，即从弧尾编号3到弧顶编号0。其他点与A同理。

注意: 十字链表只用于存储有向图。

如何找到指定顶点的所有出边?一一顺着绿色线路找

如何找到指定顶点的所有入边?一一顺着橙色线路找

2.4 邻接多重表存储无向图 

以下图为例，A有两条边，顶点结点中包含有数据域，和一个指向与该顶点相连的第一条边的指针，在A中该指针指向B，即i=0, j=1，依附于顶点i的下一条边（黄色小块）指向与A相连的另一条边D，此时即i=0, j=3 ，其他点与A同理。（由于为无向图所以 i  , j 互换无影响）

2.5 小结

三、图的基本操作

下图为书《大话数据结构》中对图的一些操作接口。 

四、图的遍历

4.1 广度优先算法（BFS）

广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一。

广度优先生成树：邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一。遍历非连通图可得广度优先生成森林。

4.2 深度优先算法（DFS）

其中数组的初始化属性都为 false 。类似于树的先根遍历。

//访问标记数组
bool visited[MAX_VERTEX NUM];
void DFSTraverse(Graph G)//对图G进行深度优先遍历
{
	for (v = 0; v < G.vexnum; ++v)//初始化已访问标记数据
		visited[v] = FALSE;
	for (v = 0; v < G.vexnum; ++v)//本代码中是从v=0开始遍历
		if (!visited[v])//不为true时执行
			DFS(G, v);
}
	
void DFS(Graph G, int v)//从顶点v出发，深度优先遍历图G
{
	visit(v);//访问顶点v
	visited[v]=TRUE;//设已访问标记
	for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, V, w))
	{
		if (!visited[w])//w为u的尚未访问的邻接顶点
		{
			DFS(G, w);
		}
	}
}

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一。

同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一。 

五、最小生成树

5.1 最小生成树的概念

连通图的生成树是包含图中全部顶点的一个极小连通子图。

若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树(Minimum-Spanning-Tree,MST) 。

特点：

1. 最小生成树可能有多个，但边的权值之和总是唯一且最小的。

2. 最小生成树的边数 = 顶点数 –1。砍掉一条则不连通，增加一条边则会出现回路。

3. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。只有连通图才有生成树，非连通图只有生成森林。

5.2 Prim算法（普里姆)

从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

时间复杂度： ，适用于边稠密图。

5.2 Kruskal 算法(克鲁斯卡尔)

每次选择—条权值最小的边，使这条边的两头连通（原本已经连通的就不选)直到所有结点都连通。

时间复杂度： ，适合于边稀疏图。

5.3 最短路径问题

5.3.1 BFS算法求无权图的单源最短路径

注:无权图可以视为一种特殊的带权图，只是每条边的权值都为1。

BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图

5.3.2 迪杰斯特拉（Dijkstra）算法

注意: Dijkstra算法不适用于有负权值的带权图

5.3.3 弗洛伊德（Floyd）算法

Floyd算法: 求出每一对顶点之间的最短路径

使用动态规划思想，将问题的求解分为多个阶段

核心代码如下：

for (int k = 0; k < n; k++) //考虑以 vk 作为中转点
{
	for (int i = 0; i < n; i++)//遍历整个矩阵，i为行号，j为列号
	{
		for (int j = 0; j < n; j++)
		{
 
			if (A[i][j] > A[i][k] + A[k][j])//以 vk 为中转点的路径更短
			{
				A[il[j] = A[i][k] + A[k][j];//更新最短路径长度
				path[il[j] = k;//中转点
			}
		}
	}
}

Floyd算法不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径

5.3.4 小结

六、有向无环图

6.1 拓扑排序

AOV网 (Activity On Vertex Network，用顶点表示活动的网) 用DAG图 (有向无环图) 表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行。

拓扑排序: 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:

1、每个顶点出现且只出现一次。

2、若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为: 拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

拓扑排序的实现:
1、从AOV网中选择一个没有前驱 (入度为0)的顶点并输出
2、从网中删除该顶点和所有以它为起点的有向边。
3、重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止 

6.2 逆拓扑排序

对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序：

1、从AOV网中选择一个没有后继 (出度为0) 的顶点并输出。

2、从网中删除该顶点和所有以它为终点的有向边。

3、重复1和2直到当前的AOV网为空。

七、关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销 (如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)

 AOE网具有以下两个性质:

1、只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;

2、只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生另外，有些活动是可以并行进行的。

概念：

在AOE网中仅有一个入度为0的顶点，称为开始顶点 (源点)，它表示整个工程的开始;也仅有一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。

关键路径：

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

活动 ai 的最早开始时间 e(i) 指该活动弧的起点所表示的事件的最早发生时间

活动 ai 的最迟开始时间 l(i) 它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

活动 ai 的时间余量d(i)= l(i) - e(i)，表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0 即 l(i)= e(i)的活动ai 是关键活动。

由关键活动组成的路径就是关键路径。