有向图和无向图中出度和入度的关系

在有向图中，每个节点有出度和入度两个概念。出度指该节点向外连出去的边的数量，入度指该节点从外部连入的边的数量。对于有向图中的任意一个节点，它的出度等于它所连出的边的数量，即它的出度等于它所连出的边的个数。而它的入度等于所有指向它的边的数量，即它的入度等于指向它的边的个数。

在无向图中，每个节点没有出度和入度的区别，因为它们只有相邻节点的概念。对于无向图中的任意一个节点，它的度数等于与之相邻的节点的数量，即它的度数等于相邻节点的个数。

相关问题

离散数学无向图和有向图

离散数学中，图可以分为有向图和无向图两种类型。

无向图：由一组顶点和一组边组成，每条边连接两个顶点，没有方向。在无向图中，每个顶点的度数是与之相连的边的数量，而一个无向图的总度数等于其边数的两倍。无向图中的边可以看作是没有方向的，因此从一个顶点到另一个顶点的路径是可以沿着任意一条边走的，因此无向图中的路径是没有方向的。

有向图：由一组顶点和一组有向边组成，每条边连接两个顶点，有方向。在有向图中，每个顶点的入度是指指向该顶点的边的数量，而出度是指从该顶点出发的边的数量。一个有向图的总入度等于总出度。有向图中的边是有方向的，因此从一个顶点到另一个顶点的路径必须沿着边的方向走，因此有向图中的路径是有方向的。

邻接表求图的入度出度

邻接表是一种图的存储结构，可以用来表示有向图和无向图。在邻接表中，每个顶点都对应一个链表，链表中存储了该顶点所指向的其他顶点。邻接表可以用来求图的入度和出度。

求图的入度：对于有向图中的每个顶点，遍历整个邻接表，统计指向该顶点的边的数量即为该顶点的入度。

求图的出度：对于有向图中的每个顶点，遍历该顶点对应的链表，统计链表中边的数量即为该顶点的出度。

下面是C++代码实现：

#include <iostream>
using namespace std;

#define MaxSize 20

struct Node {
    int weight;
    int index;
    struct Node *next;
};

struct HNode {
    char nodeData;
    struct Node *next;
};

struct Graph {
    int vertexNum;
    int arcNum;
    bool isDireted;
    HNode verList[MaxSize];
};

// 计算顶点v的入度
int getInDegree(Graph G, int v) {
    int inDegree = 0;
    for (int i = 0; i < G.vertexNum; i++) {
        Node *p = G.verList[i].next;
        while (p != NULL) {
            if (p->index == v) {
                inDegree++;
            }
            p = p->next;
        }
    }
    return inDegree;
}

// 计算顶点v的出度
int getOutDegree(Graph G, int v) {
    int outDegree = 0;
    Node *p = G.verList[v].next;
    while (p != NULL) {
        outDegree++;
        p = p->next;
    }
    return outDegree;
}

// 计算出度最大的顶点编号
int getMaxOutDegreeVertex(Graph G) {
    int maxOutDegree = 0;
    int maxOutDegreeVertex = -1;
    for (int i = 0; i < G.vertexNum; i++) {
        int outDegree = getOutDegree(G, i);
        if (outDegree > maxOutDegree) {
            maxOutDegree = outDegree;
            maxOutDegreeVertex = i;
        }
    }
    return maxOutDegreeVertex;
}

// 计算出度为0的顶点数
int getZeroOutDegreeVertexNum(Graph G) {
    int zeroOutDegreeVertexNum = 0;
    for (int i = 0; i < G.vertexNum; i++) {
        int outDegree = getOutDegree(G, i);
        if (outDegree == 0) {
            zeroOutDegreeVertexNum++;
        }
    }
    return zeroOutDegreeVertexNum;
}

int main() {
    // 创建一个有向图
    Graph G;
    G.vertexNum = 5;
    G.arcNum = 7;
    G.isDireted = true;
    for (int i = 0; i < G.vertexNum; i++) {
        G.verList[i].nodeData = 'A' + i;
        G.verList[i].next = NULL;
    }
    int arcs[7][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 3}, {2, 4}, {3, 2}, {4, 3}};
    for (int i = 0; i < G.arcNum; i++) {
        int from = arcs[i][0];
        int to = arcs[i][1];
        Node *p = new Node;
        p->index = to;
        p->next = G.verList[from].next;
        G.verList[from].next = p;
    }

    // 计算每个顶点的入度和出度
    for (int i = 0; i < G.vertexNum; i++) {
        cout << "顶点" << G.verList[i].nodeData << "的入度为：" << getInDegree(G, i) << endl;
        cout << "顶点" << G.verList[i].nodeData << "的出度为：" << getOutDegree(G, i) << endl;
    }

    // 计算出度最大的顶点编号
    int maxOutDegreeVertex = getMaxOutDegreeVertex(G);
    cout << "出度最大的顶点编号为：" << maxOutDegreeVertex << endl;

    // 计算出度为0的顶点数
    int zeroOutDegreeVertexNum = getZeroOutDegreeVertexNum(G);
    cout << "出度为0的顶点数为：" << zeroOutDegreeVertexNum << endl;

    return 0;
}