Java数据结构与算法(有向无环图)

前言

有向无环图（Directed Graph）是在有向图的基础上，增加无环的检查。

实现原理

使用邻接表表示法实现有向图相对简单明了，步骤也相对简单。

1:首先创建有向图

2.创建顶点

3.顶点间创建边

4.创建边的过程中检查节点是否存在环，每个节点的检查采用递归。

具体代码实现

package test13;import java.util.*;public class DAG {private Map<Vertex, List<Vertex>> adjacencyList;public DAG() {this.adjacencyList = new HashMap<>();}// 添加顶点public void addVertex(String label) {adjacencyList.putIfAbsent(new Vertex(label), new ArrayList<>());}// 添加边并检查是否会形成环public boolean addEdge(String sourceLabel, String destinationLabel) {Vertex source = new Vertex(sourceLabel);Vertex destination = new Vertex(destinationLabel);if (!adjacencyList.containsKey(source) || !adjacencyList.containsKey(destination)) {throw new IllegalArgumentException("顶点不存在");}adjacencyList.get(source).add(destination);// 检查是否形成环if (hasCycle()) {adjacencyList.get(source).remove(destination);return false;}return true;}// 深度优先搜索检查环private boolean hasCycle() {Set<Vertex> visited = new HashSet<>();Set<Vertex> recursionStack = new HashSet<>();for (Vertex vertex : adjacencyList.keySet()) {if (hasCycleUtil(vertex, visited, recursionStack)) {return true;}}return false;}private boolean hasCycleUtil(Vertex vertex, Set<Vertex> visited, Set<Vertex> recursionStack) {if (recursionStack.contains(vertex)) {return true;}if (visited.contains(vertex)) {return false;}visited.add(vertex);recursionStack.add(vertex);for (Vertex neighbor : adjacencyList.get(vertex)) {if (hasCycleUtil(neighbor, visited, recursionStack)) {return true;}}recursionStack.remove(vertex);return false;}// 拓扑排序public List<Vertex> topologicalSort() {Set<Vertex> visited = new HashSet<>();Stack<Vertex> stack = new Stack<>();for (Vertex vertex : adjacencyList.keySet()) {if (!visited.contains(vertex)) {topologicalSortUtil(vertex, visited, stack);}}List<Vertex> sortedList = new ArrayList<>();while (!stack.isEmpty()) {sortedList.add(stack.pop());}return sortedList;}private void topologicalSortUtil(Vertex vertex, Set<Vertex> visited, Stack<Vertex> stack) {visited.add(vertex);for (Vertex neighbor : adjacencyList.get(vertex)) {if (!visited.contains(neighbor)) {topologicalSortUtil(neighbor, visited, stack);}}stack.push(vertex);}// 打印图的顶点和边public void printGraph() {for (Map.Entry<Vertex, List<Vertex>> entry : adjacencyList.entrySet()) {System.out.print(entry.getKey() + " -> ");for (Vertex vertex : entry.getValue()) {System.out.print(vertex + " ");}System.out.println();}}public static void main(String[] args) {DAG graph = new DAG();graph.addVertex("A");graph.addVertex("B");graph.addVertex("C");graph.addVertex("D");graph.addEdge("A", "B");graph.addEdge("A", "C");graph.addEdge("B", "D");graph.addEdge("C", "D");graph.addEdge("B", "A");System.out.println("图的顶点和边:");graph.printGraph();System.out.println("\n拓扑排序:");List<Vertex> sortedList = graph.topologicalSort();for (Vertex vertex : sortedList) {System.out.print(vertex + " ");}}
}

QA:待定