图的存储

邻接矩阵

Adjaency matrix，使用矩阵来表示点与点的连接关系，包含两部分：

一个一维数组存储图中顶点的信息。
一个二维数组存储图中顶点之间的邻接关系。

如果顶点的信息是0~n编号，则可以省略掉一维数组，但如果顶点是类似字符串这样的信息，则需要先用一维数组存储，然后将下标作为邻接矩阵的顶点，以下是一个邻接矩阵的示例：

使用邻接矩阵存储图时要考虑以下问题：

对角线上的点为0，这个设置可以简化后续运算。
有向图 vs 无向图：无向图是沿对角线对称的。
无权图 vs 带权图：无权图每个位置只能为0和1，但有权图可以是具体的数值，表示这条边的权值。

邻接矩阵形式的图优缺点如下：

优点：

快速判断两顶点之间是否有边。
方便计算每个顶点的度，包括入度和出度。

缺点：

空间复杂度高，尤其是在存储稀疏图时空间利用率低。
不便于增加或删除顶点。
访问一次全部的邻接点时间固定为O(n)，其中n为顶点的个数，如果n较大，则访问邻接点的将非常耗时。

邻接表

Adjacency list，图的一种链表存储方式，包含两部分：

顶点：包含顶点信息和指向第一个邻接点的指针。
邻接点：包含邻接点的下标和指向下一个邻接点的指针。

顶点的所有邻接点构成一个单链表，但如果图的情况比较简单，或者图只需要建立一次，也可以使用数组来存储所有的邻接点。以下是一个邻接表的示意图：

以下是邻接表的一些代码实现形式：

vector<int> graph[MAXN]; // maxn个顶点，graph[i]表示顶点i的全部邻接点

// 邻接点类型
struct Node {
    int val;    // 邻接点下标
    Node *next; // 下一个邻接点
    Node() : val(0), next(nullptr) {}
    Node(int v) : val(v), next(nullptr) {}
    Node(int v, Node *next) : val(v), next(next) {}
};

// 顶点类型
struct VexNode {
    VexType data;   // 顶点的数据类型，比如字符串，数字等
    Node *first;    // 指向第一个邻接点
};

// 邻接表类型
typedef struct {
    VexNode nodes[MAXN];
    int v; // 节点数
    int e; // 边数
}ALGraph;

。

页面树结构

图论基础

图的存储

邻接矩阵

邻接表