[数据结构与算法]王道数据结构6.2（图的应用）

一、最小生成树

（一）什么是最小生成树？

1. 对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树。
2. 一个连通图的生成树包含图的所有的顶点，并且只尽可能少的边，对于生成树而言，若砍去它的一条边，则生成树变成非连通图，若给它增加一条边，则会形成图中的一条回路。
3. 只有连通图才有生成树，非连通图只有生成森林。
4. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。
5. 最小生成树不是唯一的，但是当各个边的权值互不相同时，最小生成树是唯一的，若无向连通图的边数比顶点少1，即本身就是一个树，则最小生成树就是它自身。
6. 最小生成树的权值总和却是唯一的，是最小的。

（二）求最小生成树算法

1. 都是基于贪心算法的策略。
2. 总体思路：确定顶点集合中有关的边，寻找到最小代价边(u,v),判断加入集合后会不会产生回路，若不会，则为最小生成树的一员。

（1）prim算法

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

int dist[n],state[n],pre[n];
dist[1] = 0;
for(i : 1 ~ n)
{
    t <- 没有连通起来，但是距离连通部分最近的点;
    state[t] = 1;
    更新 dist 和 pre;
}

3. 时间复杂度：O(|V|2)，适合于稠密图。
4. 算法实现，以图示为例：
   
   （1）首先从V0开始，构建两个表，分别是isjoin[]：记录各个结点是否已经加入树，初始时，v0为true，其他为false；lowCost[]:各个节点加入树的最低代价。
   （2）如图所示：lowCost数组的意思：小集团中只有v0存在的情况下，v1到v0最少需要6，v2到v0需要5，v3需要1，而v45没有连通，为∞。
   （3）对比lowCost数值，得到v3最小，则修改isjoin[3]=true，并且将lowCost更新为：v1可以于v3连通为5,5<6，则改为5，v2可以有4/5，则填入4，v3仍为1，v4为6，v5为4，总之lowCost为054164，扫描一遍lowCost数组选择false中最小的，即v2/v5。
   （4）重复以上过程，直到isjoin所有都变成true。

（2）Kruskal算法（克鲁斯卡尔）

1. 思路：每次选择一条权值最小的边，使者条边的两头连通（原本连通的就不选），直到所有结点都连通。
2. 时间复杂度：O(|E|log2|E|)，适用于边稀疏图。
3. 算法实现过程：
   
   （1）如图所示，首先对所有的边进行大小排序
   （2）第一轮：检查第一条边的两个顶点是否连通（是否属于同一个集合，意思是，初始的时候所有顶点都是独自成为一个集合，都不互相连通，当选取顶点以后，被选择的顶点就属于一个集合，并且连在一起，其他顶点保持不变），如果顶点不是一个集合，则选择存入被选中集合，即选择（v0，v3）（v2，v5）（v1，v4）（v2，v3）而到（v3，v5）时，由于借助v2实现了连通，则跳过不建立集合，如下图所示，类似的后序寻找
   （3）一共需要执行e轮，每轮判断两个顶点是否属于同一个集合，需要O(log2e)，总时间复杂度为O(elog2e)

二、最短路径问题

（一）单源最短路径问题

（1）BFS算法（无权图）

1. 类似于广度优先遍历算法
2. 代码：

#include <stdio.h>
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
int Max = 0x3f3f3f3f;

typedef struct {
	VertexType Vex[MaxVertexNum];
	EdgeType EdgeType[MaxVertexNum][MaxVertexNum];
	int vexnum, arcnum;
} Gragh;

//BFS遍历
bool visited[MaxVertexNum];
void BFSTraverse(Graph G) {
	for (int i = 0; i < G.vexnum; ++i)
		visited[i] = false;
	InitQueue(Q);
	for (int i = 0; i < G.vexnum; ++i)
		if (!visited[i])
			BFS(G, i);

}

void BFS(Graph G, int v) {
	visit(v);
	visited[v] = true;
	Enqueue(Q, v);
	while (!isEmpty(Q)) {
		DeQueue(Q, v);
		for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
			if (!visited[w]) {
				visit(w);
				visited[w] = true;
				EnQueue(Q, w);
			}
	}
}
//BFS求单源最短路径
void BFS_MIN_Distance(Graph G, int u) {
//d[i]表示从u到i结点的最短路径
	for (int i = 0; i < G.vexnum; i++){
		d[i] = Max; //初始化路径为无穷
		path[i]=-1;//最短路径从哪个顶点过来
		}
	visited[u] = true; 
	d[u] = 0;
	EnQueue(Q, u);
	while (!isEmpty(Q)) {
		DeQueue(Q, u);//队头元素u出队
		for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))//找到和它相邻的所有结点+
			if (!visited[w]) {//w为u的尚未访问的邻接顶点
				visited[w] = true;//设已访问的标记
				d[w] = d[u] + 1;//路径长度+1
				path[w]=u;//最短路径应该是从u到v
				EnQueue(Q, w);//顶点w入队
			}//if
	}//while
}

