邻接表有向图入度计算

邻接表表示的有向图，入度指的是以某个顶点为终点的边的数量。计算有向图的入度可以通过遍历所有顶点并统计以每个顶点为终点的边的数量来实现。

以下是计算有向图入度的一种简单算法：

1. 创建一个大小为顶点数量的数组 indegree，用于存储每个顶点的入度。
2. 遍历邻接表的所有顶点。
3. 对于每个顶点 v，遍历它的所有邻接顶点 w。
4. 对于每个邻接顶点 w，将 indegree[w] 的值加1。
5. 遍历完所有顶点后，indegree 数组中的每个元素即为对应顶点的入度。

以下是一个示例代码来计算有向图入度：

def calculate_indegree(adjacency_list):
    num_vertices = len(adjacency_list)
    
    indegree = [0] * num_vertices  # 创建一个大小为顶点数量的数组
    
    for v in range(num_vertices):
        for w in adjacency_list[v]:
            indegree[w] += 1  # 将邻接顶点的入度加1
    
    return indegree

# 示例邻接表
adjacency_list = [[1, 2], [2, 3], [0], [2]]
indegrees = calculate_indegree(adjacency_list)
print(indegrees)  # 输出: [1, 1, 2, 0]

相关问题

将有向图的出度邻接表改为按入度建立的逆邻接表

将有向图的出度邻接表改为按入度建立的逆邻接表，可以按照以下步骤进行：

1. 创建一个空的逆邻接表，用于存储每个顶点的入度邻接关系。

2. 遍历原有的出度邻接表，对于每个顶点，找到其指向的所有邻接顶点。

3. 对于每个邻接顶点，将其加入到对应的逆邻接表中，即将该邻接顶点加入到与其相连的顶点的入度邻接列表中。

4. 重复步骤2和步骤3，直到遍历完所有顶点和其出度邻接关系。

5. 返回最终得到的逆邻接表，即为按入度建立的逆邻接表。

这样，将原有的出度邻接表转换为按入度建立的逆邻接表后，我们可以更方便地查找每个顶点的入度邻接关系。

邻接表求图的入度出度

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

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

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

下面是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;
}