FC03-计算有向图中每个顶点的入度和出度¶

代码实现¶

C
// 函数 func：计算有向图中每个顶点的入度和出度
// 参数：
// G - 图的邻接表表示
// inres[] - 存储每个顶点入度的数组
// outres[] - 存储每个顶点出度的数组
void func(Graph G, int inres[], int outres[]) {
    // 初始化入度和出度数组
    for (int i = 0; i < G.numver; i++) {
        inres[i] = 0;    // 初始化入度为 0
        outres[i] = 0;   // 初始化出度为 0
    }

    // 遍历每个顶点的邻接表，计算入度和出度
    for (int i = 0; i < G.numver; i++) {
        // 获取顶点 i 的第一条邻接边
        Node p = G.adjlist[i].firstarc;

        // 遍历顶点 i 的所有邻接边
        for (; p != NULL; p = p->nextarc) {
            outres[i]++;              // 顶点 i 的出度加 1
            inres[p->adjvex]++;       // 边指向的顶点入度加 1
        }
    }
}

代码逻辑解析¶

1. 邻接表存储结构¶

顶点数组：G.adjlist[] 存储每个顶点的信息
边链表：每个顶点对应一个链表，存储从该顶点出发的所有边

边节点结构：

C
typedef struct ArcNode {
    int adjvex;              // 弧头顶点的索引
    struct ArcNode* nextarc; // 指向下一个弧节点
} ArcNode, *Node;

2. 度数定义¶

出度：从某个顶点出发的边的数量
入度：指向某个顶点的边的数量

3. 算法思路¶

初始化阶段：将所有顶点的入度和出度都初始化为 0
统计阶段：
遍历每个顶点的邻接表
对于从顶点 i 出发的每条边：
- 顶点 i 的出度加 1
- 该边指向的顶点入度加 1

4. 遍历过程¶

外层循环：遍历所有顶点（0 到 G.numver-1）
内层循环：遍历当前顶点的所有邻接边
对每条边进行度数统计

时间复杂度分析¶

1. 初始化阶段¶

遍历所有顶点：O(V)，其中 V 是顶点数

2. 统计阶段¶

外层循环遍历所有顶点：O(V)
内层循环遍历所有边：O(E)，其中 E 是边数
总时间复杂度：O(V + E)

3. 总体时间复杂度¶

O(V + E) - 线性时间复杂度

空间复杂度分析¶

1. 额外空间使用¶

inres[] 数组：O(V)
outres[] 数组：O(V)
循环变量和其他局部变量：O(1)

2. 总体空间复杂度¶

O(V)

较难理解部分的说明¶

1. 入度和出度的计算机制¶

C
// 关键理解点：
outres[i]++;              // 从顶点 i 出发的边，i 的出度加 1
inres[p->adjvex]++;       // 指向顶点 p->adjvex 的边，该顶点入度加 1

图解说明：¶

假设有向图如下：

Text Only
1 2 3	`0 → 1 ↓ ↓ 2 → 3`

邻接表表示：

Text Only

顶点 0: 1 → 2 → NULL    (从 0 出发有两条边：0→1, 0→2)
顶点 1: 3 → NULL        (从 1 出发有一条边：1→3)
顶点 2: 3 → NULL        (从 2 出发有一条边：2→3)
顶点 3: NULL            (从 3 出发没有边)

度数统计过程：

Text Only

处理顶点 0 的邻接表：
- 边 0→1: outres[0]++, inres[1]++
- 边 0→2: outres[0]++, inres[2]++

处理顶点 1 的邻接表：
- 边 1→3: outres[1]++, inres[3]++

处理顶点 2 的邻接表：
- 边 2→3: outres[2]++, inres[3]++

处理顶点 3 的邻接表：
- 无边

最终结果：
出度: [2, 1, 1, 0]  // 顶点 0,1,2,3 的出度
入度: [0, 1, 1, 2]  // 顶点 0,1,2,3 的入度

延伸知识点¶

