Java uses JGraphT for depth first traversal, breadth first traversal, and Topological sorting
In Java, you can use the JGraphT library to implement depth first traversal, breadth first traversal, and Topological sorting of graphs. JGraphT is an open source Java graph library that provides rich graph algorithms and data structures. It supports multiple types of graphs, including directed graphs, undirected graphs, weighted graphs, etc., and provides many tools and algorithms for graph operations. The following are the Maven coordinates and a brief introduction of the JGraphT library:
Maven coordinates:
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.5.1</version>
</dependency>
The JGraphT library mainly includes the following features:
1. Support multiple graph types: directed graph, undirected graph, weighted graph, etc.
2. It provides rich graph algorithms and data structures: Depth-first search, Breadth-first search, Topological sorting, shortest path, Minimum spanning tree, etc.
3. Support custom vertex and edge data types.
4. Provided visualization tools and interfaces.
The following is a complete Java code example, demonstrating how to use the JGraphT library to perform depth first traversal, breadth first traversal, and Topological sorting of graphs:
import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.interfaces.VertexTraversalListener;
import org.jgrapht.alg.interfaces.VertexTraversalEvent;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.traverse.BreadthFirstIterator;
import org.jgrapht.traverse.DepthFirstIterator;
import org.jgrapht.traverse.TopologicalOrderIterator;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
//Create a directed graph
Graph<String, DefaultEdge> directedGraph = new DefaultDirectedGraph<>(DefaultEdge.class);
directedGraph.addVertex("A");
directedGraph.addVertex("B");
directedGraph.addVertex("C");
directedGraph.addVertex("D");
directedGraph.addVertex("E");
directedGraph.addEdge("A", "B");
directedGraph.addEdge("A", "C");
directedGraph.addEdge("B", "C");
directedGraph.addEdge("C", "D");
directedGraph.addEdge("D", "E");
//Depth First Traverse
System. out. println ("depth first traversal");
DepthFirstIterator<String, DefaultEdge> dfsIterator = new DepthFirstIterator<>(directedGraph);
while (dfsIterator.hasNext()) {
String vertex = dfsIterator.next();
System.out.println(vertex);
}
//Breadth First Traverse
System. out. println ("breadth first traversal");
BreadthFirstIterator<String, DefaultEdge> bfsIterator = new BreadthFirstIterator<>(directedGraph);
while (bfsIterator.hasNext()) {
String vertex = bfsIterator.next();
System.out.println(vertex);
}
//Topological sorting
System. out. println ("Topological sorting");
TopologicalOrderIterator<String, DefaultEdge> topoIterator =
new TopologicalOrderIterator<>(directedGraph);
while (topoIterator.hasNext()) {
String vertex = topoIterator.next();
System.out.println(vertex);
}
}
}
Running the above code will output the following results:
Depth First Traverse
E
D
C
B
A
breadth-first search
A
B
C
D
E
Topological sorting
A
B
C
D
E
Summary: JGraphT is a powerful Java graph library that provides a simple and easy-to-use interface and algorithm for easy graph construction, traversal, and algorithm solving. It supports multiple graph types and custom data types, while also providing visualization tools and interfaces. For developers who need to handle graph related issues, JGraphT is a very practical tool library.
