第5关：根据一个有向图的邻接表建立它的逆邻接表

### 构建有向图的逆邻接表

为了构建有向图的逆邻接表，可以遍历原邻接表中的每一条边，并将其反向加入到新的逆邻接表中。具体来说，在原始邻接表中如果存在从顶点`u`指向顶点`v`的一条弧，则在逆邻接表中应建立从`v`指向`u`的一个对应关系。

以下是实现这一过程的具体方法：

#### 定义数据结构
定义用于表示有向图的数据结构如下所示[^1]：

struct ArcNode {
    int adjvex;                 // 变的另一个邻接点的序号
    struct ArcNode *nextarc;   // 指向下一条弧的指针
};

struct VNode {
    char data;                  // 顶点信息
    ArcNode *firstout, *firstin;// 出边表和入边表的表头指针
};

struct LGraph {
    VNode vertexs[MAX_VERTEX_NUM];
    int vexnum;
    int arcnum;
};

#### 创建逆邻接表函数
下面是一个C++代码片段来展示如何基于给定的正向邻接表创建对应的逆邻接表：

void CreateInverseAdjacencyList(LGraph &G, LGraph &IGraph) {
    IGraph.vexnum = G.vexnum;
    IGraph.arcnum = G.arcnum;

    for (int i = 0; i < G.vexnum; ++i) {        // 初始化新图各个结点的信息
        strcpy(IGraph.vertexs[i].data, G.vertexs[i].data);
        IGraph.vertexs[i].firstin = nullptr;
        IGraph.vertexs[i].firstout = nullptr;
    }

    for (int v = 0; v < G.vexnum; ++v) {         // 遍历每一个顶点
        ArcNode* p = G.vertexs[v].firstout;      // 获取当前顶点的第一个出边节点
        
        while(p != NULL){
            int w = p->adjvex;                   // 找到该边所连接的目标顶点w
            
            // 向目标顶点w添加一个新的入边记录，即从w出发回到原来的起点v形成的新边
            ArcNode* newArc = new ArcNode{v, IGraph.vertexs[w].firstin};  
            
            IGraph.vertexs[w].firstin = newArc;  // 更新目标顶点w的第一条入边位置为新建的这条边
            p = p->nextarc;                      // 继续处理下一条出边
        }
    }
}

此算法通过两次循环实现了对原有向图邻接表的转换操作，第一次初始化了逆邻接表的各项参数；第二次则逐一遍历每个顶点及其相连的所有边并完成相应的反转工作。