3. 过程：从2号顶点开始
   ① 首先初始化d和path和visited数组
   队列：NULL

② 修改起始节点的数组，并且将2结点压入队列中
队列：2

③ 非空进入while循环，取出队首元素2，判断与2相连的所有结点：1,6，1结点的visited为false,1的d[]数组改为1+d[2],并且path[1]=2,表示与结点2距离为1，并且最短路径中前驱是2,并且将1压入队列；6号结点同理，6的d[]数组改为1+d[2]=1,并且path[6]=2，visited[6]=true,并且将6压入队列
队列：1、6

④ 取出队首1，判断1的连通未访问的顶点为5，则5的d[5]改为d[1]+1=1+1=2,path[5]=1,visited[5]=1,入队
队列：6、5

⑤ 判断6 判断5即可得到
队列：1、6

得到上述表格，问2到8的路径=d[8]=3,路径逆向思维进行寻找，8前为7,7前为6,6前为2，得到:2->6->7->8
4. 分析：广度优先生成树其实层数就反映了到达其他节点的最短路径，换句话说，利用广度优先构造的最小生成树，高度一定是最小的。

（2）Dijkstra算法（带权图、无权图）

1. BFS算法的局限性：BFS算法只适合于不带权或带权值都相同的情况，如果带权权值不同则会出现错误。
2. 过程：
   ① 初始化三个数组：final[] (标记各顶点是否已找到最短路径)、dist[] （最短路径长度）、path[]（路径上的前驱）。

如图所示：当前可以确定的是v0可以到v4，可以到v1，分别是5,10，写入数组，并且修改path1,4的前驱为0 。
② 第一轮，循环遍历所有结点，找到目前还没有确定最短路径，且dist最小的顶点v，令final[i]=ture。如本题，最小dist为4的5，即可以说明v0到v4的最短路径为5，修改final[4]=√，并且检查所有和v4相邻的顶点，寻找有没有可能v0经过v4到其他点路径更近，发现v0v4v1长度为5+3=8＜10=v0v1，所以让dist[1]=8，同理dist[2]=5+9=14,path[2]=4,dist[3]=7,path[3]=4。

③第二轮，随后检查所有final值为false的顶点的，发现目前dist最小的是7，则处理3顶点，让final为√，表示已经可以确定v0->v3最短为7，且路径为0->4->3,然后检查所有v0经过v3到达的顶点vi，修改得

④ 检查所有final值为×的结点，选择1，更新后检查v4，v2，因为v4之前已经确定了，所以无需检查只要看v2即可，
⑤ 一直到final值全部为√。

3. 分析
   （1）代码思路：以从v0开始为例，初始时

final[0]=ture;dist[0]=0;path[0]=-1;
final[k]=false;dist[k]=arcs[0][k];path[k]=(arcs[0][k]==∞)?-1:0;

