文章

15

粉丝

0

获赞

6

访问

860

头像
【2024年】408计算机统考真题模拟考试 - 第41题答案笔记
数据结构
发布于2025年5月6日 22:26
阅读数 25

计算机考研408统考历年真题及答案解析

(1) 首先由题意可得,G一定是一个AOV网,因此一定有拓扑序列;若G中某个顶点的入度或出度>1,那么G中就不存在唯一的拓扑序列,又因为G是用邻接矩阵存储的,故可以检查每个顶点的入度与出度,若某个值大于1,则返回0;全部检查完也没有找到入度与出度大于1的,则返回1。时间复杂度为O(|V|^2)与空间复杂度为O(1)。
(2)
// 算法主体
int solution(MGraph G) {
    // 遍历每个顶点,以获取其入度与出度
    for (int i = 0; i < G.numVertices; i++) {
        int inDegree = 0, outDegree = 0;    // 顶点i的入度与出度
        for (int j = 0; j < G.numVertices; j++) {
             if (G.Edge[j][i] == 1) {    // j到i有一条有向边,入度+1
                 inDegree++; 
                 if (inDegree > 1)    // 如果入度 > 1,则返回0

                      return 0;
             }
             if (G.Edge[i][j] == 1) {   // i到j有...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发