文章
363
粉丝
0
获赞
0
访问
73.7k
(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]; // 存储...
登录后发布评论
暂无评论,来抢沙发