（2）需要经过n-1轮循环，循环遍历所有结点，找到还没有确定最短路径，且dist最小的顶点vi，令final[i]=true。检查所有邻接自vi的顶点，对于邻接自vi的顶点vj，若final[j]==false且dist[i]+arcs[i][j]<dist[j],则令dist[j]=dist[i]+dist[i][j],path[j]=i。
（3）时间复杂度：由于每一轮都要扫描所有数组，数组长度为n顶点个数，并且还要扫描邻接矩阵，则O(2n)~O(n)，因为要扫描n-1轮，则时间复杂度为O(n(n-1)~O(n2)
（4）和prim算法很是相似，时间复杂度也是相似的
（5）注意：如果带权图中权值有负数，则这个算法将会出错，不适用。

（二）多源最短路径问题— Floyd算法（带权图、无权图）

1. 使用的是动态规划思想，将问题分为多个阶段。
2. 思路：
   （1）弗洛伊德算法定义了两个二维矩阵：
   ① 矩阵A记录顶点间的最小路径
   例如A[0][3]= 10，说明顶点0 到 3 的最短路径为10；
   ② 矩阵Path记录顶点间最小路径中的中转点
   例如Path[0][3]= 1 说明，0 到 3的最短路径轨迹为：0 -> 1 -> 3。
   （2）它通过3重循环，k为中转点，v为起点，w为终点，循环比较A[v][w] 和 A[v][k] + A[k][w] 最小值，如果A[v][k] + A[k][w] 为更小值，则把A[v][k] + A[k][w] 覆盖保存在A[v][w]中。
3. 过程：
   ① 首先，初始化两个二维矩阵，让A[]存放各个点之间的距离，不连通则为0/∞，path[]都为-1
   

② 以 A 为「中转站」，刷新所有「入度」和「出度」的距离，A 的入度有 B 、D 2点，A 的出度也是 B、D 2，BA + AD > BD，DA + AB > DB，所以没有更小的距离，不能「刷新距离」，A[][] 和 path[][] 不刷新。
③ 以 B 为「中转站」，刷新所有的「入度」和「出度」的距离，B 的入度有 A、C、D；B 的出度有 A、C、D。（所以一共有 6 种组合）：
(1) AB + BC < AC （ 2 + 3 < 无穷大，这里的 -1 代表无穷大），将 AB + BC 的距离 5 赋值给 AC 距离 -1，即 A[0][2] = A[0][1] +A[1][2]，AC 的最短距离不再是直线 AC 的最短距离，引入「中转站」B 点，即 path[0][2] = 1
(2)AB + BD < AD （ 2 + 2 < 6)，将 AB + BD = 4 的值赋值给 AD，即 A[0][3] = A[0][1] +A[1][3]，AD的最短距离不再是直线 AD 的最短距离，引入「中转站」B 点，即 path[0][3] = 1。
(3) DB + BC < DC（2 + 3 < 2 ，不用刷新距离）

④ 最后结果：
A
0 2 5 4
2 0 3 2
5 3 0 2
4 2 2 0
path
0 1 1 1
0 1 2 3
1 1 2 3
1 1 2 3

4. 代码
   （1）结构设置

typedef struct struct_graph{
    char vexs[MAXN];
    int vexnum;//顶点数 
    int edgnum;//边数 
    int matirx[MAXN][MAXN];//邻接矩阵 
} Graph;

（2）Floyd

//这里是弗洛伊德算法的核心部分 
    //k为中间点 
    for(k = 0; k < G.vexnum; k++){
        //v为起点 
        for(v = 0 ; v < G.vexnum; v++){
            //w为终点 
            for(w =0; w < G.vexnum; w++){
                if(D[v][w] > (D[v][k] + D[k][w])){
                    D[v][w] = D[v][k] + D[k][w];//更新最小路径 
                    P[v][w] = P[v][k];//更新最小路径中间顶点 
                }
            }
        }
    }

（3）求最短距离

    v = 0;
    w = 3;
    //求 0 到 3的最小路径
    printf("\n%d -> %d 的最小路径为：%d\n", v, w, D[v][w]);
    k = P[v][w];
    printf("path: %d", v);//打印起点
    while(k != w){
        printf("-> %d", k);//打印中间点
        k = P[k][w]; 
    }
    printf("-> %d\n", w);

5. 时间复杂度：O(|v|3)
6. 分析：无法解决“带负权回路”的图。

（三）总结

注意：也可以使用Dijkstra算法求取各个顶点之间的最短路径，重复V次即可，时间复杂度也是O(V3)。

三、有向无环图的表达式

1. 有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图。
2. 规律：顶点部分不可能出现重复的。
3. 方法：
   ① 先对各个操作数不重复的排成一排
   ② 标出各个运算符的生效顺序（先后顺序有点出入无所谓）
   ③对运算符按顺序加入，注意分层
   ④ 自底向上逐层检查同层的运算符是否可以合体
4. 注意：最终得到的图像是不唯一的。

四、拓扑排序

1. AOV网：用DAG图表示一个工程，顶点表示活动，有向边<Vi,Vj>表示活动Vi必须优先于Vj进行。
2. 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
   ① 每个顶点出现且只出现一次
   ② 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
3. 拓扑排序的实现：

①从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
② 从网中删除该顶点的所有以它为起点的有向边。
③ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。
4. 每个AOV网会有多个拓扑排序，不是所有的图都会有拓扑排序，有回路的图是不存在拓扑排序的

5. 代码：
   （1）准备：
   设置indegree[]数组存储每个顶点当前的入度
   topo[]存放生成G的一个拓扑排序
   利用栈存储度为0的顶点。
   （2）过程
   拓扑排序算法思路：
   1：求出各结点的入度存入数组indegree中
   2：遍历indegree[i]数组，将单元值为0的编号值i进栈
   3：将栈顶元素保存在topo数组中，并将此元素出栈。
   4：定义指向边结点的指针，使该指针从出栈元素的第一个边结点开始依次向后指，遍历某顶点元素的所有边结点，并将每个边结点对应的indegree数组单元值自减，当indegree单元值为0时，将该边结点邻接点域进栈
   5：最后将m和有向图顶点比较，若两者相等，则该图是有向无环图。
   （3）代码函数：

