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

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

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

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

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

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

#include 
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> 或数组的链表实现。每个顶点维护一个相邻顶点列表。

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

#include 
#include 
using namespace std;

void calculateInAndOutDegree(vector>& adj, int V) {
    vector 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;
    }
}

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

优化建议与注意事项

对于频繁查询入度的场景，可以在建图时同步维护入度数组，避免重复遍历。
如果是有向图，入度和出度通常不相等；无向图中，每个边会被双向记录，因此每个顶点的入度等于出度，也等于其度数。

建图时注意边界处理，如重边和自环，根据实际需求决定是否去重或特殊处理。

基本上就这些，选择合适的数据结构能显著提升效率。