一、无环图（Acyclic Graph）
1. 定义
无环图是一种没有环路的图，图中的路径不会形成封闭回路。如果无环图是有向的，则称为 有向无环图（DAG, Directed Acyclic Graph）。
2. 特点
- 无环性：无环图中不存在任何顶点能通过一系列边回到自身的路径。
- 拓扑结构：有向无环图可以进行拓扑排序，将图中的所有顶点线性排序，使得对于每条边 u→v，顶点 u 在 v 之前。
- 有向无环图（DAG）：有向图中没有任何循环的子图。
- 无向无环图：若是无向图，则无环图为树或森林。
3. 优缺点
- 优点：
- DAG 支持拓扑排序，适合表达依赖关系。
- 在算法中常用于流程管理，如任务调度、编译器中的依赖图。
- 缺点：
- 图的构建和验证无环性相对复杂。
- 无法表达循环依赖或重复路径。
4. 应用场景
- 任务调度：表示任务及其依赖关系，确保任务按正确顺序执行。
- 数据流分析：分析和优化数据流，确保无循环依赖。
- 版本控制：Git 等版本控制系统使用 DAG 表示分支和合并。
5. 示例
DAG 示例：
该图表示任务 A 完成后可以进行任务 B 和 D，而 C 需要在 B 完成后执行。
示例代码（Java 实现检测 DAG）
import java.util.*;class Graph {private Map<String, List<String>> adjacencyList;public Graph() {adjacencyList = new HashMap<>();}public void addVertex(String vertex) {adjacencyList.putIfAbsent(vertex, new ArrayList<>());}public void addEdge(String from, String to) {adjacencyList.putIfAbsent(from, new ArrayList<>());adjacencyList.putIfAbsent(to, new ArrayList<>());adjacencyList.get(from).add(to);}public boolean isDAG() {Set<String> visited = new HashSet<>();Set<String> recStack = new HashSet<>();for (String vertex : adjacencyList.keySet()) {if (isCyclic(vertex, visited, recStack)) {return false;}}return true;}private boolean isCyclic(String vertex, Set<String> visited, Set<String> recStack) {if (recStack.contains(vertex)) {return true;}if (visited.contains(vertex)) {return false;}visited.add(vertex);recStack.add(vertex);for (String neighbor : adjacencyList.get(vertex)) {if (isCyclic(neighbor, visited, recStack)) {return true;}}recStack.remove(vertex);return false;}
}
二、邻接矩阵（Adjacency Matrix）
1. 定义
邻接矩阵是图的表示方式之一，用一个二维数组来存储图中顶点之间的连接关系。矩阵的行和列代表图的顶点，数组元素表示对应顶点之间是否存在边。
2. 特点
- 大小：对于有 n 个顶点的图，邻接矩阵的大小为 n×n。
- 元素表示：
- 在无权图中，元素为 0 或 1，表示有无边。
- 在加权图中，元素为边的权重或无穷大（表示无边）。
3. 优缺点
- 优点：
- 查询高效：判断顶点之间是否存在边的时间复杂度为 O(1)。
- 简单直观：适合存储稠密图（边多的图）。
- 缺点：
- 空间复杂度高：需要 O(n2) 的空间，即使图较稀疏。
- 添加和删除顶点不便：需要重新调整矩阵。
4. 应用场景
- 网络图：存储所有可能的连接关系，如网络拓扑结构。
- 图论算法：如 Floyd-Warshall 算法求任意两点间的最短路径。
5. 示例
邻接矩阵表示如下图：
邻接矩阵表示：
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
示例代码（Java 实现邻接矩阵）
class AdjacencyMatrixGraph {private int[][] matrix;private int numVertices;public AdjacencyMatrixGraph(int numVertices) {this.numVertices = numVertices;matrix = new int[numVertices][numVertices];}public void addEdge(int i, int j) {matrix[i][j] = 1;matrix[j][i] = 1; // 无向图}public boolean hasEdge(int i, int j) {return matrix[i][j] != 0;}
}
三、邻接表（Adjacency List）
1. 定义
邻接表是另一种图的表示方式，使用链表或数组列表来存储每个顶点的邻居。每个顶点维护一个列表，包含它所连接的所有其他顶点。
2. 特点
- 存储灵活：根据每个顶点的度数，所需的存储空间不同。
- 空间高效：对于稀疏图（边少的图）更节省空间，所需空间为 O(V+E)。
- 动态性强：添加和删除边和顶点相对简单。
3. 优缺点
- 优点：
- 空间节省：适合稀疏图。
- 动态操作方便：容易添加和删除边。
- 缺点：
- 查询效率低：判断是否存在边的时间复杂度为 O(k)，其中 k 是顶点的度数。
- 实现稍复杂：相比邻接矩阵，结构更复杂。
4. 应用场景
- 社交网络：表示用户和用户之间的朋友关系。
- 图遍历：如广度优先搜索（BFS）和深度优先搜索（DFS）中经常使用。
5. 示例
邻接表表示如下图：
邻接表表示：
import java.util.*;class AdjacencyListGraph {private Map<Integer, List<Integer>> adjacencyList;public AdjacencyListGraph() {adjacencyList = new HashMap<>();}public void addVertex(int vertex) {adjacencyList.putIfAbsent(vertex, new ArrayList<>());}public void addEdge(int vertex1, int vertex2) {adjacencyList.get(vertex1).add(vertex2);adjacencyList.get(vertex2).add(vertex1); // 无向图}public List<Integer> getNeighbors(int vertex) {return adjacencyList.get(vertex);}
}
总结比较
| 表示方式 | 优点 | 缺点 | 应用场景 |
|---|---|---|---|
| 邻接矩阵 | 查询边存在性快（O(1)），结构简单 | 空间复杂度高（O(n^2)），稀疏图不高效 | 稠密图、网络结构 |
| 邻接表 | 空间效率高（O(V + E)），适合动态操作 | 查询边存在性慢（O(k)） | 稀疏图、社交网络 |
| 无环图 (DAG) | 适合表达依赖关系，可拓扑排序 | 验证无环性复杂 | 任务调度、数据流分析 |
