数据结构课程设计关键路径

由天下分享时间：2025/1/30 17:28:53 加入收藏我要投稿点赞

数学与计算机学院课程设计说明书

课程名称: 数据结构课程设计课程代码:

题目: 有向图的关键路径年级/专业/班: 学生姓名: 学号: 开始时间: 年月日完成时间: 年月日课程设计成绩：

学习态度及平技术水平与实时成绩（30）际能力（20）创新（5）说明书（计算书、图纸、总分分析报告）撰写质量（45）（100）指导教师签名：年月日

引言?????????????????????????????1 1 需求分析??????????????????????????

xxxx（X代表你的课程设计题目名称，宋体，5号字）

2 概要设计?????????????????????????? 3详细设计?????????????????????????? 4调试分析?????????????????????????? 5用户使用说明???????????????????????? 6测试结果?????????????????????????? 7结论??????????????????????????? 致谢????????????????????????????? 参考文献???????????????????????????

摘要

随着计算机的普及，计算机在各行各业中的应用中越来越广泛，在实际工程

中也会用到，有时候会根据实际情况要求缩短工期，这时我们就要清楚那些是影响工程进度的非常关键的环节，于是就可以利用AOE网，计算完成整个工程预计

xxxx（X代表你的课程设计题目名称，宋体，5号字）

需要多少时间，并找出影响工程进度的“关键活动”,从而为决策者提供修改各活动的预计进度的依据。

关键词：有向图关键路径拓扑排序

1 需求分析 1.1任务与分析

言

引 xxxx（X代表你的课程设计题目名称，宋体，5号字）

一、设计题目

有向图的关键路径

二、主要内容

从键盘上输入带权有向图的各顶点和弧上的权值，要求完成下列运算： 1）以邻接表存储该有向图； 2）输出该有向图的各顶点和弧； 3）计算各顶点的入度；

4）如果该有向图的弧表示活动，权表示活动持续的时间（活动和时间用户自行定义），请编程计算出该AOE网的关键路径。

1.2测试数据

第一组： 6 6

1 2 3 4 5 6 1 3 1 2 3 2 3 4 3 3 5 4 4 6 5 5 6 6 第二组: 9 11

a b c d e f g h i a b 6 a c 4 a d 5

xxxx（X代表你的课程设计题目名称，宋体，5号字）

b e 1 c e 1 d h 2 e f 9 e g 7 h i 4 g i 4 f i 2

第三组： 7 10

v1 v2 v3 v4 v5 v6 v7 v1 v2 3 v1 v4 6 v1 v3 2 v2 v5 4 v4 v5 1 v2 v4 2 v3 v4 1 v3 v6 3 v6 v7 4 v5 v7 3 第四组:

xxxx（X代表你的课程设计题目名称，宋体，5号字）

6 6

v1 v2 v3 v4 v5 v6 v1 v3 1 v2 v3 2 v4 v3 3 v3 v5 4 v5 v4 5 v5 v6 6 第五组: 1 3 1 v1 v2 v3 v1 v2 1

2 概要设计

2.1 ADT描述 ADT Graph{

数据对象v：v 是具有相同特性额数据元素的集合，称为顶点集。数据关系：R＝{VR}

VR={|v,e属于v,表示v到w的弧，谓词p(v,w)定义了弧的意义或信息}

基本操作：

Init(&g):初始化有向图

初始条件：g->n是有向图的顶点个数，g->e是有向图的边数，g->adjlist是存放有向图的顶点和邻接点的指针的数组。

操作结果：g->n,g->e赋值为零，数组中的每一行的指针域都赋值为

xxxx（X代表你的课程设计题目名称，宋体，5号字）

空。

Creat(&g):根据输入信息创建有向图

初始条件：g是初始化后的图。

操作结果：根据输入的信息建立起邻接表存储的有向图。

Empty(g):判断g是否为有向图。

操作结果：如果有向图为空，则返回true，否则返回false。

Output(g):按照邻接表的形式输出有向图

初始条件：有向图g存在且不为空

操作结果: 按照邻接表的形式输出有向图。 Du(g):求有向图中每个顶点的出度。

初始条件：有向图g存在且不为空。操作结果：求出每个顶点的出度，并输出。 Rdu(g):有向图中每个顶点的出度。

初始条件：有向图g存在且不为空

结束条件：求出有向图的中每个顶点的入度。

Topsort(g, u, v):进行拓扑排序求出事件的最早发生时间和最晚发生时间，并确定是否是关键路径。

初始条件：有向图存在并且不为空。

结束条件：求出每个事件的最早发生时间和最晚发生时间，并确定是否是关键路径上的时间。

Path(g,u,v,path,d):遍历关键路径并输出。初始条件：经过拓扑排序之后，关键路径已经。结束条件：输出关键路径。 CriticPath(g):输出有向图的关键路径初始条件：拓扑排序成功。

结束条件：输出有向图的所有关键路径，和总工期。

}

