经典算法解析 – Part 2 – 图算法

欢迎大家来到IT世界,在知识的湖畔探索吧!

上一章我们讲解了4个经典的查找算法（线性查找、二分查找、哈希查找、平衡树查找），今天我们来看下经典图算法以及如何去实现。

首先我们看下图算法有哪些：

• 深度优先搜索算法（Depth First Search）
• 广度优先搜索算法（Breadth First Search）
• 最短路径算法：Dijkstra 算法、Bellman-Ford 算法、Floyd-Warshall 算法
• 最小生成树算法：Prim 算法、Kruskal 算法

深度优先搜索算法

深度优先搜索（Depth First Search, DFS）是一种用于图遍历或状态图搜索的算法。在这个算法中，我们从起始点开始访问，然后继续访问起始点的第一个邻居节点，直到所有的节点都被访问过为止。如果当前节点没有未被访问的邻居节点，则返回到前一个节点并选择它的下一个邻居节点。这个过程继续进行，直到包含起始节点的整个连通区域被访问完成。

下面是DFS的Java实现：

import java.util.ArrayList; import java.util.List; public class DepthFirstSearch { private boolean[] visited; // 标记每个节点是否被访问 private List<List<Integer>> adjacencyList; // 邻接表表示图 public DepthFirstSearch(List<List<Integer>> adjacencyList) { this.visited = new boolean[adjacencyList.size()]; this.adjacencyList = adjacencyList; } public void dfs(int v) { visited[v] = true; System.out.print(v + " "); for (int i = 0; i < adjacencyList.get(v).size(); ++i) { int u = adjacencyList.get(v).get(i); if (!visited[u]) { dfs(u); } } } public static void main(String[] args) { List<List<Integer>> adjacencyList = new ArrayList<>(); // 假设这里有一个6个顶点的无向图，邻接表如下 adjacencyList.add(new ArrayList<Integer>() {{add(1); add(2);}}); adjacencyList.add(new ArrayList<Integer>() {{add(0); add(3); add(4);}}); adjacencyList.add(new ArrayList<Integer>() {{add(0); add(4);}}); adjacencyList.add(new ArrayList<Integer>() {{add(1);}}); adjacencyList.add(new ArrayList<Integer>() {{add(1); add(2);}}); adjacencyList.add(new ArrayList<Integer>()); DepthFirstSearch dfs = new DepthFirstSearch(adjacencyList); dfs.dfs(0); // 从顶点0开始深度优先遍历 } } 

欢迎大家来到IT世界,在知识的湖畔探索吧!

上述代码中通过递归实现了DFS算法，并通过创建 visited 数组来跟踪每个状态的访问情况，在访问每个状态时标记 visited 数组，并将其添加到输出中。

总之，深度优先搜索是一种重要的图遍历算法，可用于寻找任意两个节点之间的路径，也可以用于检查图是否联通。

广度优先搜索算法

广度优先搜索（Breadth-First Search，简称BFS）是一种基于图的遍历算法，从起点开始，依次扩展其相邻节点并添加到队列中，以此类推，直到遍历完成或者找到目标节点。该算法通常使用队列作为辅助数据结构，确保每个节点仅被访问一次。

以下是使用Java实现广度优先搜索算法的代码：

欢迎大家来到IT世界,在知识的湖畔探索吧!import java.util.*; public class BFS { public static void main(String[] args) { // 构建测试用例 int[][] graph = new int[][]{{0, 1, 1, 0, 0}, {1, 0, 0, 1, 1}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 1, 0, 1, 0}}; int start = 0; List<Integer> path = bfs(graph, start); System.out.println(path); } private static List<Integer> bfs(int[][] graph, int start) { List<Integer> path = new ArrayList<>(); Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[graph.length]; visited[start] = true; queue.offer(start); while (!queue.isEmpty()) { int node = queue.poll(); path.add(node); for (int i = 0; i < graph[node].length; i++) { if (graph[node][i] == 1 && !visited[i]) { visited[i] = true; queue.offer(i); } } } return path; } } 

上述代码中，我们首先构建了一个邻接矩阵 graph，代表了一张图。然后使用 bfs 函数进行广度优先搜索，并返回路径 path 。在搜索过程中，我们使用了一个队列 Queue 来保存待遍历节点，并使用一个布尔数组 visited 标记每个节点是否已经被访问过。

由于在广度优先搜索算法中，节点是按照“层次”逐个遍历的，因此最终得到的路径 path 将会是从起点到各个节点的最短路径。

值得注意的是，在搜索过程中，我们需要通过一个 for 循环来遍历与当前节点相邻的所有节点，并将其添加到队列 queue 中，以此执行广度优先搜索。

时间复杂度方面，由于每个节点均被遍历一次，因此时间复杂度为 O(V+E)，其中 V,E 分别代表节点数和边数。

最短路径算法

最短路径问题是在一个带权的有向或无向图中找到从一个顶点到另一顶点的最短路径。解决这个问题的算法有多种，其中最常用的包括Dijkstra、Bellman-Ford和Floyd-Warshall算法。下面是对这三种算法的简要讲解，并给出Java实现。

1. Dijkstra算法

Dijkstra算法解决的是单源最短路径问题，即给定一个源节点，求到其他所有节点的最短路径。它使用了贪心策略，每次扩展距离起始点最近的节点，并更新其周围节点的最短路径。需要注意的是，该算法只适用于边权非负的图。

以下是基于邻接矩阵实现的Dijkstra算法代码：

public class Dijkstra { public static final int INF = Integer.MAX_VALUE; private int[][] graph; private int[] dist; private boolean[] visited; public Dijkstra(int[][] graph) { this.graph = graph; this.dist = new int[graph.length]; this.visited = new boolean[graph.length]; Arrays.fill(dist, INF); dist[0] = 0; } public void solve() { for (int count = 0; count < graph.length - 1; count++) { int u = minDistance(); visited[u] = true; for (int v = 0; v < graph.length; v++) { if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; } } } } private int minDistance() { int minDist = INF; int minIdx = -1; for (int i = 0; i < graph.length; i++) { if (!visited[i] && dist[i] < minDist) { minDist = dist[i]; minIdx = i; } } return minIdx; } } 

2. Bellman-Ford算法

Bellman-Ford算法也用于解决单源最短路径问题，但相比Dijkstra算法，它支持处理带负权边的情形。该算法的主要思想是进行n-1轮松弛操作（即对每条边进行更新），以保证每个节点的最短路径估计值都已经收敛。如果还存在可以缩短的路径，说明图中存在负环。

以下是基于邻接矩阵实现的Bellman-Ford算法代码：

欢迎大家来到IT世界,在知识的湖畔探索吧!public class BellmanFord { public static final int INF = Integer.MAX_VALUE; private int[][] graph; private int[] dist; public BellmanFord(int[][] graph) { this.graph = graph; this.dist = new int[graph.length]; Arrays.fill(dist, INF); dist[0] = 0; } public void solve() { for (int i = 0; i < graph.length - 1; i++) { for (int u = 0; u < graph.length; u++) { for (int v = 0; v < graph.length; v++) { if (dist[u] != INF && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; } } } } for (int u = 0; u < graph.length; u++) { for (int v = 0; v < graph.length; v++) { if (dist[u] != INF && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) { System.out.println("Negative cycle detected"); return; } } } } } 

3. Floyd-Warshall算法

Floyd-Warshall算法是一种用于寻找任意两个顶点之间的最短路径的动态规划算法。目标是寻找从一个顶点到另一个顶点的最短路径长度，可能经过多个顶点（中间顶点可以重复），路径权值为各边权值之和。

该算法使用嵌套循环遍历每个结点对，并在需要时更新邻接矩阵以反映新的最短路径。算法从i到j的路径依次考察每个结点k，如果k使得从i到j的路径长度缩短，则保留k。

以下是Java实现：

public class FloydWarshallAlgorithm { static final int INF = Integer.MAX_VALUE; public void floydWarshall(int graph[][]) { int V = graph.length; int dist[][] = new int[V][V]; int i, j, k; for (i = 0; i < V; i++) for (j = 0; j < V; j++) dist[i][j] = graph[i][j]; for (k = 0; k < V; k++) { for (i = 0; i < V; i++) { for (j = 0; j < V; j++) { if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; } } } printSolution(dist); } void printSolution(int dist[][]) { System.out.println("The following matrix shows the shortest "+ "distances between every pair of vertices"); for (int i=0; i<dist.length; ++i) { for (int j=0; j<dist[0].length; ++j) { if (dist[i][j]==INF) System.out.print("INF "); else System.out.print(dist[i][j]+" "); } System.out.println(); } } public static void main(String[] args) { int graph[][] = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0} }; FloydWarshallAlgorithm a = new FloydWarshallAlgorithm(); a.floydWarshall(graph); } } 

