做网站运营有提成吗,资源下载网站源码,wordpress无法访问,WordPress开发过程前言
有向无环图#xff08;Directed Graph#xff09;是在有向图的基础上#xff0c;增加无环的检查。
实现原理
使用邻接表表示法实现有向图相对简单明了#xff0c;步骤也相对简单。
1:首先创建有向图
2.创建顶点
3.顶点间创建边
4.创建边的过程中检查节点是否存…前言
有向无环图Directed Graph是在有向图的基础上增加无环的检查。
实现原理
使用邻接表表示法实现有向图相对简单明了步骤也相对简单。
1:首先创建有向图
2.创建顶点
3.顶点间创建边
4.创建边的过程中检查节点是否存在环每个节点的检查采用递归。
具体代码实现
package test13;import java.util.*;public class DAG {private MapVertex, ListVertex 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() {SetVertex visited new HashSet();SetVertex recursionStack new HashSet();for (Vertex vertex : adjacencyList.keySet()) {if (hasCycleUtil(vertex, visited, recursionStack)) {return true;}}return false;}private boolean hasCycleUtil(Vertex vertex, SetVertex visited, SetVertex 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 ListVertex topologicalSort() {SetVertex visited new HashSet();StackVertex stack new Stack();for (Vertex vertex : adjacencyList.keySet()) {if (!visited.contains(vertex)) {topologicalSortUtil(vertex, visited, stack);}}ListVertex sortedList new ArrayList();while (!stack.isEmpty()) {sortedList.add(stack.pop());}return sortedList;}private void topologicalSortUtil(Vertex vertex, SetVertex visited, StackVertex 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.EntryVertex, ListVertex 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拓扑排序:);ListVertex sortedList graph.topologicalSort();for (Vertex vertex : sortedList) {System.out.print(vertex );}}
}QA:待定
