定义

图的概念

图 是由 顶点 和 边 组成的非线性数据结构。顶点 有时也被称为节点，而 边 是连接图中任意两个节点的线或弧。更正式地说，图 是由一组 顶点 $(V)$ 和一组 边 $(E)$ 组成的。图用 $G(E, V)$ 表示。

在 图论 中，根据边的方向性、连接方式、顶点间的关系等，可以进一步划分出多种类型的图，并引入如 连通性、完全性、度数 等一系列关键概念。这些分类和术语有助于我们更好地理解 图的结构特点和应用场景，下面我们将逐一进行介绍。

方向

• 有向图（directed graph）：边是有方向的，从一个定点指向另一个定点
• 无向图（undirected graph）：边是没有方向的

连通性

• 连通图（Connected Graph）：图中的每一对不同顶点都可以通过一条或多条边相互连接，也就是说，从图中的任意一个顶点出发，都可以到达图中的任意其他顶点。
• 非连通图（Disconnected Graph）：图中存在两个或多个互不相连的子图，也就是说，其中至少存在一个顶点集合，无法通过边连接到图中的其他顶点集合。
• 完全图（Complete Graph）：完全图是一种特殊的图，其中每一对不同的顶点都直接相连，也就是说，完全图中的任意两个顶点之间都存在一条边。如果一个完全图有 $n$ 个顶点，那么它将有 $C(n, 2) = n(n‑1)/2$ 条边，其中 $C(n, 2)$ 表示从 n 个顶点中选择 2 个顶点的组合数。

• 连通分量（Connected Components）：也称为连通子图，是一个无向图中的一个重要概念。一个连通分量是指在无向图中，如果从其中一个顶点出发，可以通过边的路径到达该连通分量内的任何其他顶点，而无法通过图中的边到达其他连通分量内的顶点。

度

• 顶点的度（Degree）：顶点的度是指与该顶点相邻的边的数量，也就是与该顶点直接相连的其他顶点的个数。对于有向图和无向图都适用。
  • 在无向 图 中，顶点 的度就是与该 顶点 相邻的 边 的数量。
  • 在有向 图 中，顶点 的度分为 入度 和 出度，分别表示指向该 顶点 的 边 的数量和从该 顶点 出发的 边 的数量的总和。
• 入度（In-Degree）：入度是指在有向图中指向某个顶点的边的数量，也就是与该顶点关联的边中以该顶点为终点的边的数量。
• 出度（Out-Degree）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

路径

• 简单路径：顶点不出现重复的路径
• 非简单路径：顶点出现重复的路径
• 回路：路径的起点和终点相同

图的存储

在我们使用数据结构存储 图 时，主要关注两点：1. 如何存储 顶点？2. 如何存储 边？
采用的数据结构需要能够准备表示这些信息。

邻接矩阵

定义

图的 邻接矩阵（Adjacency Matrix）是一种常用的图表示方法，特别适用于 稠密图，它以矩阵的形式表示图的连接关系。

在邻接矩阵中，行和列分别代表 图的顶点，矩阵的元素表示顶点之间是否相邻或者 边的权重。

1. 对于 无向图：
   • 如果顶点 $i$ 和顶点 $j$ 之间存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $1$ （或者表示 边 的权重）。
   • 如果顶点 $i$ 和顶点 $j$ 之间不存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $0$ 。
2. 对于 有向图：
   • 如果有一条从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $1$ （或者表示 边 的权重）。
   • 如果没有从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $0$ 。

实现

在邻接矩阵的实现中，我们使用一个 二维数组 来表示图的连接关系，邻接矩阵matrix 的行数和列数与图中的顶点数量相同。
其中 matrix[i][j] 表示顶点i 到顶点j 是否有边（或边的权值）。

• 邻接矩阵定义
• 添加边

##define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵

// 初始化邻接矩阵
void initializeMatrix(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0; // 初始化所有元素为 0
        }
    }
}

// 在邻接矩阵中添加一条边
void addEdge(int start, int end) {
    adjMatrix[start][end] = 1; // 添加边，将对应位置的元素设为 1
    adjMatrix[end][start] = 1; // 无向图需要将对称位置的元素也设为 1
}

入度出度

如果需要计算 邻接矩阵 中某个 顶点 的 出度 的话，假设 顶点 编号为 i，我们统计 邻接矩阵 中的 第 i 行 有多少元素不为 0 即可（该顶点指向哪些顶点）。

