实现图的领接矩阵和领接表的存储

图的领接矩阵和领接表都是用来表示无向图或有向图的数据结构，其中领接矩阵是一个二维数组，而领接表则是一个链表数组。

领接矩阵的存储方式：假设有$n$个节点，$m$条边，那么我们可以用一个$n\times n$的矩阵$M$来表示图的领接矩阵。其中$M[i][j]$表示节点$i$和节点$j$之间是否有边相连，如果有，则为$1$，否则为$0$。当图是有向图时，领接矩阵中的元素可能为$-1$或$1$，表示出度和入度。这种方式的存储方式比较简单，但是当图比较稀疏时，矩阵中会存在大量的$0$，造成存储空间的浪费。

领接表的存储方式：假设有$n$个节点，$m$条边，那么我们可以用一个长度为$n$的链表数组来存储图的领接表。具体来说，对于节点$i$，我们可以用一个链表$L_i$来存储所有与节点$i$相连的节点。链表$L_i$中的每一个节点都保存了一个指向与节点$i$相连的另一个节点的指针。这种方式的存储方式比较灵活，适用于稀疏图的存储，但是对于稠密图，可能会造成存储空间的浪费。

综上所述，领接矩阵适用于稠密图的存储，而领接表适用于稀疏图的存储。

相关问题

领接链表和领接矩阵应用

邻接矩阵和邻接链表是图论中两种常用的存储方式。

邻接矩阵是用一个二维数组来表示图中的顶点之间的关系，对于无向图来说，如果顶点 i 与顶点 j 之间有边相连，则邻接矩阵中第 i 行第 j 列和第 j 行第 i 列的元素值都为 1，否则都为 0。对于有向图来说，邻接矩阵中第 i 行第 j 列的元素值表示从顶点 i 到顶点 j 是否有一条有向边。邻接矩阵的优点是易于理解和实现，能够快速判断两个顶点之间是否有边相连，但缺点是对于稀疏图而言，浪费了很多空间。

邻接链表是将每个顶点作为链表中的一个节点，每个节点中存储该顶点的出边或入边。对于无向图来说，如果顶点 i 与顶点 j 之间有边相连，则在节点 i 的链表中加入一个节点 j，在节点 j 的链表中加入一个节点 i。对于有向图来说，只需要在出度节点的链表中加入该节点指向的节点即可。邻接链表的优点是节约空间，缺点是判断两个顶点之间是否有边相连需要遍历链表。

邻接矩阵和邻接链表都可以用于描述图中的结构，它们在算法中都有广泛应用。比如基于邻接矩阵或邻接链表可以实现广度优先搜索和深度优先搜索等算法。

有向表的领接矩阵存储代码

以下是一个示例代码，用于将有向图的邻接矩阵存储为二维数组：

#include <iostream>
using namespace std;

const int MAXN = 100; // 最大节点数

int g[MAXN][MAXN]; // 存储邻接矩阵
int n, m; // 节点数和边数

int main() {
    cin >> n >> m; // 输入节点数和边数

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g[i][j] = 0;
        }
    }

    // 输入边信息，存储到邻接矩阵中
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = 1;
    }

    // 输出邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

在这个示例代码中，我们首先使用二维数组 `g` 存储邻接矩阵，然后使用两个变量 `n` 和 `m` 分别存储节点数和边数。在输入边信息时，我们将起点和终点存储到邻接矩阵中，表示这两个节点之间有一条有向边。最后输出邻接矩阵。