数据结构-图的应用-拓扑排序与关键路径（类C语言版）

• 有向无环图
• • AOV网：拓扑排序
  • • 拓扑排序例：排课表
    • AOV网的特点
    • 拓扑排序的方法
    • 检测AOV网中是否存在环方法
  • AOE网：关键路径
  • • 求关键路径

无环的有向图，简称DAG图（Directed Acycline Graph）。

有向无环图常用来描述一个工程或系统的进行过程。（通常把计划、施工、生产、程序流程等当成是一个工程）。
一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成。

用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网（Activity On Vertex network）。
在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧存在，则在这个序列中，i 一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

• 若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。
• 若是网中有向边，则 i 是 j 的直接前驱；j 是 i 的直接后继。
• AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

• 在有向图中选一个没有前驱的顶点且输出之。
• 从图中删除该顶点和所有以它为尾的弧。
• 重复上述两部，直至全部顶点均已输出；或者当图中不存在无前驱的顶点位置。
  

Status TopologicalSort(ALGraph G,int topo[]) 
{	// 有向图G采用邻接表存储结构
	// 若 G 无回路，则生成 G 的一个拓扑序列 topo[]并返回 OK, 否则 ERROR
	FindinDegree(G,indegree); 			// 求出各顶点的入度存入数组 indegree中
	InitStack(S); 						// 栈 s初始化为空
	for(i=O;i
		Pop(S, i); 						// 将栈顶顶点Vi出栈
		topo[m]=i; 						// 将Vi保存在拓扑序列数组 topo中
		++m; 							// 对输出顶点计数
		p=G.vertices[i].firstarc; 		// p指向Vi的第一个邻接点
		while (p! =NULL) 
		{ 
			k=p->adjvex;				// vk为vi 的邻接点
			--indegree[k];				// vi的每个邻接点的入度减1
			if(indegree[k]==O) Push(S,k); 	// 若入度减为0, 则入栈
			p=p->nextarc; 				// p指向顶点Vi下一个邻接结点
		}
	}
	if(m 
检测AOV网中是否存在环方法 
对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。
 
AOE网：关键路径 
用一个有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网（Activity On Edge）。
把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。事件表示在它之前的活动已经完成，在它之后的活动可以开始。
 
 
求关键路径