文档介绍：数据结构
DATA STRUCTURE
拓扑排序与关键路径
第九章图
图的基本概念
图的存储结构
图的遍历
拓扑排序与关键路径
最小代价生成树
最短路径
内容提要:
从本节开始讨论图数据结构的应用,包括拓扑排序与关键路径、最小代价生成树和最短路径。
拓扑排序
一、AOV网络
拓扑排序是求解网络问题所需的主要算法,PERT (计划评审技术)和CMP(关键路径法)都要用到。
通常,一个工程(如软件开发、施工、生产流程等)可以分成若干子工程(称为活动)。要完成整个工程,就要完成所有活动。而活动的执行通常有某些先决条件的,即一些活动必须先于另一些活动完成。
用有向图可以表示活动的领先关系。
顶点:表示活动。
有向边:表示先决条件。
AOV网(顶点活动网络):有向图G中,若用顶点代表活动,有向边表示活动之间的领先关系,则称图G为AOV网络。
AOV网络举例:计算机专业学生学习的课程。
课程代号课程名称先修课程
C1 高等数学
C2 C++
C3 离散数学 C1,C2
C4 数据结构 C2,C3
C5 高级语言 C2
C6 编译方法 C4,C5
C7 操作系统 C4,C9
C8 普通物理 C1
C9 计算机原理 C8
C1
C2
C8
C3
C5
C9
C4
C7
C6
AOV网的例子
传递性:活动的领先关系是可以传递的。如C1领先于C8,C8领先于C9,C1也领先于C9。
反自反性:不允许一个活动在开始之前就完成。要求AOV网是一个有向无回路图。
一个拓扑序列是AOV网中顶点的线性序列,使得对图中任意二个顶点i和j,若在网中,i领先于j,则在线性序列中i是j的前驱结点。
用拓扑排序可以做以下两件事情:
(1)测试AOV网的可行性;(是否存在回路)
(2)得到一个拓扑序列。
一个AOV网络的拓扑序列不一定是唯一的!
AOV网中的领先关系是一种拟序关系,即具有传递性和反自反性。
二、拓扑排序算法
拓扑排序算法:
(1)在图中找一个入度为零的顶点,输出之;
(2)从图中删除该顶点及其所有出边;
(3)重复(1)、(2),直到所有顶点都输出,或图中剩下的顶点再也没有入度为零的顶点(存在有向回路)为止。
C1
C2
C8
C3
C5
C9
C4
C7
C6
左图中的两个拓扑序列为:
C1,C2,C3,C4,C5,C8,C9,C7,C6
C1,C8,C9,C2,C5,C3,C4,C7,C6
如按拓扑次序学习课程,能保证学任何课程时,其他先修课均已学过。
注意:
(1)从图中删除一个顶点及其所有出边时,会产生新的入度为0的顶点;
(2)入度为0的顶点的输出次序无关紧要。
因此算法实现时,可以用堆栈或队列保存新产生的入度为0的顶点;
拓扑排序算法要解决以下两个问题:
(1)计算每个顶点的入度;
可以计算每个顶点的直接前驱的个数。
(2)删除一个顶点的所有出边。
将该顶点的邻接点的入度减一。
三、拓扑排序算法的C++程序
拓扑排序算法采用邻接表存储,用InDegree[i]存储顶点i的入度。
(e),。
template <class T>
LinkedGraph<T>::LinkedGraph(int Vertices)
{ n=Vertices;
a=new Enode<T> *[n];
InDegree=new int [n];
for(i=0; i<n; i++)
{ a[i]=NULL;
InDegree[i]=0;
}
}
。
template <class T>
bool LinkedGraph::Add(int u, int v, const T&w)
{ if(u<0||v<0||v>n-1||u==v||Exist(u,v))
{ cerr<<“BadInput”<<endl;
return false;
}
Enode<T> *p=new Enode<T>(v,w,a[u]);
a[u]=p; InDegree[v]++;
e++;
return true;
}
拓扑排序算法:
template <class T>
void LinkedGraph::TopoSort()
{ int i,j,top=-1;
Enode<T> *p;
for(i=0; i<n; i++)
if(!InDegree[i])
{ InDegree[i]=top; top=i; //入度为0的顶点进栈
}