有向无环图（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;
}
@Override
public 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
}
}
比较两种拓扑排序算法
DFS拓扑排序：
- 优点：实现简单，递归方式直观，适用于大部分编程场景。
- 缺点：需要使用额外的栈空间，可能导致栈溢出问题。
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 = Shortest
PathDAG.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相关的算法。
