文章

130

粉丝

0

获赞

0

访问

6.1k

头像
2024年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年8月14日 22:48
阅读数 104

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) { /...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发