文章

408

粉丝

0

获赞

0

访问

105.8k

头像
2024年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月6日 16:37
阅读数 109

(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...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发