图的度 - 七级 | C++ & Algorithm 编程研习社

认识图的度——从朋友数量到社交关系

在图中，每个顶点有多少条边和它相连，叫做这个顶点的度（Degree）。你可以把一个顶点想象成一个小明星，度就是他的朋友数量。度能帮我们快速了解这个顶点在图里有多“热闹”，是图论中最基础也最常用的概念之一。

比如，在一个班级里，你可以把自己想象成一个顶点，你和班上其他同学之间的友谊关系就是边。你的朋友越多，你的“度”就越大。如果没有任何朋友（度=0），那就是孤立无援啦。

下面我们分两种情况来详细讲解：无向图和有向图。

? 无向图的度：数一数你连接了几条边

在无向图中，边没有方向，就像“朋友关系”是互相的。你和小明是朋友，那么这条边既连接你，也连接小明。所以一个顶点的度就是和它相连的边数。

生活例子：

小明和小红是朋友，小明和小刚也是朋友，小明和小丽也是朋友。那么小明的朋友有3个，他的度就是3。
如果小红只认识小明一个人，她的度就是1。
如果小华谁也不认识，他的度就是0，说明他孤立无援。

如何计算？
在代码里，我们可以用邻接矩阵来记录每个顶点之间是否有边。假设有4个顶点（0、1、2、3），矩阵中 graph[v][u] = 1 表示顶点v和u之间有边，0 表示没有边。要算顶点v的度，就数第v行里有多少个1。

下面这段代码展示了无向图度的计算（注意：无向图的矩阵是对称的，所以每行数1的个数就是度）：

#include <iostream>
using namespace std;

int main() {
    const int n = 4;                    // 顶点个数
    // 邻接矩阵，0表示无边，1表示有边
    int graph[n][n] = {
        {0, 1, 1, 0},   // 顶点0与1和2相连
        {1, 0, 1, 1},   // 顶点1与0、2和3相连
        {1, 1, 0, 0},   // 顶点2与0和1相连
        {0, 1, 0, 0}    // 顶点3只与1相连
    };

    cout << "每个顶点的度（无向图）:" << endl;
    for (int v = 0; v < n; v++) {
        int degree = 0;                 // 记录顶点v的度
        for (int u = 0; u < n; u++) {
            if (graph[v][u] == 1)       // 如果v和u之间有边
                degree++;               // 度就加1
        }
        cout << "顶点" << v << " 的度 = " << degree << endl;
    }

    return 0;
}

运行结果：

每个顶点的度（无向图）:
顶点0 的度 = 2
顶点1 的度 = 3
顶点2 的度 = 2
顶点3 的度 = 1

? 有向图的度：入度和出度，谁说谁听？

在有向图中，边是有方向的，就像“你主动跟别人说话”和“别人主动跟你说话”是两回事。所以有向图的度要分成两种：

出度（Out-degree）：从该顶点出发的边数。 → 你主动跟别人说了多少次话。
入度（In-degree）：指向该顶点的边数。 → 别人主动跟你说了多少次话。

总度 = 出度 + 入度。

生活例子：
在班级里，你给小明发了一条消息，那你的出度+1，小明的入度+1。如果你给小红发了三条消息，你出度+3，小红入度+3。同时，小刚给你发了一条消息，你的入度+1，小刚的出度+1。
如果一个人既不给别人发消息，也没人给他发消息，那他的出度和入度都是0，相当于“社交绝缘体”。

如何计算？
同样用邻接矩阵，但注意方向：graph[v][u] = 1 表示有一条从v指向u的边（v→u）。

顶点v的出度：数第v行里有多少个1（v出发指向谁）。
顶点v的入度：数第v列里有多少个1（谁指向v）。

下面补充一个有向图的计算例子：

#include <iostream>
using namespace std;

int main() {
    const int n = 4;                    // 顶点个数
    // 有向图的邻接矩阵，graph[v][u] = 1 表示 v -> u
    int graph[n][n] = {
        {0, 1, 1, 0},   // 0 → 1, 0 → 2
        {0, 0, 0, 1},   // 1 → 3
        {0, 0, 0, 0},   // 2 没有出边
        {1, 0, 0, 0}    // 3 → 0
    };

    cout << "每个顶点的出度和入度（有向图）:" << endl;
    for (int v = 0; v < n; v++) {
        int out_deg = 0;                // 出度
        int in_deg = 0;                 // 入度
        for (int u = 0; u < n; u++) {
            if (graph[v][u] == 1)       // v有一条指向u的边
                out_deg++;
            if (graph[u][v] == 1)       // u有一条指向v的边
                in_deg++;
        }
        cout << "顶点" << v << " : 出度=" << out_deg 
             << " , 入度=" << in_deg 
             << " , 总度=" << (out_deg + in_deg) << endl;
    }
    return 0;
}

