在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中實現拓撲圖。你可以根據自己的需求對這個實現進行擴展和修改。