已知有向图 G 采用邻接矩阵存储，类型定义如下：_

[数据结构 P2012] 已知有向图 G 采用邻接矩阵存储，类型定义如下：

学习人数: 734

正确率: ??%

题目描述

未通过

已知有向图 G 采用邻接矩阵存储，类型定义如下：

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

将图中出度大于入度的顶点称为 K 顶点。例如在题41图中，顶点 a 和 b 都是 K 顶点。

设计算法 int printVertices(MGraph G)对给定任意非空有向图 G，输出 G 中所有 K 顶点的算法，并返回 K 顶点的个数。

(1)给出算法的设计思想。

(2)根据算法思想，写出 C/C++描述，并注释。

上一题

下一题

加入错题本

个人笔记

已有1条笔记

登录后提交答案

暂无评论，来抢沙发

参考答案

解答：

⑴

⑵...

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

解答：

⑴

⑵ 根据上述思路，C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>
#define MAXV 11

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

int printVertices(MGraph G) {
    int indegrees[G.numVertices];
    int outdegrees[G.numVertices];
    memset(indegrees, 0, sizeof(indegrees));
    memset(outdegrees, 0, sizeof(outdegrees));
    // 遍历无向图统计所有点的出度和入度
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            outdegrees[i] += G.Edge[i][j];
            indegrees[j] += G.Edge[i][j];
        }
    }
    int count = 0;
    // 遍历indegrees和outdegrees数组统计出度大于入度的顶点
    for (int i = 0; i < G.numVertices; i++) {
        if (outdegrees[i] > indegrees[i]) {
            printf("%c", G.VerticesList[i]);
            count++;
        }
    }
    return count;
}

int main() {
    MGraph G;
    G.numEdges = 5;
    G.numVertices = 4;
    memset(G.VerticesList, 0, sizeof(G.numVertices));
    char V[4] = {'a', 'b', 'c', 'd'};
    for (int i = 0; i < G.numVertices; i++) {
        G.VerticesList[i] = V[i];
    }
    memset(G.Edge, 0, sizeof(G.numVertices));
    int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            G.Edge[i][j] = M[i][j];
        }
    }
    int count = printVertices(G);
    printf("%d", count);
    return 0;
}

复杂度分析

时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
空间复杂度： O(n) ，开辟了 O(n) 大小的辅助数组。

时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>
#define MAXV 11

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

int printVertices(MGraph G) {
    int count = 0, indegree = 0, outdegree = 0;
    // 遍历无向图统计所有点的出度和入度
    for (int i = 0; i < G.numVertices; i++) {
        indegree = 0;    // i的入度
        outdegree = 0;   // i的出度
        for (int j = 0; j < G.numVertices; j++) {
            outdegree += G.Edge[i][j];
            indegree += G.Edge[j][i];
        }
        if (outdegree > indegree) {
            printf("%c", G.VerticesList[i]);
            count++;
        }
    }
    return count;
}

int main() {
    MGraph G;
    G.numEdges = 5;
    G.numVertices = 4;
    memset(G.VerticesList, 0, sizeof(G.numVertices));
    char V[4] = {'a', 'b', 'c', 'd'};
    for (int i = 0; i < G.numVertices; i++) {
        G.VerticesList[i] = V[i];
    }
    memset(G.Edge, 0, sizeof(G.numVertices));
    int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            G.Edge[i][j] = M[i][j];
        }
    }
    int count = printVertices(G);
    printf("%d", count);
    return 0;
}

复杂度分析

时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
空间复杂度： O(1) ，使用了常数个辅助变量。