当前位置：首页 > news >正文

数据结构 - 图

news 来源：原创 2024/7/7 8:20:50

图（Graph）是由节点（Vertex）和边（Edge）组成的一种数据结构，用于描述不同事物之间的关系。图的算法涉及到图的遍历、最短路径、最小生成树等多个方面，下面简要介绍几种常见的图相关算法：

图的表示方式：
- 邻接矩阵：使用二维数组表示节点之间的连接关系，适合稠密图。
- 邻接表：使用链表或数组列表表示节点和相邻节点的连接关系，适合稀疏图。
图的遍历：
- 深度优先搜索（DFS）：从起始节点开始，沿着路径直到末端，然后回溯到上一个节点，继续探索未访问的路径。
- 广度优先搜索（BFS）：从起始节点开始，先访问所有与该节点相邻的节点，然后依次访问这些节点的邻居节点，层层递进，直到所有节点均被访问。
最短路径算法：
- Dijkstra算法：用于计算带权重图中单源最短路径的算法，通过贪心法和逐步扩展已找到的最短路径集合来实现。
- Bellman-Ford算法：适用于计算带有负权重边的图的单源最短路径，通过重复减少可能的最短路径集合来实现。
最小生成树算法：
- Prim算法：基于贪心策略，从一个节点开始逐步扩展，选择连接已包含节点和未包含节点的最小权重边。
- Kruskal算法：将所有边按权重排序，然后逐个加入到最小生成树中，保证不形成环路。
拓扑排序：
- 拓扑排序：适用于有向无环图（DAG），一种将图中所有节点线性排序的算法，使得对于每一对有向边 u -> v，均有 u 在排序列表中排在 v 的前面。
关键路径算法：
- 关键路径法：用于确定项目的最短时间完成路径，依赖于图的拓扑排序和任务的持续时间。

图的算法在实际应用中涵盖了广泛的领域，如网络路由、社交网络分析、推荐系统等。选择合适的图算法取决于图的类型（有向图、无向图、带权重图等）和具体的问题需求。

当谈论图的表示方式时，具体的例子可以帮助更好地理解不同表示方式的应用场景和优缺点。

图的表示方式

1. 邻接矩阵 (Adjacency Matrix)

假设我们有以下简单的无向图：

   A/   \
B --- C

使用邻接矩阵表示该图：

节点集合：( {A, B, C} )
邻接矩阵：

在邻接矩阵中：

( M[i][j] = 1 ) 表示节点 ( i ) 与节点 ( j ) 之间有边。
( M[i][j] = 0 ) 表示节点 ( i ) 与节点 ( j ) 之间无边。

优点：

快速判断任意一对节点之间是否有边，时间复杂度 ( O(1) )。
适用于稠密图，节省空间。

缺点：

对于稀疏图，会浪费大量空间。
添加或删除节点的操作复杂度高，为 ( O(V^2) )。

2. 邻接表 (Adjacency List)

继续使用上述无向图的例子，使用邻接表表示该图：

邻接表：

A -> B, C
B -> A, C
C -> A, B

在邻接表中：

每个节点 ( A, B, C ) 分别指向与其相邻的节点列表。

优点：

适用于稀疏图，节省空间。
添加或删除节点的操作简单，时间复杂度 ( O(1) ) 或 ( O(d) )，其中 ( d ) 是相邻节点的数量。

缺点：

查询任意一对节点之间是否有边的效率较低，需要遍历链表或列表，时间复杂度取决于相邻节点的数量 ( O(d) )。

应用场景选择：

如果我们知道图是密集的，即边的数量接近 ( V^2 )，邻接矩阵更为适合，因为可以快速判断边的存在。
如果图是稀疏的，即边的数量远小于 ( V^2 )，邻接表更为适合，因为节省空间且支持高效的节点添加和删除操作。

这些例子希望能够帮助理解图的不同表示方式的实际应用和选择。

图的遍历方式

图的遍历是指按照一定规则访问图中所有节点的过程。常见的图遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。这两种算法在图的结构上有不同的特点和应用场景。

1. 深度优先搜索（DFS）

深度优先搜索从图的某个起始节点出发，沿着一条路径尽可能深地访问，直到该路径上所有节点都被访问过，然后回溯到上一个节点，继续探索未访问的路径。

实现过程：

使用递归（或栈）来实现深度优先搜索。
标记访问过的节点，防止重复访问，通常使用布尔数组（visited）。
遍历邻接节点：
- 对于当前节点，依次访问其未被访问过的邻接节点。
- 对每个邻接节点，递归调用DFS函数。

示例：

考虑以下无向图的邻接表表示：

A -> B, C
B -> A, C, D
C -> A, B, E
D -> B
E -> C

从节点 A 出发的深度优先搜索过程：

访问顺序：A -> B -> C -> E -> D

代码示例（Java）：

import java.util.*;class Graph {private int V; // 节点数private LinkedList<Integer> adj[]; // 邻接表Graph(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}void addEdge(int v, int w) {adj[v].add(w);}void DFSUtil(int v, boolean visited[]) {visited[v] = true;System.out.print(v + " ");Iterator<Integer> i = adj[v].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n])DFSUtil(n, visited);}}void DFS(int v) {boolean visited[] = new boolean[V];DFSUtil(v, visited);}public static void main(String args[]) {Graph g = new Graph(5);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(2, 4);System.out.println("从节点 0 开始的 DFS 遍历：");g.DFS(0);}
}

2. 广度优先搜索（BFS）

广度优先搜索从图的某个起始节点出发，首先访问该节点的所有未访问邻接节点，然后逐层向外扩展，直到所有可达节点都被访问。

实现过程：

使用队列来实现广度优先搜索。
标记访问过的节点，防止重复访问，通常使用布尔数组（visited）。
遍历邻接节点：
- 对于当前节点，依次访问其未被访问过的邻接节点。
- 将每个邻接节点加入队列，并标记为已访问。

示例：

继续考虑上述无向图的邻接表表示，从节点 A 出发的广度优先搜索过程：

访问顺序：A -> B -> C -> D -> E

代码示例（Java）：

import java.util.*;class Graph {private int V; // 节点数private LinkedList<Integer> adj[]; // 邻接表Graph(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList();}void addEdge(int v, int w) {adj[v].add(w);}void BFS(int s) {boolean visited[] = new boolean[V];LinkedList<Integer> queue = new LinkedList<>();visited[s] = true;queue.add(s);while (queue.size() != 0) {s = queue.poll();System.out.print(s + " ");Iterator<Integer> i = adj[s].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n]) {visited[n] = true;queue.add(n);}}}}public static void main(String args[]) {Graph g = new Graph(5);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(2, 4);System.out.println("从节点 0 开始的 BFS 遍历：");g.BFS(0);}
}