课程设计：拓扑排序和关键路径
一、 需求分析
创建一个带权的有向网，求拓扑序列，求关键路径。并输出每个事件的最早发生时间 ve 及
v1 最迟发生时间，每个活动的最早开始时间及最迟开始时间，关键活动，给出关键路径。
二、 概要设计
本程序是实现 AOV 网的拓扑排序和 AOE 网的关键路径求法，而在求关键路径过程中又用
到了拓扑排序来判断图中是否存在回路。为了保持图的初始化一致性，虽然在拓扑排序算
法中不需要求边的权值，但关键路径需要。所以在输入图的时候都规定了一种格式：
（v1,v2,w1），表示边（ v1,v2）上的权值为 w1。
在用邻接表当作图的存储结构时，它包括两部分：顺序存储的顶点表和链式存储的边表。
顶点表包括：顶点字段（vertex）存放顶点 vi 信息，指针字段（edgelist）存放与 vi 相关联
的边表的第一个结点位置。边表中每个边结点表示的都是与 vi 关联的边。包括位置字段
（endvex）,权字段（weight）,链字段(nextege)。具体说明如下：
typedef struct edgenode
{ int endvex; /*相邻顶点在顶点表中的下标*/
int weight; /*边的权值*/
struct edgenode *nextedge; /指向下一条弧的指针*/
} EdgeNode,*EdgeList; /*边表中的结点*/
typedef struct
{ int vertex; /*顶点信息*/
EdgeList edgelist; /*指向第一条依附该顶点的弧的指针*/
} VexNode,AdjList[MAX_VEXTEX_NUM]; /*顶点表中的结点*/
typedef struct{
int vexnum; /*图的顶点数*/
int arcnum; /*图的边的个数*/
AdjList vexs; /*顶点表*/
} GraphList; /*图的邻接表表示法*/
三、 详细设计
(1) 初始化图函数 InitGraph( )
这是图转化为计算机可以识别的方式，数据结构用的是邻接表。首先提示输入此图的顶点
个数和边数，格式：（vertexnum,arcnum）.再依次输入所有的边信息：（起点，终点，权
值），程序将自动建立图的邻接表，这是实现下述所有功能的基础。
（2）求出图中所有顶点的入度函数 FindInDegree( )
首先给入度向量赋初值 0，然后对顶点表中的每一个顶点，以此访问与此顶点相关联的边 ，
并令入度自增 1.当遍历所有顶点后，也就求出了所有顶点的入度。
- 1
- 2
前往页