工程中的关键活动和关键路径
#include <iostream> using namespace std; #define MVNum 100 //最大顶点数 #define BDNum MVNum * (MVNum - 1) //最大边数 #define OK 1 #define ERROR 0 typedef char VerTexType; //- - - - -图的邻接表存储表示- - - - - typedef struct ArcNode { int adjvex; int weight; struct ArcNode *nextarc; }ArcNode; typedef struct VNode { VerTexType data; ArcNode *firstarc; }VNode, AdjList[MVNum]; typedef struct { AdjList vertices; //邻接表 AdjList converse_vertices; //逆邻接表 int vexnum, arcnum; //图的当前顶点数和边数 }ALGraph; //- - - - -顺序栈的定义- - - - - typedef struct { int *base; int *top; int stacksize; }spStack; int indegree[MVNum]; //数组indegree存放个顶点的入度 int ve[BDNum]; //事件vi的最早发生时间 int vl[BDNum]; //事件vi的最迟发生时间 int topo[MVNum]; //记录拓扑序列的顶点序号 spStack S; //----------------栈的操作-------------------- void InitStack(spStack &S) { //栈的初始化 S.base = new int[MVNum]; if (!S.base) exit(1); S.top = S.base; S.stacksize = MVNum; } void Push(spStack &S, int i) { //入栈 if (S.top - S.base == S.stacksize) return; *S.top++ = i; } void Pop(spStack &S, int &i) { //出栈 if (S.top == S.base) return; i = *--S.top; } bool StackEmpty(spStack S) { //判断栈是否为空 if (S.top == S.base) return true; return false; } int LocateVex(ALGraph G, VerTexType v) { //确定点v在G中的位置 for (int i = 0; i < G.vexnum; ++i) if (G.vertices[i].data == v) return i; return -1; } int CreateUDG(ALGraph &G) { //创建有向图G的邻接表、逆邻接表 int i, k; cout << "请输入总顶点数:"; cin >> G.vexnum; cout << "请输入弧数："; cin >> G.arcnum; cout << "请依次输入各顶点："; for (i = 0; i < G.vexnum; ++i) { //输入各点，构造表头结点表 cin >> G.vertices[i].data; //输入顶点值 G.converse_vertices[i].data = G.vertices[i].data; //初始化表头结点的指针域为NULL G.vertices[i].firstarc = NULL; G.converse_vertices[i].firstarc = NULL; } cout << "请输入各条弧和对应的权值：" << endl; for (k = 0; k < G.arcnum; ++k) { VerTexType v1, v2; int i, j, w; cin >> v1 >> v2 >> w; i = LocateVex(G, v1); j = LocateVex(G, v2); ArcNode *p1 = new ArcNode; p1->adjvex = j; p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; p1->weight = w; ArcNode *p2 = new ArcNode; p2->adjvex = i; p2->nextarc = G.converse_vertices[j].firstarc; G.converse_vertices[j].firstarc = p2; p2->weight = w; } return OK; } void FindInDegree(ALGraph G) { //求出各顶点的入度存入数组indegree中 int i, count; for (i = 0; i < G.vexnum; i++) { count = 0; ArcNode *p = G.vertices[i].firstarc; if (p) { while (p) { p = p->nextarc; count++; } } indegree[i] = count; } } int TopologicalOrder(ALGraph G, int topo[]) { //有向图G采用邻接表存储结构 //若G无回路，则生成G的一个拓扑序列topo[]并返回OK，否则ERROR int i, m; FindInDegree(G); //求出各顶点的入度存入数组indegree中 InitStack(S); //栈S初始化为空 for (i = 0; i < G.vexnum; ++i) if (!indegree[i]) Push(S, i); //入度为0者进栈 m = 0; //对输出顶点计数，初始为0 while (!StackEmpty(S)) { //栈S非空 Pop(S, i); //将栈顶顶点vi出栈 topo[m] = i; //将vi保存在拓扑序列数组topo中 ++m; //对输出顶点计数 ArcNode *p = G.vertices[i].firstarc; //p指向vi的第一个邻接点 while (p) { int k = p->adjvex; //vk为vi的邻接点 --indegree[k]; //vi的每个邻接点的入度减1 if (indegree[k] == 0) Push(S, k); //若入度减为0，则入栈 p = p->nextarc; //p指向顶点vi下一个邻接结点 } } if (m < G.vexnum) return ERROR; //该有向图有回路 else return OK; } int CriticalPath(ALGraph G) { //G为邻接表存储的有向网，输出G的各项关键活动 int n, i, k, j, e, l; if (!TopologicalOrder(G, topo)) return ERROR; //调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR n = G.vexnum; //n为顶点个数 for (i = 0; i < n; i++) //给每个事件的最早发生时间置初值0 ve[i] = 0; /*――――――――――按拓扑次序求每个事件的最早发生时间－――――－―――――*/ for (i = 0; i < n; i++) { k = topo[i]; //取得拓扑序列中的顶点序号k ArcNode *p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点 while (p != NULL) { //依次更新k的所有邻接顶点的最早发生时间 j = p->adjvex; //j为邻接顶点的序号 if (ve[j] < ve[k] + p->weight) //更新顶点j的最早发生时间ve[j] ve[j] = ve[k] + p->weight; p = p->nextarc; //p指向k的下一个邻接顶点 } } for (i = 0; i<n; i++) //给每个事件的最迟发生时间置初值ve[n-1] vl[i] = ve[n - 1]; /*――――――――――按逆拓扑次序求每个事件的最迟发生时间－――――－―――――*/ for (i = n - 1; i >= 0; i--) { k = topo[i]; //取得拓扑序列中的顶点序号k ArcNode *p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点 while (p != NULL) { //根据k的邻接点，更新k的最迟发生时间 j = p->adjvex; //j为邻接顶点的序号 if (vl[k] > vl[j] - p->weight) //更新顶点k的最迟发生时间vl[k] vl[k] = vl[j] - p->weight; p = p->nextarc; //p指向k的下一个邻接顶点 } } /*――――――――――――判断每一活动是否为关键活动－――――――－―――――*/ cout << "关键路径为:" << endl; for (i = 0; i < n; i++) { //每次循环针对vi为活动开始点的所有活动 ArcNode *p = G.vertices[i].firstarc; //p指向i的第一个邻接顶点 while (p != NULL) { j = p->adjvex; //j为i的邻接顶点的序号 e = ve[i]; //计算活动<vi, vj>的最早开始时间 l = vl[j] - p->weight; //计算活动<vi, vj>的最迟开始时间 if (e == l) //若为关键活动，则输出<vi, vj> cout << G.vertices[i].data << G.vertices[j].data << " "; p = p->nextarc; //p指向i的下一个邻接顶点 } } return OK; } int main() { ALGraph G; CreateUDG(G); if (!CriticalPath(G)) cout << "网中存在环，无法进行拓扑排序！" << endl; return OK; }