邻接矩阵

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

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

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

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

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

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

优点：

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

缺点：

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

邻接表

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

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

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

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

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]; // n个顶点，每个顶点有自己的数据，以及一个指向全部邻接点的单链表
    int v; // 节点数
    int e; // 边数
}ALGraph;

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

优点：

  1. 节省空间。
  2. 便于增删顶点。
  3. 便于访问顶点的所有邻接点。

缺点：

  1. 不便于判断两个顶点之间是否有边。
  2. 不便于计算顶点的度，尤其是顶点的入度。

边集数组

Edge list，只存储边和边的权值，不关注顶点信息，如下：

struct Edge {
    int u; // 起点
    int v; // 终点
    int w; // 权值
}; 

Edge G[MAXN]; // 边集数组

边集数组这种图的存储形式不以顶点为中心，只关注边，优点是可以对边按权值排序，以便于按顺序操作边，比如Kruskal算法就需要从小到大枚举所有的边，缺点是不便于判断两点之间是否有边，也不便于访问所有的邻接点和计算度。









。

  • 无标签