如果需要计算 邻接矩阵 中某个 顶点 的 入度 的话，假设 顶点 编号为 i，我们统计 邻接矩阵 中的 第 i 列 有多少元素不为 0 即可（哪些顶点指向该顶点）。

邻接表

定义

图的 邻接表（Adjacency List）是一种常见的图表示方法，特别适用于 稀疏图，它使用链表或数组的形式来表示图的连接关系。每个顶点都对应一个链表，链表中存储与该顶点相邻的其他顶点。

邻接表的主要思想是为 每个顶点创建一个链表，链表中的每个节点表示与该顶点相邻的另一个顶点。对于无向图，通常需要为每一条边创建两个链表节点，分别表示两个相邻的顶点。

实现

在邻接表的实现中，我们为每个顶点维护一个链表，用于存储与该顶点相邻的所有顶点；所有顶点对应的 链表头节点 组成一个数组或列表（在以下实现为 struct AdjList *array），形成整个图的邻接表结构。

• 数据结构
• 创建新节点
• 创建图
• 添加边

// 链表节点结构：表示邻接的一个顶点
struct Node {
    int dest;            // 邻接顶点的编号
    struct Node* next;   // 指向下一个邻接点
};

// 邻接表：每个顶点有一个链表
struct AdjList {
    struct Node* head;   // 链表头
};

// 图结构
struct Graph {
    int V;                      // 顶点数
    struct AdjList* array;      // 邻接表数组
};

struct Node* newNode(int dest) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->dest = dest;
    node->next = NULL;
    return node;
}

struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // 创建邻接表数组
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    // src -> dest
    struct Node* n1 = newNode(dest);
    n1->next = graph->array[src].head;
    graph->array[src].head = n1;

    // dest -> src（因为是无向图）
    struct Node* n2 = newNode(src);
    n2->next = graph->array[dest].head;
    graph->array[dest].head = n2;
}

邻接多重表

邻接多重表（Adjacency Multi-list）是一种用于表示 无向图 的数据结构，主要用于避免在 邻接表 存储方式中重复存储 无向边，提高存储效率，同时便于图的操作（如 边 的删除）。

邻接多重表中顶点种类 分为两种：

• 顶点结点（Vertex Node）：
  • 每个顶点有一个头结点，存储该顶点的信息，以及指向其所有关联边的指针。
• 边结点（Edge Node）：
  • 每条边有一个结点，存储该边的两个顶点及其相关信息。
  • 该结点包含两个指针，分别指向该边所连接的两个顶点的邻接边链表的下一条边，使得图的存储更加紧凑。

还是举个实际例子说明，在上述的邻接多重表中，总共需要存储 5 条边，每条边只需要存储一次，所以总共有 5 个边结点，每个边结点中存储的数据如下表所示：

总结一下，相比于邻接表，邻接多重表最大的不同在于如下两点：

• 节省存储空间：对于无向图，每条边只存储一次。
• 方便进行边的操作：例如，删除一条边时，只需要修改相关顶点的链表中的指针，而不需要像邻接表那样在两个顶点的邻接表中都进行操作。

十字链表

十字链表（Orthogonal List）是一种用于表示 有向图 的链式存储结构，它兼顾了 出边 和 入边 的高效查找。相比 邻接表 只方便查找 出边，十字链表 允许同时高效遍历某个顶点的所有出边和所有入边。

在 十字链表（Orthogonal List）中，顶点种类也可以分为两种：

• 顶点结点：
  • 每个顶点对应一个头结点，存储该顶点的信息；
  • 同时包含两个指针：
    • firstout：指向从该顶点出发的第一条出边；
    • firstin：指向以该顶点为终点的第一条入边；
  • 这样可分别建立“出边链表”和“入边链表”。
• 边结点：
  • 每条有向边对应一个边结点，存储该边的起点和终点在顶点表中的位置；
  • 包含两个指针，使该边同时链接在：
    • 起点顶点的出边链表中（通过 hlink）；
    • 终点顶点的入边链表中（通过 tlink）；
  • 边结点也可扩展存储额外信息（如权重）。

下图给出了一个 十字链表 的一个实例，其中忽略了 边结点 的 info 字段。我们可以沿着 顶点结点 的 firstin 和 firstout 字段高效遍历所有的 入边 和 出边。