非线性数据结构之图
一、无环图（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) | 适合表达依赖关系，可拓扑排序 | 验证无环性复杂 | 任务调度、数据流分析 |
原文地址：https://blog.csdn.net/m0_61840987/article/details/143476032
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！