标签：路径 借鉴 算法 遍历 权值 顶点 入度 数据结构 408

数据结构 图及其应用

1. 存储及基本操作
   邻接矩阵法
   邻接表法

2. 遍历
   深度优先搜索（DFS）遍历
   广度优先搜索（BFS）遍历

3. 最小生成树
   边稠密: 普里姆(Prim)算法
   边稀疏：克鲁斯卡尔(Kruskal)算法

4. 最短路径
   单源点最短路径：迪杰斯特拉(Dijkstra)算法
   各顶点之间最短路径：弗罗伊德(Floyd)算法

5. AOV网和拓扑排序
   选择没有前驱的结点，输出
   删除该结点和所有以它为起点的有向边

6. AOE网和关键路径
   关键路径
   关键活动
   所有事件的最早发生时间
   所有事件的最迟发生时间

概念

G=(V,E) V是顶点的非空有限集合

有向图和无向图

无向图 e范围[0, n(n-1)/2]
有向图 e范围[0, n(n-1)]

完全无向图 具有n(n-1)/2条边的无向图
完全有向图 具有n(n-1)条边的有向图

稀疏图与稠密图 边或弧较少或较多
一般e<nlogn时，就是稀疏图，反之稠密图

权 边或弧相关的数值
子图（点和边都是子集）与生成子图（全部的点，边子集）

顶点的邻接
顶点的度 入度 出度
路径 路径长度 回路

连通图 任意点相互连通[无向图] 强连通图
图的连通分量（极大的连通子图）[无向图] 强连通分量

无向图的生成树 极小连通子图 全部顶点和只有足以构成一个树的n-1条边
无向图的生成森林 把每个连通分量化成生成树

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

图的存储

1. 邻接矩阵（顺序存储结构） 数组（顶点一维数组、边二维数组 注意下标对应）

• 无相无权图 0、1
• 无相带权图 无穷大、权值 对称矩阵 唯一 每行或每列的非零元素个数表示顶点的度
• 有相无权图 0、1
• 有相带权图 无穷大、权值 唯一 顶点vi的第i行非零元素个数表示出度，第i列非零元素个数表示入度

	#define INFINITY MAX_VAL  //最大值无穷大
	//根据图的权值类型，分别定义为最大整数或实数
	#define MAX_VEX 30        //最大顶点数目
	typedef enum{DG, AG, WDG, WAG} GraphKind;
	typedef struct ArcType{
		VexType vex1,vex2;  //弧或边所依附的两个顶点
		ArcValType ArcVal;  //弧或边的权值
		ArcInfoType ArcInfo;//弧或边的其他信息
	}ArcType;   //弧或边的结构定义

	typedef struct{
		GraphKind kind；    //图的种类标志
		int vexnum,arcnum;  //图的当前顶点数和弧数
		VexType vexs[MAX_VEX];//顶点向量
		AdjType adj[MAX_VEX][MAX_VEX];
	}MGraph;    //图的结构定义

2. 邻接表（链式存储结构）

• 无相无权图 占用空间：n+2e
• 有相无权图 占用空间：n+e 正邻接表（出度） 逆邻接表（入度）

	#define MAX_VEX 30  //最大顶点数
	typedef int InfoType;
	typedef enum {DG, AG, WDG, WAG} GraphKind;
	typedef struct LinkNode{
		int adjvex;				 //邻接点在头结点数组中的位置(下标)
		InfoType info;			 //与边或弧相关的信息，如权值
		struct LinkNode *nextarc;//指向下一个表结点
	}LinkNode;		//表结点类型定义
	
	typedef struct VexNode{
		VexType data;		//顶点信息
		int indegree;		//顶点的度，有向图时入度或出度或没有
		LinkNode *firstarc; //指向第一个表结点
	}VexNode;		//顶点结点类型定义
	
	typedef struct ArcType{
		VexType vex1,vex2 ; //弧或边所依附的两个顶点
		InfoType info;		//与弧或边相关的信息，如权值
	}ArcType;		//弧或边的结构定义
	
	typedef struct{
		GraphKind Kind；	//图的种类标志
		int vexnum；
		VexNode AdjList[MAX_VEX];
	}ALGraph	//图的结构定义

图的遍历

深度优先搜索（DFS）遍历、广度优先搜索（BFs）遍历 采用的数据结构是(正)邻接表

唯一区别： 邻接点搜索次序不同

唯一性： 按照存储结构的顺序进行遍历 邻接矩阵结果唯一 邻接表不唯一，结果不唯一；但给定邻接表，结果唯一

连通分量的数量 等于 调用遍历算法的次数

邻接矩阵的时间复杂度O(n^2) 邻接表的时间复杂度O(n+e)

深度优先遍历树 广度优先遍历树

1. 深度优先搜索（DFS）遍历
   类似于树的按根先序遍历
   用到栈

   当图有e条边时时间复杂度O(e), 总的时间复杂度O(n+e)
   当存在非连通图，多次调用

2. 广度优先搜索（Broadth First Search,BFS）遍历
   类似于树的按层次遍历
   用到队列
   总的时间复杂度O(n+e)
   当存在非连通图，多次调用

最小生成树

生成树的代价 ： 生成树中所有边的权值之和

