c++中如何计算图的入度和出度_c++图入度出度计算方法-C++-PHP中文网

c++中如何计算图的入度和出度_c++图入度出度计算方法

尼克

发布： 2025-10-10 12:07:01

原创

651人浏览过

答案：在C++中，邻接矩阵通过行求出度、列求入度，邻接表通过邻接表大小得出度、遍历统计入度，分别适用于稠密图和稀疏图。

c++中如何计算图的入度和出度_c++图入度出度计算方法

在C++中计算图的入度和出度，主要取决于图的存储方式。常见的表示方法有邻接矩阵和邻接表。下面分别介绍这两种方式下如何统计每个顶点的入度和出度。

使用邻接矩阵计算入度和出度

邻接矩阵是一个二维数组 graph[V][V]，其中 graph[i][j] = 1 表示存在从顶点 i 到顶点 j 的边。

出度：某顶点对应行中所有为1的元素个数。
入度：某顶点对应列中所有为1的元素个数。

示例代码：

#include <iostream>
using namespace std;

void calculateDegree(int graph[][5], int V) {
    for (int i = 0; i < V; i++) {
        int outDegree = 0, inDegree = 0;
        // 计算出度：遍历第i行
        for (int j = 0; j < V; j++) {
            if (graph[i][j]) outDegree++;
        }
        // 计算入度：遍历第i列
        for (int j = 0; j < V; j++) {
            if (graph[j][i]) inDegree++;
        }
        cout << "顶点 " << i << " 的出度为：" << outDegree
             << "，入度为：" << inDegree << endl;
    }
}

登录后复制

这种方法适合顶点数较少的稠密图。

立即学习“C++免费学习笔记（深入）”；

使用邻接表计算入度和出度

邻接表通常用 vector<vector<int>> 或数组的链表实现。每个顶点维护一个相邻顶点列表。

百度·度咔剪辑

度咔剪辑，百度旗下独立视频剪辑App

查看详情

出度：直接取该顶点邻接表的大小（adj[u].size()）。
入度：需要遍历所有顶点的邻接表，统计有多少条边指向当前顶点。

示例代码：

#include <iostream>
#include <vector>
using namespace std;

void calculateInAndOutDegree(vector<vector<int>>& adj, int V) {
    vector<int> inDegree(V, 0);

    // 统计入度：遍历每条边
    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) {
            inDegree[v]++;
        }
    }

    // 出度就是邻接表中每个vector的大小
    for (int u = 0; u < V; u++) {
        cout << "顶点 " << u << " 的出度为：" << adj[u].size()
             << "，入度为：" << inDegree[u] << endl;
    }
}

登录后复制

这种方式更节省空间，适用于稀疏图。