2023年10月26日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航_

[数据结构 P2026] 2023年10月26日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航

学习人数: 486

正确率: 100%

题目描述

未通过

2023年10月26日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导工程。以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已如有向图G采用邻接矩阵存储，类型定义如下：

typedef struct //图的类型定义
{
    int numVertices, numEdges; //图的顶点数和有向边数
    char verticesList[MAXV]; //项点表，MAXV为以定义常量
    int Edge[MAXV][MAXV]; //知接矩阵
}MGraph;

请设计算法：int uniquely(MGraph G)。判定G是否存在唯一的拓扑序列，若是则返回1，否则返回0。
要求:
（1）给出算法的基本设计思想（4分）

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释（9分）

上一题

下一题

加入错题本

个人笔记

已有1条笔记

登录后提交答案

1 个回答 (点击展开回答)

jiuquv

2024年6月18日 01:25

#include<iostream>
#include<queue>
#include<vector>
#include<unordered_map>
using namespace std;

int uniquely(MGraph G) {
int n = G.numVertices;
vector<int> inDegree(n, 0);
unordered_map<int, vector<int>> umap;
queue<int> que;
vector<int> res;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (G.Edge[i][j] != 0) {
inDegree[G.VerticesList[j]]++;
umap[i].push_back(j);
}
}
}
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
int cur = que.front();
que.pop();
res.push_back(cur);
vector<int> next = umap[cur];
if (next.size() != 1) {
return 0;
} else {
inDegree[next[0]]--;
}
if (inDegree[next[0]] == 0) {
que.push(next[0]);
}
}
if (res.size() != n) {
return 0;
} else {
return 1;
}
}

参考答案

答案解析

（1）初始化：首先...

用户登录可进行刷题及查看答案

答案解析

（1）初始化：首先，我们需要一个数组来存储每个顶点的入度。我们遍历邻接矩阵，计算每个顶点的入度
初始一个计数器作为变量用于记录有多少个入度为0的节点
遍历每个节点：首先计算每个顶点的入度，然后在每次迭代中找在并移除入度为0的顶点。如果在任何时刻存在多个入度为0的顶点。那么就返回0。表示存在多个有效的拓扑序列。如果成功完成了拓扑排序，那么就返回1，表示存在唯一的拓扑序列。

（2）

int uniquely(MGraph G){
    int inDegree[MAXV]={0};
    // 计算每个顶点的入度
    for(int =0; i<G.numVertices; i++) {
        for(int j=0; j<G.numVertices; j++) {
            if(G.Edge[i][j] != 0)
                inDegree[i]++;
        }
    }
    // 对每个顶点进行处理
    for(int =0; i<G.numVertices; i++) {
        int zeroInDegreeCount = 0; // 入度为0的顶点数量
        int zeroInDegreeIndex = -1; // 入度为0的顶点索引
        // 找到入度为0的顶点
        for(int j=0; j<G.numVertices; j++) {
            if(inDegree[j] == 0) {
                zeroInDegreeCount++;
                zeroInDegreeIndex = j;
            }
        }
        // 如果存在多个入度为0的顶点，则返回0
        if(zeroInDegreeCount > 1) {
            return 0;
        }
        // 如果没有找到入度为0的顶点，则返回0
        if(zeroInDegreeCount == 0) {
            return 0;
        }
        // 将找到的入度为0的顶点从图中移除
        inDegree[zeroInDegreeIndex] = -1;
        for(int j=0; j<G.numVertices; j++) {
            if(G.Edge[zeroInDegreeIndex][j] == 1) {
                inDegree[j]--;
            }
        }
    }
    // 如果成功完成了拓扑排序，则返回1
    return 1;
}