Status TopologicalSort(ALGraph G, int topo[]) {
	//有向图G采用邻接表存储结构
	//若G无回路，则生成G的一个拓扑排序topo[]并返回OK，否则ERROR
	FindInDegree(G, indegree);//求出各结点的入度存入数组indegree中
	SqStack S;
	InitStack(S);//初始化栈
	for (int i = 0; i < G.vexnum; i++) {
		if (!indegree[i]) Push(S, i);//入度为0者进栈
	}
	int m = 0;//对输出顶点计数u，初始为0
	while (!StackEmpty(S)) {
		int i = 0;
		Pop(S, i);//将栈顶顶点vi出栈
		topo[m] = i;//将vi保存在拓扑序列数组topo中
		++m;//对输出顶点计数
		ArcNode* p = new ArcNode;
		p = G.vertices[i].firstarc;//p指向vi的第一个邻接点
		while (p != NULL) {
			int k = p->adjvex;//vk为vi的邻接点
			--indegree[k];//vi的每个邻接点的入度减一
			if (indegree[k] == 0) Push(S, k);//若入度减为0，则入栈
			p = p->nextarc;//p指向顶点vi下一个邻接结点
		}
	}
	if (m < G.vexnum) return ERROR;//该有向图有回路
	else return OK;
}

6. 逆拓扑排序：每次选择出度为0的顶点
7. 不同存储结构的时间复杂度问题
8. 逆邻接表
9. 王道综合题9
10. 有环的图是不存在逆拓扑排序的 ，因此可以用来回路识别
11. 逆拓扑排序用DFS算法实现：

int visited[MAX];//设置一个数组，判断是否遍历过，false/1为遍历过
void DFGTraverse(Graph G,int v)
{
    for(v=0;v<G.vexnum;v++)
       visited[v]=0;//初始化判断数组
    for(v=0;v<G.vexnum;v++)
    {
        if(!visited[v])//如果没有遍历过
            DFS(G,V);//进行遍历
    }
}
void DFS(Graph G,int v)//进行递归遍历
{
    visited[v]=1;printf(v);//改变判断数组，输出点
    for(w=FirstVex(G,v);w!=0;w=NextVex(G,v))//从每一行第一个邻接矩阵值为1的，跳转到下一个值为1的
    {
        if(!visited[w])
            DFS(G,v);
    }
    printf(v);//不一样的地方
}

五、关键路径

1. AOE网：以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间）称之为用边表示活动的网络，简称AOE网。
2. 性质：
   （1）只有某个顶点所代表的事件发生以后，从该顶点处罚的各有向边所代表的活动才可以开始。
   （2）只有进行某个顶点的各有向边所代表的活动都已经结束时，该顶点所代表的的事件才能发生。另外，有些活动是可以并行进行的。
   （3）只有一个入度为0的顶点，称为开始顶点（源点），表示整个工程的开始；也仅有一个顶点出度为0的顶点，称为结束顶点（汇点），表示整个工程的结束。
   （4）从源点到汇点的邮箱路径可能有多条，所有路径中，具有最大路径长度称为关键路径，而把关键路径上的活动称为关键路径。完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
3. 事件vk最早发生时间(ve(k))：决定了所有从vk开始的活动能够开工的最早时间。
4. 活动ak的最早开始时间(e(i))：指该活动弧的起点所代表的的事件的最早发生时间。
5. 事件vk的最迟发生时间(vi(k))：是指在不推迟整个工期完成的前提下，该事件最迟必须发生的时间。
6. 活动ai的最早开始时间(l(i)):是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
7. 关键路径上，活动最早开始时间=活动最迟开始时间
8. 活动ai的时间余量d(i)=l(i)-e(i)：表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间，若一个活动的时间余量为0，则说明这个故活动属于关键活动，由关键活动组成的路径就是关键路径。
9. 缩短关键活动时间，则可以缩短整个工程的工期。当缩短到一定程度，关键活动就可能会变成非关键活动。因此并不是关键活动时间不断压缩，一定可以减少时间。
10. 可能存在多条关键路径，只提高一条关键路径上的关键活动的速度并不能缩短整个工程的工期，只有加快那些包含在所有关键路径上的关键活动才能达到缩短工期的目的。
11. 例题：