步骤：
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 步骤：
1. 先进行拓扑排序，得到拓扑序列；
2. 根据拓扑序列，正向计算每个顶点的最早发生时间 ve;
3. 根据拓扑序列反过来逆向计算每个顶点的最迟发生时间 vl;
4. 依次判断每条边 u→v：若某活动的最早时间 ve(u) 等于最迟时间 vl(v)-w(u,v)，则为关键活动。 城村
## 伪代码：
仅供参考，重在理解过程，代码考察概率不大，万一考察也只是考察部分步骤（如已知拓扑序列求关键路径)。
<!-- suspect-code -->
> [!warning] 这段代码需要核对（原文第 218 页）
> OCR 体检未通过：花括号不平衡。扫描件的两栏排版（代码 + 右侧注释）有时会被交错读取，产生看起来合理但语义错误的代码。背之前请对照原文。
void CriticalPath(ALGraph G)
{
int indegree[MAXV] = {0};
int ve[MAXV] = {0};
int vl[MAXV];
int topo[MAXV];
int front = 0, rear = 0;
// 第一步:统计入度
for (int i = 0; i < G.numVertices; i++)
ArcNode *p = G.VerticesList[i].first;
while (p != NULL)
{
p = p->next; indegree[p->adjvex]++; // 考矿
}
}
// 第二步:拓扑排序，并计算每个顶点的最早发生时间 ve
for (int i = 0; i < G.numVertices; i++)
if (indegree[i] == 0)
topo[rear++] = i;
{
int u = topo[front++];
ArcNode *p = G.VerticesList[u].first;
while (p != NULL)
{X
int v = p->adjvex;
if (--indegree[v] == 0)
topo[rear++] = v;
// 更新 ve 值
if (ve[u] + p->weight > ve[v])
ve[v] = ve[u] + p->weight;
p = p->next;
15
}
// 如果 rear < G.numVertices,图中有环，不存在关键路径
if (rear < G.numVertices)
{
输出：图中存在环
} return;
// 第三步：初始化 vl 数组
for (int i = 0; i < G.numVertices; i++)
vl[i] = ve[G.numVertices - 1]; //默认项目总工期
// 第四步:逆拓扑序更新 vl 值
for (int i = G.numVertices - 1; i >= 0; i--)
{
int u = topo[i];
ArcNode *p = G.VerticesList[u].first;
while (p != NULL)
{
int v = p->adjvex;
if (vl[v] - p->weight < vl[u])
p = p->next;
}
}
// 第五步:输出关键活动
for (int u = 0; u < G.numVertices; u++)
{
ArcNode *p = G.VerticesList[u].first;
while (p != NULL)
{
int v = p->adjvex;
int e = ve[u];
int l = vl[v] - p->weight;
if (e == l) // 输出活动<u,v>是关键活动
p = p->next;
}
}
}
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef struct
{
int data;
ArcNode *firstarc;
} VNode;
typedef struct
{
VNode VerticesList[MAXV];
int numVertices, arcnum;
} ALGraph;
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点
struct ArcNode *nextarc; // 指向下一条弧的指针
}ArcNode; //边结点
typedef struct
{
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
}VNode; // 顶点结点
typedef struct
{
VNode VerticesList[MAXV]; // 顶点数组
int numVerticesarcnum; //图的当前顶点数和弧数
}ALGraph;
typedef struct ArcNode
{
int adjvex; // 该弧所指向的顶点
struct ArcNode *nextarc; // 指向下一条弧的指针
}ArcNode; //边结点
typedef struct
{
ArcNode *VerticesList[MAXV]; // 顶点数组
int numVertices, arcnum; //图的当前顶点数和弧数
}ALGraph;
typedef struct ArcNode
{
int ivex, jvex;
struct ArcNode *nextarc;
int weight;
} ArcNode;
typedef struct
{
int data;
ArcNode *firstarc;
} VNode;
typedef struct
{
VNode VerticesList[MAXV];
int numVertices, arcnum;
} ALGraph;
typedef struct {
int numV, numE; // 顶点数和边数
char VerticesList[MAXV]; // 顶点信息
int Edge[MAXV] [MAXV]; //权值矩阵
}MGraph;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef struct
{
int data;
ArcNode *firstarc;
} VNode;
typedef struct
{
VNode VerticesList[MAXV];
int numVertices, arcnum;
} ALGraph;
原资料配图 · 转写内容请回源核验
## 【习题5-7】已知无向图G 类型定义如下：
<!-- verified-by-hand -->
> [!success] 已结合原文第 227 页及 Markdown 上下文人工校对
> VexBox 与 AMLGraph 的左花括号丢失，顶点数与边数变量粘连。
typedef struct EBox
{
int mark;
int ivex, jvex;
struct EBox *ilink, *jlink;
} EBox;
typedef struct VexBox
{
char data;
EBox *firstEdge;
} VexBox;
typedef struct
{
VexBox adjMulList[MAXV];
int numVertices, numEdges;
} AMLGraph;
typedef struct{
int numVertices, numEdges; //图中实际的顶点数和边数
char VerticesList[MAXV]; //顶点表。MAXV为已定义常量
int Edge[MAXV] [MAXV]; //邻接矩阵
}MGraph;
typedef struct
{
int numVertices, numEdges;
char VerticesList[MAXV];
int Edge[MAXV][MAXV];
} MGraph;
原资料配图 · 转写内容请回源核验
G，输出G中所有的Κ顶点，并返回Κ顶点的个数。要求：1）给出算法的基本设计思想。
2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
<!-- page 231 -->
【2024年41题】（13分）2023年10月26日，神舟十七号载人飞船发射取得圆满成功再次彰显了中国航天事业辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G采用邻接矩阵存储，类型定义如下。
typedef struct //图的类型定义
{
int numVertices,numEdges; //图的顶点数和有向边数
char VerticesList[MAXV]; //顶点表，MAXV为已定义常量
int Edge[MAXV] [MAXV]; //邻接矩阵
}MGraph;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef struct
{
int data;
ArcNode *firstarc;
} VNode;
typedef struct
{
VNode VerticesList[MAXV];
int numVertices, arcnum;
} ALGraph;
int OddInDegree(ALGraph G)
{
//1.设置出度数组
int outdegree[MAXV] = {0};
//2.遍历所有顶点和边，统计每个顶点的出度
for (int i = 0; i < G.numVertices; i++)
{
//遍历当前顶点i发出的所有边
ArcNode *p = G.VerticesList[i].firstarc;
while (p != NULL)
{
outdegree[i]++;
p = p->nextarc; // 处理下一条边
}
}
//3.扫描每个顶点，统计出度的顶点数
int count = 0;
for (int i = 0; i < G.numVertices; i++)
if (outdegree[i] % 2 = 1) count++;
return count;
}
typedef struct ArcNode
{
int adjvex; // 该弧所指向的顶点
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode; //边结点
typedef struct
{
int data; //顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
}VNode; // 顶点结点
typedef struct
{
VNode VerticesList[MAXV];// 顶点数组
int numVertices, arcnum; //图的当前顶点数和弧数
}ALGraph;