数据结构——关键路径AOV（图）

在一个有向图中，顶点表示事件，有向边表示活动，边上的权值表示活动的持续时间。

关键路径：活动的持续时间又称为路径长度，把源点到终点的具有最大长度的路径叫为关键路径。

关键路径又可以理解为同一个层次的事件，所占用的最大时间，那么关键路径必然经过这个事件。

活动的最晚开始时间和最晚开始时间相等，那么该活动就是关键活动，活动的路径就是关键路径

etv：事件最早发生时间
ltv：事件最晚发生时间
ete：活动最早开始时间
lte：活动最晚开始时间

etv是求该事件最早发生的时间，实际上就是求之前路径的最大权值之和
因为只有所有事件都发生了，下面一个事件才能开始发生，也就是事件的最早开始时间

而ltv是求事件最晚发生时间，就是只要那个大事件还未结束，它在它本身的边权值上时间之前发生即可，是倒着推时间减去对应的边权值

活动的最晚发生时间lte：就是在该事件最晚发生，减去该边的持续时间
活动最早发生时间：就是该事件最早发生时。

当活动最早发生时间和活动最晚发生时间相等时，该活动所在的弧就是关键路径。

#include<iostream>
using namespace std;
#define MAX 25

typedef char Vertype;
typedef int Edgetype;
typedef int Status;

//构造图的有向图的邻接表结构体
typedef struct EdgeNode//边表结点  存放每个顶点的邻接点
{
	int adjvex;//边表下标
	Edgetype weight;//边表权重  若边不存在时即无NULL
	struct EdgeNode *next;//指向下一个邻接点
}EdgeNode;

typedef struct VerNode//顶点表   存放顶点
{
	int in;
	Vertype data;//顶点元素
	EdgeNode *firstedge;
}VerNode, AdjList[MAX];//邻接表的 顶点元素 和指向邻点的指针

typedef struct
{
	AdjList adjList;//邻接表
	int numVer, numEdge;//顶点数目和边的数目
}GraphAdjList;

//构造两个栈
typedef struct Stack
{
	int data[MAX];
	//int pop;
}SqStack;

//生成邻接表
Status CreatGraph(GraphAdjList &G)
{
	int i, j, k;
	Edgetype w;
	EdgeNode *e;
	cout << "Enter the number of vertices :" << endl;
	cin >> G.numVer;
	cout << "Enter the number of Edges :" << endl;
	cin >> G.numEdge;

	cout << "Input vertex content :" << endl;
	for (i = 0; i < G.numVer; i++)
	{
		cin >> G.adjList[i].data;//输入顶点元素
		G.adjList[i].in = 0;
		G.adjList[i].firstedge = NULL;//初始化邻边表为NULL；
	}

	for (k = 0; k < G.numEdge; k++)
	{
		cout << "Enter the vertex number of the edge (Vi->Vj)" << endl;
		cin >> i;
		cin >> j;

		cout << "Enter the weight of edge" << i << "-" << j << endl;
		cin >> w;
		e = new EdgeNode;//将两个顶点相结即可。
		e->adjvex = j;// 邻接序号为j
		e->next = G.adjList[i].firstedge;//i的第一个邻接指针 为e的指针
		e->weight = w;
		G.adjList[i].firstedge = e;
		G.adjList[j].in++;

		//有向图则只有生成一次即可
		/*
		e = new EdgeNode;
		e->adjvex = i;//无向图 重复一遍
		e->next = G.adjList[j].firstedge;
		G.adjList[j].firstedge = e;
		e->weight = w;*/
	}
	return 0;
}


SqStack *etv, *stack2;
SqStack *ltv;/*事件最晚发生时间*/
int top2;
//拓扑排序
Status TOpologicalSort(GraphAdjList &G)
{
	EdgeNode *e;
	//SqStack Q;
	int i, j, k, gettop;
	int top = 0;
	int count = 0;

	SqStack *Q;
	Q = new SqStack;
	for (i = 0; i < G.numVer; i++)
	{
		if (G.adjList[i].in == 0)
			Q->data[++top] = i;//存放入度为0的顶点
	}

	top2 = 0;/*初始化 事件最早发生的时间为0*/
	//SqStack *etv,*stack2;
	etv = new SqStack;
	for (i = 0; i < G.numVer; i++)
	{
		etv->data[i] = 0;
	}

	stack2 = new SqStack;
	while (top != 0)
	{
		gettop = Q->data[top--];//弹出入度为0的下标
		stack2->data[++top2] = gettop;//按照拓扑顺序保存弹出顶点下标
		count++;//统计拓扑网顶点数目

		//后面输出其边顶点
		//并删除边，使得边顶点入度-1
		for (e = G.adjList[gettop].firstedge; e; e = e->next)
		{
			j = e->adjvex;
			if (!(--G.adjList[j].in))//如果入度为1时  自减后进入循环   如果入度不为1，自减后 相当于边的数目减1
			{
				Q->data[++top] = j;//保存后续入度为0的顶点
			}

			/**/
			if ((etv->data[gettop] + e->weight) > etv->data[j])
			{
				etv->data[j] = etv->data[gettop] + e->weight;//保存权值   etv初始化都为0，
			}
		}
	}
	if (count < G.numVer)
	{
		cout << "不是一个网图" << endl;
		return 1;
	}
	else
	{
		cout << "是一个网图" << endl;
		return 0;
	}
	//return 0;

}

Status CriticalPath(GraphAdjList &G)
{
	EdgeNode *e;
	int i, j, k, gettop;
	int ete, lte;/*活动最早发生时间ele  活动最迟发生时间lte*/
	
	
	ltv = new SqStack;
	/*初始化ltv*/
	for (i = 0; i < G.numVer; i++)
	{
		ltv->data[i] = etv->data[G.numVer - 1];
	}
	while (top2 != 0)
	{
		gettop = stack2->data[top2--];
		for (e = G.adjList[gettop].firstedge; e; e = e->next)
		{
			k = e->adjvex;
			if (ltv->data[k] - e->weight < ltv->data[gettop])
			{
				ltv->data[gettop] = ltv->data[k] - e->weight;
			}
		}
	}
	for (j = 0; j < G.numVer; j++)
	{
		for (e = G.adjList[j].firstedge; e; e = e->next)
		{
			k = e->adjvex;
			ete = etv->data[j];
			lte = ltv->data[k] - e->weight;
			if (ete == lte)
			{
				cout <<G.adjList[j].data<<G.adjList[k].data<<e->weight << endl;
			}
		}
	}
	return 0;
}

int main()
{
	GraphAdjList G;
	CreatGraph(G);
	TOpologicalSort(G);
	CriticalPath(G);
	system("pause");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199