FC02-找出有向图中所有出度大于入度的顶点（K顶点）¶

有向图 \(G\) 采用邻接矩阵存储，将图中出度大于入度的顶点称为 K 顶点。要求输出 \(G\) 中所有的 K 顶点，并返回 K 顶点的个数。（2023 年统考题）

代码实现¶

C
// 函数 func：找出有向图中所有出度大于入度的顶点（K顶点）
// 参数：G - 邻接矩阵表示的有向图
// 返回值：K顶点的个数
int func(MGraph G) {
    int count = 0; // 用于记录K顶点的个数

    // 遍历图中的每个顶点
    for (int i = 0; i < G.numver; i++) {
        int indegree = 0, outdegree = 0; // 初始化入度和出度为0

        // 计算顶点i的入度和出度
        for (int j = 0; j < G.numver; j++) {
            outdegree += G.Edge[i][j]; // 累加第i行的值，得到顶点i的出度
            indegree += G.Edge[j][i];  // 累加第i列的值，得到顶点i的入度
        }

        // 判断是否为K顶点（出度大于入度）
        if (outdegree > indegree) {
            printf("%c ", G.verticle[i]); // 输出K顶点
            count++; // K顶点计数加1
        }
    }

    return count; // 返回K顶点的总个数
}

代码逻辑解析¶

1. 基本概念¶

出度：从某个顶点出发的边的条数
入度：指向某个顶点的边的条数
K顶点：出度大于入度的顶点

2. 邻接矩阵特性¶

在邻接矩阵中： - G.Edge[i][j] = 1 表示存在从顶点i到顶点j的边 - G.Edge[i][j] = 0 表示不存在从顶点i到顶点j的边

3. 度数计算方法¶

顶点i的出度：第i行所有元素的和
顶点i的入度：第i列所有元素的和

4. 算法流程¶

遍历每个顶点
对每个顶点计算其入度和出度
判断是否满足出度 > 入度的条件
如果满足条件，则输出该顶点并计数
返回K顶点的总个数

时间复杂度分析¶

1. 外层循环¶

遍历所有顶点：V次（V为顶点数）

2. 内层循环¶

对每个顶点计算度数：V次

3. 总体时间复杂度¶

O(V²)，其中V是顶点数

空间复杂度分析¶

1. 额外空间使用¶

只使用了常量级别的局部变量：
count：记录K顶点个数
indegree、outdegree：临时存储度数
循环变量 i、j

2. 总体空间复杂度¶

O(1) - 常数空间复杂度

较难理解部分的说明¶

1. 邻接矩阵中度数的计算原理¶

图解说明：¶

假设有一个有向图的邻接矩阵：

Text Only

    A  B  C  D
A [ 0  1  1  0 ]  // A的出度 = 1+1+0+0 = 2
B [ 0  0  1  1 ]  // B的出度 = 0+0+1+1 = 2  
C [ 1  0  0  1 ]  // C的出度 = 1+0+0+1 = 2
D [ 0  1  0  0 ]  // D的出度 = 0+1+0+0 = 1

    ↓  ↓  ↓  ↓
    1  2  2  2    // 各顶点的入度

度数计算过程：

Text Only

顶点A：
- 出度：Edge[0][0] + Edge[0][1] + Edge[0][2] + Edge[0][3] = 0+1+1+0 = 2
- 入度：Edge[0][0] + Edge[1][0] + Edge[2][0] + Edge[3][0] = 0+0+1+0 = 1
- 出度(2) > 入度(1) → A是K顶点

顶点B：
- 出度：Edge[1][0] + Edge[1][1] + Edge[1][2] + Edge[1][3] = 0+0+1+1 = 2
- 入度：Edge[0][1] + Edge[1][1] + Edge[2][1] + Edge[3][1] = 1+0+0+1 = 2
- 出度(2) = 入度(2) → B不是K顶点

2. K顶点的实际意义¶

