|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 图的相关算法 >
|
相关知识点:5个
|
|
|
|
|
在工程领域,一个大的工程项目通常被划分为许多较小的子工程(称为活动),当这些子工程都完成时,整个工程也就完成了。若以顶点表示活动,用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网(Activity On Vertex network,AOV网)。在有向网中,若从顶点νi到顶点νj有一条有向路径,则顶点νi是νj的前驱,顶点νj是νi的后继。若<νi,νj>是网中的一条弧,则顶点νi是νj的直接前驱,顶点νj是νi的直接后继。AOV网中的弧表示了活动之间的优先关系,也可以说是一种活动进行时的制约关系。
|
|
|
在AOV网中不应出现有向环,若存在的话,则意味着某项活动必须以自身任务的完成为先决条件,显然这是荒谬的。因此,若要检测一个工程划分后是否可行,首先就应检查对应的AOV网是否存在回路。检测的方法是对其AOV网进行拓扑排序。
|
|
|
|
拓扑排序是将AOV网中所有顶点排成一个线性序列的过程,并且该序列满足:若在AOV网中从顶点νi到νj有一条路径,则在该线性序列中,顶点νi必然在顶点νj之前。
|
|
|
一般情况下,假设AOV网代表一个工程计划,则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。对AOV网进行拓扑排序的方法如下:
|
|
|
(1)在AOV网中选择一个入度为零(没有前驱)的顶点且输出它;
|
|
|
|
(3)重复上述两步,直至网中不存在入度为零的顶点为止。
|
|
|
按照上述步骤进行拓扑排序的过程如下图所示,得到的拓扑序列为6,1,4,3,2,5。显然,对有向图进行拓扑排序所产生的拓扑序列有可能是多种。
|
|
|
|
|
执行的结果会有两种情况:一种是所有顶点已输出,此时整个拓扑排序完成,说明网中不存在回路;另一种是尚有未输出的顶点,剩余的顶点均有前驱顶点,表明网中存在回路,拓扑排序无法进行下去。
|
|
|