使用JGraphT进行拓扑排序
时间: 2023-05-30 11:02:37 浏览: 76
拓扑排序是一种对有向无环图进行排序的算法。在拓扑排序中,如果存在一条从节点A到节点B的有向路径,那么节点A就必须排在节点B的前面。下面是使用JGraphT进行拓扑排序的示例代码:
```java
import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.cycle.CycleDetector;
import org.jgrapht.alg.interfaces.TopologicalOrderIterator;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import java.util.ArrayList;
import java.util.List;
public class TopologicalSort {
public static void main(String[] args) {
// 创建一个有向无环图
Graph<String, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);
// 添加节点
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
// 添加边
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
graph.addEdge("D", "E");
// 检测是否有环
CycleDetector<String, DefaultEdge> cycleDetector = new CycleDetector<>(graph);
if (cycleDetector.detectCycles()) {
System.out.println("图中存在环!");
return;
}
// 进行拓扑排序
TopologicalOrderIterator<String, DefaultEdge> iterator = new TopologicalOrderIterator<>(graph);
List<String> sortedVertices = new ArrayList<>();
while (iterator.hasNext()) {
sortedVertices.add(iterator.next());
}
// 打印排序结果
System.out.println("拓扑排序结果:");
for (String vertex : sortedVertices) {
System.out.println(vertex);
}
}
}
```
在上面的代码中,我们首先创建了一个有向无环图,并添加了节点和边。然后,我们使用CycleDetector类检测图中是否存在环。如果存在环,就不进行拓扑排序。接着,我们使用TopologicalOrderIterator类进行拓扑排序,并将排序结果保存在一个列表中。最后,我们打印排序结果。
运行上面的代码,可以得到以下输出:
```
拓扑排序结果:
A
C
B
D
E
```
可以看到,节点A排在了节点B和节点C的前面,节点B和节点C排在了节点D的前面,节点D排在了节点E的前面,符合拓扑排序的定义。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)