文章
408
粉丝
0
获赞
0
访问
105.8k
(1)算法的基本设计思想(4 分)
要判定有向图是否存在唯一拓扑序列,核心思路基于拓扑排序的特性:拓扑排序的本质是每次选择入度为 0 的顶点加入序列,若存在唯一拓扑序列,则在排序的每一步都只能有且仅有一个入度为 0 的顶点(若某一步有多个入度为 0 的顶点,选择不同顶点会产生不同拓扑序列;若无法完成拓扑排序,说明图有环,更无唯一拓扑序列)。
具体设计思想如下:
初始化入度数组:遍历邻接矩阵,计算每个顶点的入度(入度为邻接矩阵中对应列的 1 的个数)。
使用队列存储入度为 0 的顶点:初始时将所有入度为 0 的顶点入队,若初始队列中顶点数≠1,直接返回 0(第一步就有多个选择,拓扑序列不唯一)。
拓扑排序核心过程:
每次从队列中出队一个顶点(因队列始终只有 1 个元素,无需选择),加入拓扑序列。
遍历该顶点的所有邻接顶点(邻接矩阵中对应行的 1 的位置),将邻接顶点的入度减 1。
若邻接顶点入度减为 0,将其入队。此时需判断队列大小:若队列大小 > 1,说明当前步有多个选择,拓扑序列不唯一,返回 0;若队列大小 = 0 且未遍历完所有顶点,说明图有环,返回 0。
验证拓扑序列完整性:若拓扑序列长度等于顶点数,且每一步都只有一个入度为 0 的顶点,则返回 1(唯一拓扑序列);否则返回 0。
(2)C 语言描述算法(9 分)
c
运行
#include <stdio.h>
#include <string.h>
#define MAXV 100 // 假设MAXV为100,可根据实际定义调整
typedef struct {
int numVertices, numEdges;
char verticesList[MAXV];
int Edge[MAXV][MAXV];
} MGraph;
int uniquely(MGraph G) {
int inDegree[MAXV]; // 存储每个顶点的入度
int queue[MAXV], front = 0, rear = 0; // 队列:存储入度为0的顶点,模拟队列(数组实现)
&nb...
登录后发布评论
暂无评论,来抢沙发