2.2程序模块结构

xxxx（X代表你的课程设计题目名称，宋体，5号字）

主函数新输顶建出点有邻的向接出图表度 2.2.1 结构体定义 typedef struct ArcNode { int adjvex;

struct ArcNode * nextarc; InfroType Infro;

bool flag;

}ArcNode;

typedef struct VNode { Vertex data; int count;

ArcNode *firstarc;

}VNode;

typedef struct Graph {

VNode adjlist[MAXN];

顶输点出的关入键度路

xxxx（X代表你的课程设计题目名称，宋体，5号字）

int n, e;

}Graph;

2.3 各功能模块

void Init(Graph * & g)

g表示有向图，这个函数的作用是初始化有向图g，使有向图顶点数和边数为0，并将邻接表的指针置空。

int Find(Graph * g,Vertex v)

在有向图中找出顶点为v在邻接表的下标。 bool Empty(Graph * g) 判断有向图是否为空。 void Create(Graph * & g)

根据提示信息输入相应的信息，并建立有向图。 void Output(Graph *g) 输出有向图的邻接表的形式 void Du(Graph * g) 求图中各个顶点的出度 void Rdu(Graph *g, int f) 求图中各个顶点的入度

bool Topsort(Graph * g, int &u, int & v)

进行拓扑排序求出事件的最早发生时间和最晚发生时间，并确定是否是关键路径。

void Path(Graph * g,int u, int v,int path[], int d) 输出关键路径

void Print(Graph * g) 输出有向图的顶点和边。 void CriticPath(Graph * g) 输出有向图的关键路径 void Menu() 菜单函数

xxxx（X代表你的课程设计题目名称，宋体，5号字）

3 详细设计

3.1结构体定义

弧的结构体的定义 typedef struct ArcNode { int adjvex;

struct ArcNode * nextarc; InfroType Infro;/*边的权值*/

bool flag;

}ArcNode;

顶点的结构体的定义 typedef struct VNode { Vertex data;

int count;/*结点的入度*/

ArcNode *firstarc;

}VNode; 图的结构体定义 typedef struct Graph { VNode adjlist[MAXN];

int n, e;

}Graph;

3.2 初始化

