邻接表和邻接矩阵的互转

1、写出从图的邻接表表示转换为邻接矩阵表示的算法

void InitMGraph(MGraph &G, ALGraph AG){
    G.VexNum = AG.Vexnum;
    G.EdgeNum = AG.EdgeNum;

    for(int i = 0; i < G.VexNum; i++){
        G.Vetex[i] = AG.Vex[i].info;
        for(int j = 0; j < G.VexNum; j++){
            if(i == j) G.Edge[i][j] = 0;
            else G.Edge[i][j] = INT_MAX;
        }
    }
    
}

// 以有向网为例
MGraph adjacencyList_to_adjacencymatrix(ALGraph AG){
    MGraph G;
    InitMGraph(G, AG);

    // 将邻接表的边结点所表示的边 转换为 邻接矩阵所表示的边
    for(int i = 0; i < AG.Vexnum; i++){
        ArcNode *ptr = AG.Vex[i].next;
        if(ptr == nullptr) continue;
        for(; ptr != nullptr; ptr = ptr->next){
            G.Edge[i][ptr->alvex] = ptr->Edgeval;
        }
    }
    return G;
}

测试代码

int main(){
    ALGraph AG;
    CreateGraph(AG,3,4);

    MGraph G = adjacencyList_to_adjacencymatrix(AG);

    // 打印边信息
    for(int i = 0; i < G.VexNum; i++){
        for(int j = 0; j < G.VexNum; j++){
            std::cout << G.Edge[i][j] << "\t\t";
        }
        std::cout << std::endl;
    }
    return 0;
}
/*
输入:
Input vex info(char): ABC 
Input vex1 and vex2 info(char): AB
Input edgeval: 20
Input vex1 and vex2 info(char): BA
Input edgeval: 10
Input vex1 and vex2 info(char): AC
Input edgeval: 30
Input vex1 and vex2 info(char): BC
Input edgeval: 40
*/
/*
输出:
0               20              30
10              0               40
2147483647              2147483647              0
*/

2、写出从图的邻接矩阵表示转换为邻接表表示的算法

同理，阿Q就偷懒咯

---

十字链表和邻接表的联系

为了解决有向图的邻接表计算入度困难问题，引入了有向图的十字链表。

有向图的十字链表本质上是将有向图的邻接表和逆邻接表整合在一起。

第一个指针域 表示 逆邻接表，第二个指针域 表示 邻接表

---

邻接多重表和邻接表的联系

为了解决无向图的邻接表的边结点重复存储问题，引入了无向图的邻接多重表。

无向图的邻接多重表本质上将无向边(u,v)视为有向边<u,v> + <v,u>，因此要在一条边结点上存两个指针

第一个指针域 表示<u,v>； 第二个指针域 表示 <v,u>