运行结果：

每个顶点的出度和入度（有向图）:
顶点0 : 出度=2 , 入度=1 , 总度=3
顶点1 : 出度=1 , 入度=1 , 总度=2
顶点2 : 出度=0 , 入度=1 , 总度=1
顶点3 : 出度=1 , 入度=1 , 总度=2

⚠️ 新手容易犯的错误

把无向图的边重复计算
在无向图中，一条边连接两个顶点，但如果你不小心数了矩阵的两侧（例如 graph[v][u] 和 graph[u][v] 都加1），度数就会变成实际的两倍。正确做法：只数一行（或一列），因为无向图矩阵对称，每行已经包含了所有相连顶点。
忽略自环
自环是一条边自己连自己，比如 graph[v][v] = 1。在无向图中，一个自环会使度数增加2（因为自己连接自己相当于两个方向）；在有向图中，一个自环会使出度和入度各增加1。很多基础代码没处理自环，需要根据题目要求决定是否包含。
混淆入度和出度
在有向图中，计算入度要关注列，出度关注行。可以记成：行表示出发，列表示到达。例如 graph[i][j] 是i→j，所以出度看第i行，入度看第j列。
忘记判断矩阵是否越界
如果顶点编号从1开始，代码里要用 n+1 大小的数组，并在循环中用 1 到 n，否则下标会错。

? 完整可运行示例（整合）

下面是一个整合程序，可以输入一个无向图或有向图（通过 directed 标志控制），然后输出每个顶点的度（无向图是总度，有向图是出度、入度、总度）。代码中包含了注释和常见情况的处理（假设没有自环，如果有自环需要额外逻辑）。

#include <iostream>
using namespace std;

int main() {
    const int n = 4;                    // 顶点个数
    bool directed = true;               // true表示有向图，false表示无向图

    // 示例：一个有向图（与上面相同）
    int graph[n][n] = {
        {0, 1, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 0},
        {1, 0, 0, 0}
    };

    if (directed) {
        // 有向图：分别计算出度和入度
        cout << "有向图：" << endl;
        for (int v = 0; v < n; v++) {
            int outDeg = 0;             // 出度
            int inDeg = 0;              // 入度
            for (int u = 0; u < n; u++) {
                if (graph[v][u] == 1)   // v → u
                    outDeg++;
                if (graph[u][v] == 1)   // u → v
                    inDeg++;
            }
            cout << "顶点" << v << " : 出度=" << outDeg 
                 << " , 入度=" << inDeg 
                 << " , 总度=" << (outDeg + inDeg) << endl;
        }
    } else {
        // 无向图：只计算总度（每行数1）
        cout << "无向图：" << endl;
        for (int v = 0; v < n; v++) {
            int degree = 0;             // 度
            for (int u = 0; u < n; u++) {
                if (graph[v][u] == 1)   // v和u之间有边
                    degree++;
            }
            cout << "顶点" << v << " 的度 = " << degree << endl;
        }
    }

    return 0;
}

? 相关指引：学完度之后可以学什么？

图的遍历：知道了每个顶点的度，可以帮助你判断从哪里开始搜索最方便。比如，在社交网络中，从度大的顶点开始遍历，能更快地发现很多朋友。
连通分量：如果某个顶点的度是0，它就是一个孤立点，属于单独的连通分量。计算度可以快速找到图中不连通的部分。
最短路径：有些算法（比如 Dijkstra）需要反复访问顶点的邻接顶点，而邻接顶点的“度”会影响算法的效率。
握手定理（了解即可）：在无向图中，所有顶点的度之和等于边数的两倍。这个定理可以用来验证你的度计算是否正确。

现在你已经学会了如何用代码计算一个顶点有多少“朋友”，赶紧试试用这个知识去分析一下你身边的小圈子吧！