该实现将一个邻接矩阵作为输入并输出所有顶点对之间的最短路径。其中，如果不存在一条路径，则输出INF（无穷大）。时间复杂度为O(n^3)，其中n为图中的节点数。

最小生成树算法

最小生成树算法是求解加权无向图的一种重要算法，它可以找到一个连接所有节点且具有最小总权值的树形子图。其中两种基本算法是Prim算法和Kruskal算法。

1. Prim算法：

首先选择一个顶点作为起始点，将该顶点加入集合U中。
然后依次做出|V|-1次贪心选择，每次从剩余的顶点中，选取与U距离最小的顶点，并将该顶点加入到集合U中。
在每次更新后，需要重新计算新加入节点的邻接点到集合U中所有节点的距离，并选择最短距离作为备选路径。

Prim算法的Java实现代码：

import java.util.Arrays; public class PrimAlgorithm { static final int INF = 0x3f3f3f3f; public static void prim(int[][] graph, int vCount) { int[] dist = new int[vCount]; // 记录距离集合U的距离 int[] parent = new int[vCount]; // 记录父节点 boolean[] visited = new boolean[vCount]; // 记录是否已加入集合U Arrays.fill(dist, INF); Arrays.fill(visited, false); parent[0] = -1; dist[0] = 0; for (int i = 1; i < vCount; i++) { int u = getMinDistIndex(dist, visited); // 找到距离集合U最近的节点 visited[u] = true; // 已加入集合U for (int v = 0; v < vCount; v++) { // 对u的所有邻接点进行松弛（即更新距离） if (!visited[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) { parent[v] = u; dist[v] = graph[u][v]; } } } printMST(dist, parent, vCount); } private static int getMinDistIndex(int[] dist, boolean[] visited) { int minIdx = -1, minDist = INF; for (int i = 0; i < dist.length; i++) { if (!visited[i] && dist[i] < minDist) { minIdx = i; minDist = dist[i]; } } return minIdx; } private static void printMST(int[] dist, int[] parent, int n) { System.out.println("Edge \tWeight"); for (int i = 1; i < n; i++) System.out.println(parent[i] + " - " + i + "\t" + dist[i]); } public static void main(String[] args) { int[][] graph = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; prim(graph, 5); } } 

2. Kruskal算法

Kruskal算法的Java实现：

首先，我们需要定义一个辅助类Edge，用于表示一条边，包括起点vertex1、终点vertex2以及边权重weight。

class Edge implements Comparable<Edge> { int vertex1, vertex2, weight; public int compareTo(Edge compareEdge) { return this.weight - compareEdge.weight; } }; 

接着，我们编写Kruskal算法的代码实现。算法主要有两个步骤：首先对所有边按照权重进行排序，然后依次选取边加入生成树，直到生成树的边数等于总节点数-1或者所有边都已经被考虑过。

import java.util.*; class KruskalMST { int V, E; //图的顶点数和边数 ArrayList<Edge> edgeList; //存储图中所有边的列表 KruskalMST(int v, int e) { this.V = v; this.E = e; edgeList = new ArrayList<>(); } public void addEdge(int u, int v, int w) { //将一条边(u,v,w)加入到边集edgeList中 edgeList.add(new Edge(u, v, w)); } public void kruskalMST() { int[] parent = new int[V]; //用于存储每个节点所在连通分量的代表元素 Arrays.fill(parent, -1); //按照权重从小到大排序 Collections.sort(edgeList); ArrayList<Edge> mst = new ArrayList<>(); int count = 0; //记录生成树的边数 for (int i = 0; i < E; i++) { if (count == V - 1) break; //边数达到最大 Edge currEdge = edgeList.get(i); int vertex1 = currEdge.vertex1; int vertex2 = currEdge.vertex2; //找到vertex1和vertex2所在连通分量的代表元素 int x = find(parent, vertex1); int y = find(parent, vertex2); //判断vertex1和vertex2是否已经在同一个连通分量里面 //如果不在同一个连通分量里面，则将它们合并（注意边的数量+1） if (x != y) { union(parent, x, y); mst.add(currEdge); count++; } } //输出生成树的信息 System.out.println("Minimum Spanning Tree of the graph:"); for (int i = 0; i < count; i++) { System.out.println(mst.get(i).vertex1 + " - " + mst.get(i).vertex2 + ": " + mst.get(i).weight); } } //寻找p节点所在连通分量的代表元素 private int find(int[] parent, int p) { while (parent[p] >= 0) { p = parent[p]; } return p; } //合并x和y所在的连通分量 private void union(int[] parent, int x, int y) { int rootX = find(parent, x); int rootY = find(parent, y); if (rootX == rootY) return; if (parent[rootX] > parent[rootY]) { parent[rootY] += parent[rootX]; parent[rootX] = rootY; } else { parent[rootX] += parent[rootY]; parent[rootY] = rootX; } } } 

以上就是Kruskal算法的Java实现代码。

好了，图算法我们已经讲解完了，下个章节我们分析经典算法 – 字符串匹配算法。