1. 改进版本 - 单次遍历¶

C
// 优化版本：在初始化的同时进行统计
void funcOptimized(Graph G, int inres[], int outres[]) {
    // 初始化数组
    for (int i = 0; i < G.numver; i++) {
        inres[i] = 0;
        outres[i] = 0;
    }

    // 统计度数
    for (int i = 0; i < G.numver; i++) {
        Node p = G.adjlist[i].firstarc;
        while (p != NULL) {
            outres[i]++;        // 出度统计
            inres[p->adjvex]++; // 入度统计
            p = p->nextarc;
        }
    }
}

2. 无向图的度数计算¶

C
// 无向图的度数计算（每个边贡献 2 个度数）
void funcUndirected(Graph G, int degree[]) {
    // 初始化
    for (int i = 0; i < G.numver; i++) {
        degree[i] = 0;
    }

    // 统计度数
    for (int i = 0; i < G.numver; i++) {
        Node p = G.adjlist[i].firstarc;
        while (p != NULL) {
            degree[i]++;           // 顶点 i 的度数加 1
            degree[p->adjvex]++;   // 相邻顶点的度数加 1
            p = p->nextarc;
        }
    }

    // 由于每条边被计算了两次，需要除以 2
    for (int i = 0; i < G.numver; i++) {
        degree[i] /= 2;
    }
}

3. 相关图论概念¶

C
// 判断是否为有向无环图 (DAG) 的必要条件
bool isPossibleDAG(int inres[], int outres[], int numver) {
    int sourceCount = 0;  // 入度为 0 的顶点数
    int sinkCount = 0;    // 出度为 0 的顶点数

    for (int i = 0; i < numver; i++) {
        if (inres[i] == 0) sourceCount++;
        if (outres[i] == 0) sinkCount++;
    }

    // DAG 至少需要一个源点和一个汇点
    return (sourceCount > 0 && sinkCount > 0);
}

// 判断是否为欧拉图
bool isEulerian(int inres[], int outres[], int numver) {
    for (int i = 0; i < numver; i++) {
        if (inres[i] != outres[i]) {
            return false; // 每个顶点的入度必须等于出度
        }
    }
    return true;
}

4. 非邻接表版本 - 邻接矩阵¶

C
// 使用邻接矩阵计算度数
void funcMatrix(int adjMatrix[][MAX_VERTICES], int numver, 
                int inres[], int outres[]) {
    // 初始化
    for (int i = 0; i < numver; i++) {
        inres[i] = 0;
        outres[i] = 0;
    }

    // 统计度数
    for (int i = 0; i < numver; i++) {
        for (int j = 0; j < numver; j++) {
            if (adjMatrix[i][j] != 0) {
                outres[i]++;  // 顶点 i 的出度
                inres[j]++;   // 顶点 j 的入度
            }
        }
    }
}

5. 实际应用场景¶

社交网络分析：计算用户的关注数（出度）和粉丝数（入度）
网页链接分析：计算网页的出链数和入链数（PageRank 算法基础）
任务调度：分析任务的依赖关系（入度表示前置任务数）
交通网络：计算路口的流入和流出车流量
软件工程：分析模块间的调用关系

6. 性能优化建议¶

C
// 并行处理版本（适用于大规模图）
void funcParallel(Graph G, int inres[], int outres[]) {
    // 初始化
    #pragma omp parallel for
    for (int i = 0; i < G.numver; i++) {
        inres[i] = 0;
        outres[i] = 0;
    }

    // 使用原子操作避免竞争条件
    #pragma omp parallel for
    for (int i = 0; i < G.numver; i++) {
        Node p = G.adjlist[i].firstarc;
        while (p != NULL) {
            __sync_fetch_and_add(&outres[i], 1);
            __sync_fetch_and_add(&inres[p->adjvex], 1);
            p = p->nextarc;
        }
    }
}

这种方法体现了图的遍历和度数统计的经典思想，是图论算法中的基础问题，在实际应用中具有重要意义。