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

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

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

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

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

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

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

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

相关问题

有向图采用邻接表存储计算入度和出度

在C++中，使用邻接表（Adjacency List）存储有向图是一种常见的数据结构选择，因为它对于稀疏图（边的数量远小于顶点数量的平方）来说非常高效，因为每个顶点只需要存储与其相邻的顶点列表，而不是所有可能的连接。

要计算有向图中某个顶点的入度（in-degree）和出度（out-degree），你可以创建两个哈希表或集合（如`std::unordered_map`），分别用于存储从其他顶点指向当前顶点的边（入度）和从当前顶点指向其他顶点的边（出度）。

以下是一个简单的示例：

#include <iostream>
#include <unordered_map>

// 定义图节点类
class GraphNode {
public:
    int vertex;
    std::unordered_map<int, bool> outgoing_edges; // 出度，键为邻接顶点，值为是否有边

    GraphNode(int v) : vertex(v) {}
};

// 计算入度和出度
void compute_degrees(const std::vector<GraphNode>& graph, int node_id, int& in_degree, int& out_degree) {
    in_degree = 0;
    out_degree = graph[node_id].outgoing_edges.size();

    for (const auto& edge : graph[node_id].outgoing_edges) {
        if (edge.second) { // 如果有边
            in_degree++;
        }
    }
}

int main() {
    // 创建一个有向图的邻接表表示，这里只是一个简化的例子，实际应用中会根据需求添加更多节点
    std::vector<GraphNode> graph = {
        {0, {{1, true}, {2, false}}}, // 0 -> 1, 0 -> 2
        {1, {{0, true}, {3, true}}}, // 1 -> 0, 1 -> 3
        {2, {{0, false}}},          // 2 -> 0
        {3, {{1, true}}}            // 3 -> 1
    };

    int in_degree, out_degree;
    compute_degrees(graph, 1, in_degree, out_degree);
    std::cout << "Vertex 1's in-degree: " << in_degree << ", out-degree: " << out_degree << std::endl;

    return 0;
}

在这个示例中，我们首先定义了一个`GraphNode`类，其中包含一个顶点ID和一个出度哈希表。然后在`compute_degrees`函数中，我们遍历该节点的出边并更新相应的度数。

运行这个程序后，你会看到节点1的入度和出度。

邻接表求图的入度出度

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

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

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

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