图的部分基础概念

完全图边数

1. 无向图

对于无向图 $G=(V,E)$，若任意两个顶点之间都有一条边相连，这种图被称为完全图。

边的数量推导

• 图中有 $|V|$ 个顶点。
• 任意两个顶点之间都有一条边相连，选两个顶点的方法总共有：
  $$(\genfrac{}{}{0ex}{}{|V|}{2})=\frac{|V|(|V|-1)}{2}$$
• 因此，完全图的边数为：
  $$|E|=\frac{|V|(|V|-1)}{2}$$
• 当且仅当边数达到这个值时，说明每一对顶点之间都有边相连，图才是完全图。

举例

假设图中有 4 个顶点 {A, B, C, D} ，选两个顶点的所有可能方法为：

• (A, B), (A, C), (A, D)
• (B, C), (B, D)
• (C, D)

这些组合一共 6 种，数量可以用组合公式计算：
$$C_2^{|V|}=\frac{|V|(|V|-1)}{2}$$

2. 有向图

对于有向图 $G=(V,E)$，若任意两个顶点之间都有一条方向不同的有向边（即 $u\to v$ 和 $v\to u$），这种图被称为完全有向图。

边的数量推导

• 图中有 $|V|$ 个顶点。
• 对于任意两个顶点 $u$ 和 $v$：
  • $u\to v$ 是一条有向边。
  • $v\to u$ 是另一条有向边。
• 每一对顶点之间都有两条方向相反的有向边，且顶点对的总数为 $|V|(|V|-1)$（排列方式，顺序不同的对算作不同）。
• 因此，完全有向图的边数为：
  $$|E|=|V|(|V|-1)$$

当且仅当边数达到这个值时，说明任意两点之间都有方向不同的有向边，图才是完全有向图。

举例

假设图中有 4 个顶点 {A, B, C, D} ，从中选两个顶点并赋予方向，所有可能的方法为：

• 从 A 指向 B ： (A, B)
• 从 B 指向 A ： (B, A)

对于每一对顶点，都会生成两个有向边。因此，从 |V| 个顶点中挑选两个顶点并考虑方向的总数为排列公式：
$$A_2^{|V|}=|V|\cdot (|V|-1)$$

总结

1. 无向图：完全图的边数为 $|E|=\frac{|V|(|V|-1)}{2}$。
2. 有向图：完全有向图的边数为 $|E|=|V|(|V|-1)$。

原因在于组合（无向图）与排列（有向图）的不同。

图的存储

邻接矩阵

https://www.lddgo.net/chart/character-relationship

定义

邻接矩阵（Adjacency Matrix）是表示图（无向图或有向图）的一种常用方式，使用一个矩阵来描述顶点与顶点之间的连接关系。

