目录

一、最小生成树

二、最短路径

三、有向⽆环图描述表达式

四、拓扑排序

五、关键路径

一、最小生成树

1、最小生成树的概念

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

• 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
• 最小生成树的边数 =顶点数 -1。砍掉一条则不连通，增加一条边则会出现回路。
• 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。
• 只有连通图才有生成树，非连通图只有生成森林。

2、求最小生成树的两种方法

• Prim算法
• Kruskal算法 

Prim算法(普里姆)：从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。时间复杂度: O(V2)适合用于边稠密图

Kruskal算法(克鲁斯卡尔)：每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)直到所有结点都连通。时间复杂度: O(lEllog2lEl )适合用于边稀疏图

二、最短路径

1.无权图的单源最短路径问题——BFS算法

使用 BFS算法求无权图的最短路径问题，需要使用三个数组

• d[]数组用于记录顶点 u 到其他顶点的最短路径。
• path[]数组用于记录最短路径从那个顶点过来。
• visited[]数组用于记录是否被访问过。

代码时间

#define MAX_LENGTH 2147483647			//地图中最大距离，表示正无穷// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){for(i=0; i=0;w=NextNeighbor(G,u,w)){if(!visited[w]){d[w]=d[u]+1;path[w]=u;visited[w]=TREE;EnQueue(Q,w);			//顶点w入队}}}
}

2.单源最短路径问题——Dijkstra算法

1. BFS算法的局限性：BFS算法求单源最短路径只适⽤于⽆权图，或所有边的权值都相同的图。
2. Dijkstra算法能够很好的处理带权图的单源最短路径问题，但不适⽤于有负权值的带权图。
3. 使用 Dijkstra算法求最短路径问题，需要使用三个数组：

• final[]数组用于标记各顶点是否已找到最短路径。
• dist[]数组用于记录各顶点到源顶点的最短路径长度。
• path[]数组用于记录各顶点现在最短路径上的前驱。

代码实现

#define MAX_LENGTH = 2147483647;// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){for(int i=0; idist[v]+G.edge[v][j]){dist[j] = dist[v]+G.edge[v][j];path[j] = v;}}}
}

3.各顶点间的最短路径问题——Floyd算法

1. Floyd算法：求出每⼀对顶点之间的最短路径，使⽤动态规划思想，将问题的求解分为多个阶段。

2. Floyd算法可以⽤于负权值带权图，但是不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径。

3. Floyd算法使用到两个矩阵：

   1. dist[][]：目前各顶点间的最短路径。
   2. path[][]：两个顶点之间的中转点。

4. 代码实现：

int dist[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];void Floyd(MGraph G){int i,j,k;// 初始化部分for(i=0;idist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}}}}
}

4.最短路径算法比较：

三、有向⽆环图描述表达式

1.有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称 DAG图（Directed Acyclic Graph）。

DAG描述表达式：((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

2.有向无环图描述表达式的解题步骤：

• Step 1:把各个操作数不重复地排成一排
• Step 2:标出各个运算符的生效顺序 (先后顺序有点出入无所谓)
• Step 3:按顺序加入运算符，注意“分层”
• Step 4:从底向上逐层检查同层的运算符是否可以合体

四、拓扑排序

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

2.拓扑排序：在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：

• 每个顶点出现且只出现⼀次；
• 若顶点 A 在序列中排在顶点 B 的前⾯，则在图中不存在从顶点 B 到顶点 A 的路径。
• 或定义为：拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后⾯。每个 AOV ⽹都有⼀个或多个拓扑排序序列。
   

3.拓扑排序的实现:

• 从AoV网中选择一个没有前驱 (入度为0) 的顶点并输出
• 从网中删除该顶点和所有以它为起点的有向边。
• 重复D和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止

4.代码实现拓扑排序（邻接表实现）：

#define MaxVertexNum 100			//图中顶点数目最大值typedef struct ArcNode{				//边表结点int adjvex;						//该弧所指向的顶点位置struct ArcNode *nextarc;		//指向下一条弧的指针
}ArcNode;typedef struct VNode{				//顶点表结点VertexType data;				//顶点信息ArcNode *firstarc;				//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];typedef struct{AdjList vertices;				//邻接表int vexnum,arcnum;				//图的顶点数和弧数
}Graph;								//Graph是以邻接表存储的图类型// 对图G进行拓扑排序
bool TopologicalSort(Graph G){InitStack(S);					//初始化栈，存储入度为0的顶点for(int i=0;inextarc){//将所有i指向的顶点的入度减1，并将入度为0的顶点压入栈v=p->adjvex;if(!(--indegree[v]))Push(S,v);			//入度为0，则入栈}}if(count