最小生成树（Minimum Spanning Tree）：带权连通图中代价最小的生成树

算法基本原则

• 尽可能选取权值最小的边，但不能构成回路，即一颗有n个顶点的生成树有且仅有n-1条边。（如果一个图有n个顶点和小于n-1条边，就是非连通图；如果多于n-1条边，就一定有环）
• 选择n-1条边构成最小生成树

MST的性质（用反证法证明）

1. 普里姆(Prim)算法
   按照边权值最小选择的点作为点集合整体参与下一次的选择

   画图或画表格
   时间复杂度O(n^2) 于边的数目无关
   适用于稠密图

2. 克鲁斯卡尔(Kruskal)算法
   将边表按权值排序（取最小值的边，且不能构成环），若采用堆排序或快速排序，则时间复杂度是O(eloge)
   适用于稀疏图

普里姆(Prim)算法与克鲁斯卡尔(Kruskal)算法唯一性：

• 当图的权值都不相等时，不同算法构造的最小生成树是唯一的，但不同算法构造过程可能不唯一
• 当图的权值都不相等时，同一个算法的构造过程是唯一的，并且构造的最小生成树是唯一的
• 当存在相等权值且相等权值位于一个环上，且环上的其他权值比它们小--->MST不唯一，但权值和唯一

某些结论：

• 最小权值的边一定会出现在某棵MST中
• 最小权值的边不一定出现在所有的MST中
• 最小权值一定会出现在所有的MST中

最短路径

1. 单源点最短路径：迪杰斯特拉(Dijkstra)算法
   按照路径长度递增次序产生最短路径的算法
   时间复杂度O(n^2)
   表格
   不适用于有负权值的带权图，不适用于有负回路的带权图 [贪心算法，局部最优解]

2. 任意顶点之间最短路径：弗罗伊德(Floyd)算法
   时间复杂度O(n^3) 空间复杂度O(n^2)
   数据结构基于图的邻接矩阵
   不能解决带有“负权回路”的图（由负权值的边组成回路），这种图有可能没有最短路径

AOV网和拓扑排序

选择没有前驱的结点（入度为0）输出，删除该结点和所有以它为起点的有向边

有向无环图（Directed Acycline Graph）:图中没有回路(环)的有向图 -> 主要用于 研究工程项目的工序问题、工程时间进度问题等
AOV网（Activity On Vertex Network），顶点表示活动的网：顶点表示活动，有向边表示活动之间的优先关系

拓扑排序定义：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1,V2,...,Vn，若满足从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi比在顶点Vj之前。 ---->>拓扑序列（直观理解，先后有序）

在AOV网中，不能有环

检查AOV网有环的方法： 对有向图的顶点进行拓扑排序，若所有定顶点都在其拓扑有序序列中，则无环，否则有环。

有向图的拓扑排序：使得该线性序列不仅保持原来有向图中顶点之间的先后关系，而且对原图中没有优先关系的顶点之间也建立有一种（人为定义的）先后关系

拓扑排序算法

基本思路：
从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AOV网中不存在入度为0的顶点为止。【选择入度为0->因为拓扑排序表示的是一种先后关系，入度为0的点表示没有前驱】

算法思想实现步骤：
1.在AOV网中选择一个没有前驱的顶点输出
2.在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边)
3.重复1、2，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)

算法分析：时间复杂度O(n+e)

唯一性：往往不唯一

若AOV网中有环，则一定不存在拓扑排序。
有两种情形：
1.不存在入度为0的顶点
2.虽然存在入度为0的顶点，但途中某个部分存在环，也没有拓朴序列

AOE网和关键路径

AOE网（Activity On Edge, 边表示活动的网）

一个带权的有向无环图，图中顶点表示事件，每个事件表示在其前的活动已经完成，其后的活动才可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用。

研究问题：
1.完成整个工程至少需要多少时间
2.哪些活动是影响工程进度的关键

路径长度：路径上各个活动所持续的时间之和

关键路径：从起点到终点具有最大长度的路径

关键活动：关键路径上的活动，影响整个工程的关键

关键路径是AOE中路径长度最大的路径，也是完成工期的最短时间

与关键路径相关的4个概念：

• 事件的最早发生时间ve(i)：即顶点vi的最早发生时间。设v0是起点，从v0到vi的最长路径长度称为事件vi的最早发生事件，即是以vi为尾的所有活动的最早发生时间。
• 事件大的最晚发生时间vl(i)：即顶点vi的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
• 活动的最早开始时间e(i)：即弧ai活动的最早发生时间
• 活动的最晚开始时间l(i)：即弧ai活动的最晚发生时间，是不推迟工期的最晚开工时间

活动的最早开始时间采用正推法，从源点开始计算，当遇到多个路径时，取最大的路径

活动的最晚开始时间采用倒推法，从终点开始计算，当遇到多个路径时，取最小的路径

l(i)-e(i) 定义为松弛量，关键活动的松弛量为0，关键活动的时间决定了整个工期的进度

缩短关键路径：缩短关键活动时间。如果有多条关键路径，缩短工期需要将所有的关键路径都缩短。

标签：路径,借鉴,算法,遍历,权值,顶点,入度,数据结构,408
From： https://www.cnblogs.com/yongchao/p/17154907.html