• 给定一个图 $G=(V,E)$，其中 $|V|=n$（顶点数为 $n$），邻接矩阵是一个 $n\times n$ 的方阵 $A$。
• 矩阵中的每个元素 $A[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 是否有边存在：
  • 无向图：若顶点 $i$ 和 $j$ 之间有边，则 $A[i][j]=1$（或权值）；否则 $A[i][j]=0$。
  • 有向图：若存在从顶点 $i$ 指向顶点 $j$ 的边，则 $A[i][j]=1$（或权值）；否则 $A[i][j]=0$。

---

邻接矩阵的构造

1. 无权图

• 无向图：$A[i][j]=1$ 表示顶点 $i$ 和 $j$ 之间有边。
• 有向图：$A[i][j]=1$ 表示存在从顶点 $i$ 指向顶点 $j$ 的有向边。

2. 带权图

• 无向图：$A[i][j]$ 存储顶点 $i$ 和 $j$ 之间的权值。
• 有向图：$A[i][j]$ 存储从顶点 $i$ 到顶点 $j$ 的权值。
• 若无边连接，则 $A[i][j]=0$ 或 $A[i][j]=\mathrm{\infty }$（表示不可达）。

---

邻接矩阵的例子

1. 无向无权图

假设有 4 个顶点 $V=A,B,C,D$，边集 $E=(A,B),(B,C),(C,D)$。

邻接矩阵如下：
$$A=\left[\begin{array}{ccccccccccccc}0& 1& 0& 01& 0& 1& 00& 1& 0& 10& 0& 1& 0\end{array}\right]$$

• $A[1][2]=1$ 表示顶点 $A$ 和 $B$ 相连。
• 矩阵是对称的，因为这是一个无向图。

---

2. 有向图

假设有 4 个顶点 $V=A,B,C,D$，边集 $E=(A,B),(B,C),(C,A)$。

邻接矩阵如下：
$$A=\left[\begin{array}{ccccccccccccc}0& 1& 0& 00& 0& 1& 01& 0& 0& 00& 0& 0& 0\end{array}\right]$$

• $A[1][2]=1$ 表示存在从 $A$ 到 $B$ 的边。
• $A[3][1]=1$ 表示存在从 $C$ 到 $A$ 的边。
• 矩阵不对称，因为边是有方向的。

---

邻接矩阵的特点

优点

1. 表示清晰，适合进行快速查询：判断两顶点是否相连只需 $O(1)$ 时间。
2. 易于实现图相关的算法，例如求最短路径或最小生成树。

缺点

1. 空间复杂度高：需要 $O(n^2)$ 的存储空间，即使是稀疏图（边较少的图）。
2. 不适合稀疏图：对于顶点很多但边很少的图，邻接矩阵会浪费大量空间。

---

邻接矩阵的应用

1. 图的遍历：如深度优先搜索（DFS）和广度优先搜索（BFS）。
2. 图的算法：如 Floyd-Warshall 算法、Dijkstra 算法等求最短路径问题。
3. 快速判断顶点连接性：通过矩阵快速判断顶点间是否有边。

邻接矩阵是一种常用的图表示方式，但对于稀疏图，更适合使用邻接表来节省空间。

邻接表

定义

邻接表（Adjacency List）是一种表示图（无向图或有向图）的常用方式，用于描述顶点与顶点之间的连接关系。
邻接表通过为每个顶点维护一个链表（或数组）来存储与之相连的其他顶点信息。

• 给定一个图 $G=(V,E)$，其中 $|V|=n$（顶点数为 $n$）。
• 邻接表使用一个大小为 $n$ 的数组，其中每个元素对应一个顶点，其值为与该顶点相邻的顶点集合。

邻接表的处理方法是这样的。

1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。

---

邻接表的构造

1. 无权图

• 无向图：若顶点 $i$ 和顶点 $j$ 之间有边，则将 $j$ 加入顶点 $i$ 的邻接链表中，同时将 $i$ 加入顶点 $j$ 的邻接链表中。
• 有向图：若存在从顶点 $i$ 指向顶点 $j$ 的边，则将 $j$ 加入顶点 $i$ 的邻接链表中。

2. 带权图

• 无向图：每个链表节点存储一个二元组 $(j,w)$，其中 $j$ 为相邻顶点，$w$ 为权值。
• 有向图：每个链表节点存储一个二元组 $(j,w)$，表示从顶点 $i$ 指向顶点 $j$ 的边权值为 $w$。

---

邻接表的例子

1. 无向无权图

2. 有向无权图

3. 带权图

---

邻接表的特点

优点

1. 节省空间：邻接表的存储复杂度为 $O(V+E)$，对于稀疏图（边较少的图）非常高效。
2. 灵活性高：添加或删除边操作简单，适合动态图的操作。

缺点

1. 查询效率较低：判断两顶点是否相连需要遍历链表，时间复杂度为 $O(\text{链表长度})$。
2. 不适合密集图：对于边较多的图，邻接表会增加复杂度。

---

邻接表的应用

1. 图的遍历：如深度优先搜索（DFS）和广度优先搜索（BFS）。
2. 动态图的处理：如频繁插入或删除边的场景。
3. 稀疏图的存储：在顶点数远大于边数时，邻接表是更高效的存储方式。

---

邻接表与邻接矩阵的比较

特性	邻接矩阵	邻接表
空间复杂度	$O(V^2)$	$O(V+E)$
查询效率	$O(1)$	$O(\text{链表长度})$
插入效率	$O(1)$（修改矩阵）	$O(1)$（修改链表）
适用场景	密集图	稀疏图