文章

363

粉丝

0

获赞

0

访问

73.7k

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

(1)算法的基本设计思想
要判定有向图是否存在唯一拓扑序列,核心思路基于拓扑排序的核心逻辑(Kahn 算法) ,关键在于监控拓扑排序过程中入度为 0 的顶点数量:
拓扑排序的核心原理:拓扑排序要求每次选择入度为 0 的顶点加入序列,删除该顶点及所有出边(对应减少邻接顶点的入度),重复此过程直到所有顶点加入序列(无环)或无入度为 0 的顶点(有环)。
唯一性判定关键:若拓扑排序的每一步都恰好只有 1 个入度为 0 的顶点,则拓扑序列唯一;若存在某一步有 2 个及以上入度为 0 的顶点,说明后续可选路径不唯一,拓扑序列不唯一;若图有环(无法生成包含所有顶点的拓扑序列),则直接返回 0(无有效拓扑序列,更无唯一序列)。
具体步骤设计:
步骤 1:计算所有顶点的入度,存储在入度数组中。
步骤 2:使用队列(或栈)存储初始入度为 0 的顶点,检查初始入度为 0 的顶点数:若为 0(有环)返回 0;若≥2(初始就有多个选择)返回 0。
步骤 3:执行拓扑排序,每次从队列中取出 1 个顶点(因步骤 2 保证初始队列只有 1 个),遍历其所有邻接顶点,减少对应顶点的入度。
步骤 4:每次减少邻接顶点入度后,检查新产生的入度为 0 的顶点数:若≥2,说明当前步骤有多个选择,拓扑序列不唯一,返回 0。
步骤 5:统计拓扑排序中加入序列的顶点数,若不等于总顶点数(有环)返回 0;否则(所有步骤均只有 1 个入度为 0 的顶点)返回 1。

2):

#include <stdio.h>
#include <string.h>
#define MAXV 100  // 假设MAXV为100,可根据实际定义调整

typedef struct {
    int numVertices, numEdges;
    char verticesList[MAXV];
    int Edge[MAXV][MAXV];
} MGraph;

// 判定图G是否存在唯一拓扑序列,是返回1,否则返回0
int uniquely(MGraph G) {
    int inDegree[MAXV];  // 存储...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发