在实际应用中，K顶点通常表示： - 信息源：发送信息多于接收信息的节点 - 生产者：产出多于消耗的实体 - 起点：在网络中作为起点使用较多的节点

延伸知识点¶

1. 优化版本 - 一次遍历计算所有度数¶

C
// 优化版本：减少重复计算
int funcOptimized(MGraph G) {
    int count = 0;
    int* indegree = (int*)calloc(G.numver, sizeof(int));
    int* outdegree = (int*)calloc(G.numver, sizeof(int));

    // 一次遍历计算所有顶点的度数
    for (int i = 0; i < G.numver; i++) {
        for (int j = 0; j < G.numver; j++) {
            outdegree[i] += G.Edge[i][j];
            indegree[j] += G.Edge[i][j];
        }
    }

    // 判断K顶点
    for (int i = 0; i < G.numver; i++) {
        if (outdegree[i] > indegree[i]) {
            printf("%c ", G.verticle[i]);
            count++;
        }
    }

    free(indegree);
    free(outdegree);
    return count;
}

2. 邻接表表示的版本¶

C
// 对于邻接表表示的图
int funcAdjList(ALGraph G) {
    int count = 0;
    int* indegree = (int*)calloc(G.numver, sizeof(int));
    int* outdegree = (int*)calloc(G.numver, sizeof(int));

    // 计算出度和入度
    for (int i = 0; i < G.numver; i++) {
        outdegree[i] = G.adjlist[i].outdegree; // 直接获取出度

        // 计算入度
        ArcNode* p = G.adjlist[i].firstarc;
        while (p != NULL) {
            indegree[p->adjvex]++;
            p = p->nextarc;
        }
    }

    // 判断K顶点
    for (int i = 0; i < G.numver; i++) {
        if (outdegree[i] > indegree[i]) {
            printf("%c ", G.adjlist[i].vertex);
            count++;
        }
    }

    free(indegree);
    free(outdegree);
    return count;
}

3. 相关概念扩展¶

C
// 统计不同类型的顶点
typedef struct {
    int source_count;     // 源点数（出度>入度）
    int sink_count;       // 汇点数（入度>出度）  
    int isolated_count;   // 孤立点数（入度=出度=0）
    int balanced_count;   // 平衡点数（入度=出度>0）
} VertexStats;

VertexStats analyzeVertices(MGraph G) {
    VertexStats stats = {0, 0, 0, 0};

    for (int i = 0; i < G.numver; i++) {
        int indegree = 0, outdegree = 0;
        for (int j = 0; j < G.numver; j++) {
            outdegree += G.Edge[i][j];
            indegree += G.Edge[j][i];
        }

        if (outdegree > indegree) {
            stats.source_count++;
        } else if (indegree > outdegree) {
            stats.sink_count++;
        } else if (indegree == 0 && outdegree == 0) {
            stats.isolated_count++;
        } else {
            stats.balanced_count++;
        }
    }

    return stats;
}

4. 实际应用场景¶

网络分析：¶

C
// 社交网络中的影响力节点识别
int findInfluencers(MGraph socialNetwork) {
    // K顶点表示发布内容多于接收内容的用户
    return func(socialNetwork);
}

交通网络：¶

C
// 交通枢纽分析
int findTrafficSources(MGraph trafficNetwork) {
    // K顶点表示发出交通流多于接收交通流的节点
    return func(trafficNetwork);
}

数据流分析：¶

C
// 数据生产者识别
int findDataProducers(MGraph dataFlow) {
    // K顶点表示产生数据多于消费数据的节点
    return func(dataFlow);
}

5. 性能对比¶

方法	时间复杂度	空间复杂度	适用场景
原始版本	O(V²)	O(1)	简单直接，空间敏感
优化版本	O(V²)	O(V)	减少重复计算
邻接表版本	O(V+E)	O(V)	稀疏图优化

这种方法体现了图论基本概念应用和矩阵运算优化的思想，是图算法中的基础问题之一。