wordpress建立的博客,长沙企业网站优化,网站建设包括哪些项目,免费下载百度软件有向无环图#xff08;DAG#xff09;是一类非常重要的图结构#xff0c;广泛应用于任务调度、数据依赖分析等领域。本文将介绍如何在DAG中实现拓扑排序、单源最短路径和单源最长路径算法#xff0c;并提供完整的Java代码示例。
图结构定义
首先#xff0c;我们定义一个…有向无环图DAG是一类非常重要的图结构广泛应用于任务调度、数据依赖分析等领域。本文将介绍如何在DAG中实现拓扑排序、单源最短路径和单源最长路径算法并提供完整的Java代码示例。
图结构定义
首先我们定义一个简单的图结构包括节点和边。使用Java代码如下
import java.util.*;class Graph {final ListListEdge 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 ListEdge 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 ListInteger sortDFS(Graph graph) {boolean[] visited new boolean[graph.size()];StackInteger stack new Stack();for (int i 0; i graph.size(); i) {if (!visited[i]) {topologicalSortUtil(graph, i, visited, stack);}}ListInteger topoOrder new ArrayList();while (!stack.isEmpty()) {topoOrder.add(stack.pop());}return topoOrder;}private static void topologicalSortUtil(Graph graph, int v, boolean[] visited, StackInteger 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 ListInteger sortBFS(Graph graph) {int[] inDegree new int[graph.size()];for (ListGraph.Edge edges : graph.adjList) {for (Graph.Edge edge : edges) {inDegree[edge.to];}}QueueInteger queue new LinkedList();for (int i 0; i graph.size(); i) {if (inDegree[i] 0) {queue.offer(i);}}ListInteger 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) {ListInteger 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) {ListInteger 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);ListInteger topoOrderDFS TopologicalSort.sortDFS(graph);System.out.println(Topological Sort (DFS): topoOrderDFS);ListInteger 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相关的算法。
