在Java中,鄰接表通常用來表示圖(Graph)的數據結構
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graph {
private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
public void addVertex(int vertex) {
adjacencyList.putIfAbsent(vertex, new ArrayList<>());
}
public void addEdge(int source, int destination) {
adjacencyList.get(source).add(destination);
adjacencyList.get(destination).add(source);
}
}
import java.util.Stack;
public class GraphTraversal {
public void depthFirstTraversal(Graph graph, int startVertex) {
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[graph.adjacencyList.size()];
stack.push(startVertex);
while (!stack.isEmpty()) {
int currentVertex = stack.pop();
if (!visited[currentVertex]) {
System.out.println("Visited vertex: " + currentVertex);
visited[currentVertex] = true;
for (int neighbor : graph.adjacencyList.get(currentVertex)) {
if (!visited[neighbor]) {
stack.push(neighbor);
}
}
}
}
}
}
public class Main {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addVertex(0);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
GraphTraversal traversal = new GraphTraversal();
traversal.depthFirstTraversal(graph, 0);
}
}
運行上述代碼,將會輸出以下結果:
Visited vertex: 0
Visited vertex: 1
Visited vertex: 3
Visited vertex: 2
Visited vertex: 4
這個例子展示了如何在Java中使用鄰接表表示圖,并使用深度優先搜索算法遍歷鄰接表。你可以根據需要修改這些代碼以適應不同類型的圖和遍歷算法。