程序填空题：关键路径
```c++
#include
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;
int indegree[MVNum];//顶点入度
int ve[BDNum];//事件vi的最早发生时间
int vl[BDNum];//事件vi的最迟发生时间
int topo[MVNum];//记录拓扑序列的顶点序号
int LocateVex(ALGraph G , VerTexType v);//确定点v在G中的位置
int CreateUDG(ALGraph &G);//创建邻接表和逆邻接表
void FindInDegree(ALGraph G,int indegree[]);//求出各顶点的入度存入数组indegree中
int TopologicalOrder(ALGraph G , int topo[]);//生成G的一个拓扑序列topo[]
int CriticalPath(ALGraph G){
int n , i , k , j , e , l,flag=1;
if (!TopologicalOrder(G, topo)) return ERROR;
n = G.vexnum;
for(i = 0; i < n; i++)
ve[i] = 0;
for(i = 0;i < n; i++){
k = topo[i];
ArcNode *p = G.vertices[k].firstarc;
while(p != NULL){
j = p->adjvex;
if(ve[j] < @@[ve[k] + p->weight](2))
ve[j] = @@[ve[k] + p->weight](2);
p = p->nextarc;
}
}
for(i=0;i vl[i]=ve[n-1];
for(i = n - 1;i >= 0; i--){
k = topo[i];
ArcNode *p = G.vertices[k].firstarc;
while(p != NULL){
j = p->adjvex;
if(vl[k] > @@[vl[j] - p->weight](2))
vl[k] = @@[vl[j] - p->weight](2);
p = p->nextarc;
}
}
for(i = 0;i < n; i++){
ArcNode *p = G.vertices[i].firstarc;
while(p != NULL) {
j = p->adjvex;
e = @@[ve[i]](2);
l = @@[vl[j] - p->weight](2);
if(e == l) {
if(flag){
cout << G.vertices[i].data << "->" << G.vertices[j].data;flag=0;
}
else
cout << "," << G.vertices[i].data << "->" << G.vertices[j].data;
}
p = p->nextarc;
}
}
return OK;
}
int main(){
ALGraph G;
CreateUDG(G);
int *topo = new int [G.vexnum];
CriticalPath(G);
return 0;
}
```
答案：
第1空：ve[k] + p->weight
第2空：ve[k] + p->weight
第3空：vl[j] - p->weight
第4空：vl[j] - p->weight
第5空：ve[i]
第6空：vl[j] - p->weight
#include
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;
int indegree[MVNum];//顶点入度
int ve[BDNum];//事件vi的最早发生时间
int vl[BDNum];//事件vi的最迟发生时间
int topo[MVNum];//记录拓扑序列的顶点序号
int LocateVex(ALGraph G , VerTexType v);//确定点v在G中的位置
int CreateUDG(ALGraph &G);//创建邻接表和逆邻接表
void FindInDegree(ALGraph G,int indegree[]);//求出各顶点的入度存入数组indegree中
int TopologicalOrder(ALGraph G , int topo[]);//生成G的一个拓扑序列topo[]
int CriticalPath(ALGraph G){
int n , i , k , j , e , l,flag=1;
if (!TopologicalOrder(G, topo)) return ERROR;
n = G.vexnum;
for(i = 0; i < n; i++)
ve[i] = 0;
for(i = 0;i < n; i++){
k = topo[i];
ArcNode *p = G.vertices[k].firstarc;
while(p != NULL){
j = p->adjvex;
if(ve[j] < @@[ve[k] + p->weight](2))
ve[j] = @@[ve[k] + p->weight](2);
p = p->nextarc;
}
}
for(i=0;i
for(i = n - 1;i >= 0; i--){
k = topo[i];
ArcNode *p = G.vertices[k].firstarc;
while(p != NULL){
j = p->adjvex;
if(vl[k] > @@[vl[j] - p->weight](2))
vl[k] = @@[vl[j] - p->weight](2);
p = p->nextarc;
}
}
for(i = 0;i < n; i++){
ArcNode *p = G.vertices[i].firstarc;
while(p != NULL) {
j = p->adjvex;
e = @@[ve[i]](2);
l = @@[vl[j] - p->weight](2);
if(e == l) {
if(flag){
cout << G.vertices[i].data << "->" << G.vertices[j].data;flag=0;
}
else
cout << "," << G.vertices[i].data << "->" << G.vertices[j].data;
}
p = p->nextarc;
}
}
return OK;
}
int main(){
ALGraph G;
CreateUDG(G);
int *topo = new int [G.vexnum];
CriticalPath(G);
return 0;
}
```
答案：
第1空：ve[k] + p->weight
第2空：ve[k] + p->weight
第3空：vl[j] - p->weight
第4空：vl[j] - p->weight
第5空：ve[i]
第6空：vl[j] - p->weight
