在Java中,实现拓扑图可以通过使用邻接表或邻接矩阵来表示图。这里我将给出一个使用邻接表实现的简单示例。拓扑图是有向无环图(Directed Acyclic Graph,简称DAG)的一种应用场景。
首先,我们需要创建一个表示图的类,包括顶点和边。然后,我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历图并实现拓扑排序。
以下是一个简单的实现:
public class Vertex {
private String label;
private List<Vertex> neighbors;
public Vertex(String label) {
this.label = label;
this.neighbors = new ArrayList<>();
}
public void addNeighbor(Vertex neighbor) {
this.neighbors.add(neighbor);
}
public String getLabel() {
return label;
}
public List<Vertex> getNeighbors() {
return neighbors;
}
}
public class Graph {
private List<Vertex> vertices;
public Graph() {
this.vertices = new ArrayList<>();
}
public void addVertex(Vertex vertex) {
this.vertices.add(vertex);
}
public List<Vertex> getVertices() {
return vertices;
}
}
public class TopologicalSort {
public static List<Vertex> topologicalSort(Graph graph) {
List<Vertex> sortedVertices = new ArrayList<>();
Set<Vertex> visitedVertices = new HashSet<>();
for (Vertex vertex : graph.getVertices()) {
if (!visitedVertices.contains(vertex)) {
dfs(vertex, visitedVertices, sortedVertices);
}
}
Collections.reverse(sortedVertices);
return sortedVertices;
}
private static void dfs(Vertex currentVertex, Set<Vertex> visitedVertices, List<Vertex> sortedVertices) {
visitedVertices.add(currentVertex);
for (Vertex neighbor : currentVertex.getNeighbors()) {
if (!visitedVertices.contains(neighbor)) {
dfs(neighbor, visitedVertices, sortedVertices);
}
}
sortedVertices.add(currentVertex);
}
}
public class Main {
public static void main(String[] args) {
Graph graph = new Graph();
Vertex v1 = new Vertex("1");
Vertex v2 = new Vertex("2");
Vertex v3 = new Vertex("3");
Vertex v4 = new Vertex("4");
Vertex v5 = new Vertex("5");
graph.addVertex(v1);
graph.addVertex(v2);
graph.addVertex(v3);
graph.addVertex(v4);
graph.addVertex(v5);
v1.addNeighbor(v2);
v1.addNeighbor(v3);
v2.addNeighbor(v4);
v3.addNeighbor(v4);
v4.addNeighbor(v5);
List<Vertex> sortedVertices = TopologicalSort.topologicalSort(graph);
for (Vertex vertex : sortedVertices) {
System.out.print(vertex.getLabel() + " ");
}
}
}
输出结果:
1 3 2 4 5
这个示例展示了如何在Java中实现拓扑图。你可以根据自己的需求对这个实现进行扩展和修改。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
推荐阅读:Android怎么做线路拓扑图