void Init(Graph * & g) { int i;

g->n = 0;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

g->e = 0;

for(i = 0; i < MAXN; i++) { g->adjlist[i].firstarc = null; g->adjlist [i].count = 0;

}

3.3建立有向图

int Find(Graph * g,Vertex v) { if(Empty(g)) { cout << \图为空.\ return -1;

} int i;

for(i = 0; i < g->n; i++) if(g->adjlist[i].data == v)

return i;

return -1;

}

void Create(Graph * & g) { int i, i1, i2; Vertex v1, v2; InfroType w;

cout << \请输入顶点数和边数: \ cin >> g->n >> g->e;

cout << \请输入顶点：\

xxxx（X代表你的课程设计题目名称，宋体，5号字）

for(i = 0; i < g->n; i++)

cin >> g->adjlist[i].data ;

ArcNode * p; p = null;

cout << \边和权值: \ for(i = 1; i <= g->e; i++) { cin >> v1 >> v2 >> w ; i1 = Find(g, v1); i2 = Find(g, v2);

if( i1 != -1 && i2 != -1) { p = new ArcNode; p->adjvex = i2; p->Infro = w; p->flag = false;

p->nextarc = g->adjlist[i1].firstarc ; g->adjlist [i1].firstarc = p;

}

3.4输出邻接表

void Output(Graph *g)/*按照存储结构输出*/ { if(Empty(g)) { cout << \图为空.\ return;

}

xxxx（X代表你的课程设计题目名称，宋体，5号字）

int i;

cout << \按照邻接表输出为: \for( i = 0; i < g->n; i++) {

cout << g->adjlist [i].data; ArcNode * p;

p = g->adjlist [i].firstarc ; while(p) {

cout << \\<< \<< g->adjlist[p->adjvex ].data << \

<< p->Infro << \ }

}

cout << endl;

p = p->nextarc ;

3.5输出各个顶点的出度

void Du(Graph * g)/*求图中各个顶点的度*/ {

if(Empty(g)) { } int v; int k = 0;

for(v = 0; v < g->n; v++) {

cout << \图为空.\return;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

k = 0; ArcNode * p;

p = g->adjlist[v].firstarc ; while(p) { }

cout << \顶点\<< g->adjlist[v].data << \的出度为: \<< k <

k++;

p = p->nextarc ;

3.6输出各个顶点的入度

void Rdu(Graph *g, int f) {

if(Empty(g)) { } int i; ArcNode * p;

for(i = 0; i <= g->n; i++)

g->adjlist [i].count = 0; cout << \有向图为空.\return;

for(i = 0; i < g->n; i++) {

p = g->adjlist [i].firstarc ; while(p) {

g->adjlist [p->adjvex].count ++;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

p = p->nextarc ;

if(f == 0) {

for(i = 0; i < g->n; i++)

cout << g->adjlist [i].data << \的入度为: \<< g->adjlist

[i].count << endl; }

}

3.7输出关键路径

void CriticPath(Graph * g) {

if(Empty(g)) { }

int infro, v, i; infro = -1; v = -1;

if(Topsort(g, infro, v) == false || infro == -1 || v == -1) { }

Rdu(g, 1);

for(i = 0; i < g->n; i++)

if(g->adjlist [i].count == 0 && g->adjlist [i].firstarc && return ;

cout << \图为空.\return;

g->adjlist [i].firstarc ->Infro == infro)

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

{

memset(visited, 0, sizeof(int) * MAXN); memset(st, 0, sizeof(int) * MAXN); Path(g, i, v, st, -1);

}

4 调试分析

在调试的过程中，遇到过很多的问题，我觉得在这之中的比较具有技术含量的问题就是在求事件的最晚发生的时间时，不知如何着手，然后我翻阅了一些书籍和上网查了一些资料，最后确定采用堆栈的方法，保存拓扑排序的顶点序列，然后根据后进先出的原则，进行求事件的最晚发生世间的计算。另外就是很多的特殊情况需要考虑，比如说有向图含有环，这种情况是要编程加以排除，开始事件有多个，关键路径不只一条等一些很细节的问题。

5 用户使用说明

我的程序是采用菜单的形式，但是这个选项不是随机的，特别是在首次使用的时候，首先要选一”新建有向图”建立有向图，否则其他的选项都会是没有意义的，在输入数据的时候也是要按照规范输入。

6 测试结果

建立有向图

xxxx（X代表你的课程设计题目名称，宋体，5号字）

输出有向图的邻接表的形式

输出有向图中各顶点的出度

xxxx（X代表你的课程设计题目名称，宋体，5号字）

输出有向图的个顶点的入度

输出有向图

xxxx（X代表你的课程设计题目名称，宋体，5号字）

输出关键路径

xxxx（X代表你的课程设计题目名称，宋体，5号字）

结论

通过这次课程设计，我更加的了解并能更加灵活的运用有向图的邻接表的存

储方式进行相关的应用，在我独立编写程序和调试运行的时候，我收获很多，这一个课程设计的题目涉及到我平时不曾掌握的算法，甚至连思维也不是很清新，我是一步步的由易到难，慢慢的去解决我所遇到的问题，最开始的时候编写有向图的建立和求有向图的出度等这些平时比较熟悉的算法，然后去想怎样去求有向图的入度的问题，再然后通过查资料了解到求关键路径需要用到拓扑排序，于是我又慢慢的去学习和理解拓扑排序的基本的思想和算法实现，并在此基础上稍作改进，求出每个事件的最早开始时间，用逆拓扑排序的方法求出每个事件的最迟开始时间。最后利用深度优先的算法思想输出关键路径，在这个过程中遇到过很多的问题，有时候需要反复的修改和测试程序，在编程的过程中，随时会发现新的问题，随时要更改和调试程序。我觉得在调试的过程中，最开始的时候出现有多条关键路径的图但是程序却只输出一条关键路径，我仔细查看程序，发现每个事件的最早开始时间和最迟开始时间是没有问题的，最终确定在采用有向图的深度优先遍历的时候，没有将访问标志数组恢复，所以只能输出一条关键路径修改后，能正确的求出关键路径，在这样的基础上我觉得应该多找一些测试数据来测试一下，于是我在网上找到一个有向图，进行关键路径的测试，结果发现输出了一条错误的关键路径，反复的检查和思考之后，发现这是我算法设计上的一个缺陷，因为我只考虑了点是否在关键路径上，而没有考虑到边，比如说两个点的在关键路径之上，但是他们两个点所组成的弧，假设存在弧，却不一定在关键路径上，因为可能他们可能分属两条关键路径上的点，随后我在弧的结构体中加了一个数据域作为标识判断弧是否在关键路径上，解决了这个问题。

xxxx（X代表你的课程设计题目名称，宋体，5号字）

致谢

xxxx（X代表你的课程设计题目名称，宋体，5号字）

7 附录

#include #include using namespace std; typedef string Vertex;

typedef int InfroType;/*存放权值*/ #define null 0 const int MAXN = 20; typedef struct ArcNode { int adjvex;

struct ArcNode * nextarc; InfroType Infro;

bool flag;

}ArcNode;

typedef struct VNode { Vertex data; int count;

ArcNode *firstarc;

}VNode;

typedef struct Graph { VNode adjlist[MAXN];

int n, e;

}Graph;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

int visited[MAXN]; int ve[MAXN]; int vl[MAXN]; int stack[MAXN]; int st[MAXN]; int tp; int top;

int max(int x, int y) { if( x > y) return x; else return y;

}

int min(int x, int y) { if(x < y)

return x; else return y;

}

void Init(Graph * & g) { int i; g->n = 0; g->e = 0;

for(i = 0; i < MAXN; i++) { g->adjlist[i].firstarc = null;

g->adjlist [i].count = 0; 24

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

bool Empty(Graph * g) { if( g->n == 0 && g->e == 0 )

return true;

else

return false;

}

int Find(Graph * g,Vertex v) { if(Empty(g)) { cout << \图为空.\ return -1;

} int i;

for(i = 0; i < g->n; i++) if(g->adjlist[i].data == v)

return i;

return -1;

}

void Create(Graph * & g) { int i, i1, i2; Vertex v1, v2; InfroType w;

cout << \请输入顶点数和边数: \

cin >> g->n >> g->e; 25

xxxx（X代表你的课程设计题目名称，宋体，5号字）

cout << \请输入顶点：\ for(i = 0; i < g->n; i++)

cin >> g->adjlist[i].data ;

ArcNode * p; p = null;

cout << \边和权值: \ for(i = 1; i <= g->e; i++) { cin >> v1 >> v2 >> w ; i1 = Find(g, v1); i2 = Find(g, v2);

if( i1 != -1 && i2 != -1) { p = new ArcNode; p->adjvex = i2; p->Infro = w; p->flag = false;

p->nextarc = g->adjlist[i1].firstarc ; g->adjlist [i1].firstarc = p;

}

void Output(Graph *g)/*按照存储结构输出*/ { if(Empty(g)) { cout << \图为空.\ return;

}

xxxx（X代表你的课程设计题目名称，宋体，5号字）

int i;

cout << \按照邻接表输出为: \for( i = 0; i < g->n; i++) {

cout << g->adjlist [i].data; ArcNode * p;

p = g->adjlist [i].firstarc ; while(p) {

cout << \\<< \<< g->adjlist[p->adjvex ].data << \

<< p->Infro << \ }

void Du(Graph * g)/*求图中各个顶点的度*/ {

if(Empty(g)) { } int v; int k = 0;

for(v = 0; v < g->n; v++) {

k = 0;

cout << \图为空.\return; }

}

cout << endl;

p = p->nextarc ;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

ArcNode * p;

p = g->adjlist[v].firstarc ; while(p) { }

cout << \顶点\<< g->adjlist[v].data << \的出度为: \<< k <

k++;

p = p->nextarc ;

void Rdu(Graph *g, int f) {

if(Empty(g)) { } int i; ArcNode * p;

for(i = 0; i <= g->n; i++)

g->adjlist [i].count = 0; cout << \有向图为空.\return;

for(i = 0; i < g->n; i++) {

p = g->adjlist [i].firstarc ; while(p) { }

g->adjlist [p->adjvex].count ++; p = p->nextarc ;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

if(f == 0) {

for(i = 0; i < g->n; i++)

cout << g->adjlist [i].data << \的入度为: \<< g->adjlist

[i].count << endl; }

bool Topsort(Graph * g, int &infro, int & v)

/*采用拓扑排序的方法求事件发生的最早时间和最迟时间，并确定最短路径包含的结点*/ {

int stack[MAXN]; }

int st[MAXN]; int tp; int top;

memset(ve, 0, sizeof(int) * MAXN); Rdu(g, 1); top = -1; tp = -1; int i, m, n; ArcNode * p; p = null; infro = 0;

for(i = 0; i < g->n; i++)

if(g->adjlist [i].count == 0) {

if(g->adjlist [i].firstarc && infro < g->adjlist

[i].firstarc ->Infro )

xxxx（X代表你的课程设计题目名称，宋体，5号字）

{ infro = g->adjlist [i].firstarc ->Infro ;

}

m = v;

for(i = 0; i < g->n; i++) if(!g->adjlist [i].firstarc) { if( v == m)

v = i;

else { cout << \结束事件不唯一.\

return false;

}

if(infro == -1) { cout << \没有找到开始事件. \ return false;

}

if(v == -1) { cout << \没有找到结束事件.\ return false;

}

for(i = 0; i <= g->n; i++)

vl[i] = INT_MAX;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

for(i = 0; i < g->n; i++) if(g->adjlist [i].count == 0)

stack[++top] = i;

while( top + 1 ) {

m = stack[top--]; g->adjlist [m].count = -1; st[++tp] = m;

p = g->adjlist [m].firstarc ; while(p) { n = p->adjvex ;

if(g->adjlist [n].count == -1) { cout << \该有向图有环.\ return false ;

}

ve[n] = max(ve[n],ve[m] + p->Infro) ; g->adjlist [n].count --; if(g->adjlist [n].count == 0)

stack[++top] = n;

p = p->nextarc;

}

if(tp < g->n - 1) { cout << \拓扑排序不成功.\ return false;

}

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

else

cout << \拓扑排序成功.\

vl[tp] = ve[tp]; tp--;

while(tp + 1) { }

p = g->adjlist [st[tp]].firstarc ; while(p) { }

p = g->adjlist [st[tp]].firstarc ; while(p) { } tp--;

if(vl[st[tp]] == vl[p->adjvex ] - p->Infro )

p->flag = true;

vl[st[tp]] = min(vl[st[tp]], vl[p->adjvex ] - p->Infro ); p = p->nextarc ;

p = p->nextarc ;

return true;

void Print(Graph * g) {

if(Empty(g)) {

cout << \有向图为空.\

xxxx（X代表你的课程设计题目名称，宋体，5号字）

return;

}

int i;

cout << \有向图的顶点为: \ for(i = 0; i < g->n; i++) { cout << g->adjlist [i].data << \

}

cout << endl;

cout << \弧: \ for(i = 0; i < g->n; i++) { ArcNode *p;

p = g->adjlist[i].firstarc; while(p) {

cout << g->adjlist[i].data << \\[p->adjvex].data << \ p = p->nextarc;

}

void Path(Graph * g,int u, int v,int path[], int d) { int j, i; ArcNode * p; p = null;

visited[u] = 1; << g->adjlist 33

xxxx（X代表你的课程设计题目名称，宋体，5号字）

d++;

path[d] = u;

p = g->adjlist [u].firstarc ; if(u == v) { cout << \关键路径: \

cout << g->adjlist [path[0]].data; for(i = 1; i <= d; i++)

cout << \

cout << \总工期: \

} while(p) { j = p->adjvex ;

if(visited[j] == 0 && vl[j] == ve[j] && p->flag )

Path(g, j, v, path, d); p = p->nextarc ;

}

visited[u] = 0; d--;

}

void CriticPath(Graph * g) { if(Empty(g)) { cout << \图为空.\

return;

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

int infro, v, i; infro = -1; v = -1;

if(Topsort(g, infro, v) == false || infro == -1 || v == -1) { return ;

}

Rdu(g, 1);

for(i = 0; i < g->n; i++)

if(g->adjlist [i].count == 0 && g->adjlist [i].firstarc g->adjlist [i].firstarc ->Infro == infro) { memset(visited, 0, sizeof(int) * MAXN); memset(st, 0, sizeof(int) * MAXN); Path(g, i, v, st, -1);

}

void Menu() { cout << \

有向网的相关操作\

cout << \ 新建有向网-------------------->1\ cout << \ 输出邻接表-------------------->2\ cout << \ 输出各顶点的出度-------------->3\

cout << \ 输出各顶点的入度-------------->4\

cout << \输出有向图的顶点和弧---------->5\ cout << \输出关键路径------------------>6\ cout << \ 退出-------------------------->0\

cout << \请输入...\

&& 35

xxxx（X代表你的课程设计题目名称，宋体，5号字）

}

void main() { Graph * g; g = new Graph; Init(g); int choose; while(1) { Menu(); cin >> choose; switch(choose) {

case 1: Init(g); Create(g); break; case 2: