在有向无环图（DAG）中实现拓扑排序与最短路径和最长路径算法

有向无环图（DAG）是一类非常重要的图结构，广泛应用于任务调度、数据依赖分析等领域。本文将介绍如何在DAG中实现拓扑排序、单源最短路径和单源最长路径算法，并提供完整的Java代码示例。

图结构定义

首先，我们定义一个简单的图结构，包括节点和边。使用Java代码如下：

import java.util.*;class Graph {final List<List<Edge>> adjList;public Graph(int vertices) {adjList = new ArrayList<>(vertices);for (int i = 0; i < vertices; i++) {adjList.add(new ArrayList<>());}}public void addEdge(int from, int to, int weight) {adjList.get(from).add(new Edge(from, to, weight));}public List<Edge> getEdges(int vertex) {return adjList.get(vertex);}public int size() {return adjList.size();}static class Edge {final int from;final int to;final int weight;Edge(int from, int to, int weight) {this.from = from;this.to = to;this.weight = weight;}@Overridepublic String toString() {return String.format("%d - %d: %d", from, to, weight);}}
}

拓扑排序算法

拓扑排序是DAG中非常基础且重要的算法。它为每个节点排列顺序，使得所有有向边从前往后指向。这里我们介绍两种拓扑排序算法：基于DFS和基于BFS的算法。

基于DFS的拓扑排序

import java.util.*;class TopologicalSort {public static List<Integer> sortDFS(Graph graph) {boolean[] visited = new boolean[graph.size()];Stack<Integer> stack = new Stack<>();for (int i = 0; i < graph.size(); i++) {if (!visited[i]) {topologicalSortUtil(graph, i, visited, stack);}}List<Integer> topoOrder = new ArrayList<>();while (!stack.isEmpty()) {topoOrder.add(stack.pop());}return topoOrder;}private static void topologicalSortUtil(Graph graph, int v, boolean[] visited, Stack<Integer> stack) {visited[v] = true;for (Graph.Edge edge : graph.getEdges(v)) {if (!visited[edge.to]) {topologicalSortUtil(graph, edge.to, visited, stack);}}stack.push(v);}
}

基于BFS的拓扑排序

import java.util.*;class TopologicalSort {public static List<Integer> sortBFS(Graph graph) {int[] inDegree = new int[graph.size()];for (List<Graph.Edge> edges : graph.adjList) {for (Graph.Edge edge : edges) {inDegree[edge.to]++;}}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < graph.size(); i++) {if (inDegree[i] == 0) {queue.offer(i);}}List<Integer> topoOrder = new ArrayList<>();while (!queue.isEmpty()) {int v = queue.poll();topoOrder.add(v);for (Graph.Edge edge : graph.getEdges(v)) {if (--inDegree[edge.to] == 0) {queue.offer(edge.to);}}}return topoOrder.size() == graph.size() ? topoOrder : new ArrayList<>(); // Check for cycle}
}

比较两种拓扑排序算法

1. DFS拓扑排序：

   • 优点：实现简单，递归方式直观，适用于大部分编程场景。
   • 缺点：需要使用额外的栈空间，可能导致栈溢出问题。

2. BFS拓扑排序（Kahn’s Algorithm）：

   • 优点：使用队列实现，避免了递归带来的栈空间问题。能有效检测图中的环。
   • 缺点：实现稍微复杂，需要额外的入度数组。

基于拓扑排序的DAG单源最短路径算法

DAG中的单源最短路径算法可以利用拓扑排序来实现。由于DAG中不存在环，可以按照拓扑顺序依次松弛每个节点的边，从而实现单源最短路径。

import java.util.*;class ShortestPathDAG {public static int[] shortestPath(Graph graph, int start) {List<Integer> topoOrder = TopologicalSort.sortDFS(graph);int[] distTo = new int[graph.size()];Arrays.fill(distTo, Integer.MAX_VALUE);distTo[start] = 0;for (int v : topoOrder) {if (distTo[v] != Integer.MAX_VALUE) {for (Graph.Edge edge : graph.getEdges(v)) {if (distTo[v] + edge.weight < distTo[edge.to]) {distTo[edge.to] = distTo[v] + edge.weight;}}}}return distTo;}
}

最短路径算法与Dijkstra算法的优劣性比较

• 优点：

  • 拓扑排序+最短路径算法在DAG中效率高，可以在线性时间内解决最短路径问题。
  • 对于DAG来说，算法实现相对简单。

• 缺点：

  • 仅适用于DAG，对于有环图无效。
  • Dijkstra算法适用于任意有向图和无向图，且能处理正权边的最短路径问题。

基于拓扑排序的DAG单源最长路径算法

方法1：使用图的副本和最短路径算法

import java.util.*;class LongestPathDAG {public static int[] longestPathWithNegation(Graph graph, int start) {Graph negatedGraph = new Graph(graph.size());for (int i = 0; i < graph.size(); i++) {for (Graph.Edge edge : graph.getEdges(i)) {negatedGraph.addEdge(edge.from, edge.to, -edge.weight);}}int[] negatedDistances = ShortestPathDAG.shortestPath(negatedGraph, start);int[] distances = new int[graph.size()];for (int i = 0; i < negatedDistances.length; i++) {distances[i] = -negatedDistances[i];}return distances;}
}

方法2：直接修改最短路径算法

import java.util.*;class LongestPathDAG {public static int[] longestPathDirect(Graph graph, int start) {List<Integer> topoOrder = TopologicalSort.sortDFS(graph);int[] distTo = new int[graph.size()];Arrays.fill(distTo, Integer.MIN_VALUE);distTo[start] = 0;for (int v : topoOrder) {if (distTo[v] != Integer.MIN_VALUE) {for (Graph.Edge edge : graph.getEdges(v)) {if (distTo[v] + edge.weight > distTo[edge.to]) {distTo[edge.to] = distTo[v] + edge.weight;}}}}return distTo;}
}

比较两种单源最长路径算法

• 使用图的副本和最短路径算法：

  • 优点：利用现有的最短路径算法作为黑箱，方便直接调用。
  • 缺点：需要额外创建图的副本，增加了时间和空间复杂度。

• 直接修改最短路径算法：

  • 优点：无需额外的图副本，算法效率更高，直接适用于最长路径问题。
  • 缺点：实现稍微复杂，需要对算法进行适当调整。

主类（用于测试）

public class Main {public static void main(String[] args) {Graph graph = new Graph(6);graph.addEdge(0, 1, 5);graph.addEdge(0, 2, 3);graph.addEdge(1, 3, 6);graph.addEdge(1, 2, 2);graph.addEdge(2, 4, 4);graph.addEdge(2, 5, 2);graph.addEdge(2, 3, 7);graph.addEdge(3, 4, -1);graph.addEdge(3, 5, 1);graph.addEdge(4, 5, -2);List<Integer> topoOrderDFS = TopologicalSort.sortDFS(graph);System.out.println("Topological Sort (DFS): " + topoOrderDFS);List<Integer> topoOrderBFS = TopologicalSort.sortBFS(graph);System.out.println("Topological Sort (BFS): " + topoOrderBFS);int[] shortestPaths = ShortestPathDAG.shortestPath(graph, 0);System.out.println("Shortest Paths from vertex 0: " + Arrays.toString(shortestPaths));int[] longestPathsNegation = LongestPathDAG.longestPathWithNegation(graph, 0);System.out.println("Longest Paths from vertex 0 (with negation): " + Arrays.toString(longestPathsNegation));int[] longestPathsDirect = LongestPathDAG.longestPathDirect(graph, 0);System.out.println("Longest Paths from vertex 0 (direct method): " + Arrays.toString(longestPathsDirect));}
}

总结

本文介绍了在有向无环图（DAG）中实现拓扑排序、单源最短路径和单源最长路径算法的详细步骤和Java代码。通过比较不同的拓扑排序方法和最长路径算法，我们可以根据实际需求选择最适合的实现方案。希望这些内容能帮助读者更好地理解和应用DAG相关的算法。