c++算法int DegreeDifferent ( Graph& G, int i )求有向图Vi 的出度和入度的差

您好！感谢您的提问！根据您的问题，我可以给出以下的C++算法实现：

int DegreeDifferent(Graph& G, int i) {
    int in_degree = 0, out_degree = 0;
    for (int j = 0; j < G.V(); j++) {
        if (G.hasEdge(i, j)) {
            out_degree++;
        }
        if (G.hasEdge(j, i)) {
            in_degree++;
        }
    }
    return out_degree - in_degree;
}

上述算法首先初始化入度和出度为0，然后遍历整个图，对于每个与Vi有边相连的顶点，增加出度计数器。对于每个与Vi相连的顶点，增加入度计数器。最后返回出度和入度的差即可。

希望这个算法可以帮到您，如果您还有其他问题，请随时提出！

相关问题

数据结构 C+＋实现 有向图的邻接表存储，并输出 顶点的出度和入度

下面是一个简单的 C++ 实现，使用邻接表存储有向图，并输出每个顶点的出度和入度：

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

class Graph {
private:
    int V; // 图中顶点的数量
    vector<vector<int>> adj; // 邻接表

public:
    // 构造函数
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    // 添加一条从 u 到 v 的边
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    // 输出每个顶点的出度和入度
    void printDegree() {
        for (int i = 0; i < V; i++) {
            int out_degree = adj[i].size(); // 出度
            int in_degree = 0; // 入度

            // 计算入度
            for (int j = 0; j < V; j++) {
                for (auto k : adj[j]) {
                    if (k == i) {
                        in_degree++;
                        break;
                    }
                }
            }

            cout << "顶点 " << i << " 的出度为 " << out_degree << "，入度为 " << in_degree << endl;
        }
    }
};

int main() {
    // 创建图
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(3, 4);

    // 输出每个顶点的出度和入度
    g.printDegree();

    return 0;
}

输出结果如下：

顶点 0 的出度为 1，入度为 1
顶点 1 的出度为 1，入度为 1
顶点 2 的出度为 1，入度为 1
顶点 3 的出度为 1，入度为 0
顶点 4 的出度为 0，入度为 1

用C语言写出代码和输入实例及结果：已知有向图采用邻接矩阵作为存储结构，设计算法求该图中每个顶点的出度和入度,

代码如下：

#include <stdio.h>

#define MAX_VERTEX_NUM 100

typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vex_num, arc_num; // 顶点数、弧数
} Graph;

// 初始化有向图
void init_graph(Graph *g, int vex_num, int arc_num) {
    g->vex_num = vex_num;
    g->arc_num = arc_num;
    for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
        for (int j = 0; j < MAX_VERTEX_NUM; ++j) {
            g->arcs[i][j] = 0; // 初始化邻接矩阵
        }
    }
}

// 添加弧
void add_arc(Graph *g, int start, int end) {
    g->arcs[start][end] = 1;
}

// 求每个顶点的出度和入度
void get_degree(Graph g, int out_degree[], int in_degree[]) {
    for (int i = 0; i < g.vex_num; ++i) {
        out_degree[i] = 0;
        in_degree[i] = 0;
        for (int j = 0; j < g.vex_num; ++j) {
            if (g.arcs[i][j]) { // 如果有弧 i -> j
                out_degree[i]++; // i 的出度加 1
                in_degree[j]++; // j 的入度加 1
            }
        }
    }
}

int main() {
    Graph g;
    int out_degree[MAX_VERTEX_NUM], in_degree[MAX_VERTEX_NUM];
    int vex_num, arc_num;
    printf("请输入顶点数和弧数：");
    scanf("%d%d", &vex_num, &arc_num);
    init_graph(&g, vex_num, arc_num);
    printf("请输入每条弧的起点和终点：\n");
    for (int i = 0; i < arc_num; ++i) {
        int start, end;
        scanf("%d%d", &start, &end);
        add_arc(&g, start, end);
    }
    get_degree(g, out_degree, in_degree);
    printf("每个顶点的出度和入度分别为：\n");
    for (int i = 0; i < vex_num; ++i) {
        printf("顶点 %d：出度 %d，入度 %d\n", i, out_degree[i], in_degree[i]);
    }
    return 0;
}

输入实例：

请输入顶点数和弧数：4 5
请输入每条弧的起点和终点：
0 1
1 2
2 0
1 3
3 2

输出结果：

每个顶点的出度和入度分别为：
顶点 0：出度 1，入度 1
顶点 1：出度 2，入度 1
顶点 2：出度 1，入度 2
顶点 3：出度 1，入度 1