文章
130
粉丝
0
获赞
0
访问
6.1k
1)算法的基本设计思想
要判定有向图 G 是否存在唯一的拓扑序列,需基于拓扑排序的基本原理,并增加对唯一性的判断。核心设计思想如下:
拓扑排序基础:使用 Kahn 算法进行拓扑排序,通过计算各顶点的入度,每次选择入度为 0 的顶点加入拓扑序列,并减少其邻接顶点的入度。
唯一性判断:在拓扑排序过程中,若某一步存在超过 1 个入度为 0 的顶点,则说明存在多种拓扑排序方式(可选择不同顶点作为下一个节点),因此拓扑序列不唯一。
完整性检查:若排序结束后,得到的拓扑序列长度不等于图的顶点数,说明图中存在环,不存在拓扑序列,自然也不满足 “唯一” 条件。
结果判定:只有当拓扑排序过程中每一步都恰好有 1 个入度为 0 的顶点,且最终得到包含所有顶点的拓扑序列时,才返回 1(存在唯一拓扑序列),否则返回 0。
2):
int getVertexIndex(MGraph G, char v) {
for (int i = 0; i < G.numVertices; i++) {
if (G.verticesList[i] == v) {
return i;
}
}
return -1; // 未找到(理论上不会出现)
}
// 初始化各顶点的入度
void initInDegree(MGraph G, int inDegree[]) {
for (int i = 0; i < G.numVertices; i++) {
inDegree[i] = 0;
for (int j = 0; j < G.numVertices; j++) {
if (G.Edge[j][i] == 1) { /...
登录后发布评论
暂无评论,来抢沙发