在Java中,使用邻接表实现图结构需要以下几个步骤:
public class Vertex {
private String id;
private List<Vertex> neighbors;
public Vertex(String id) {
this.id = id;
this.neighbors = new ArrayList<>();
}
public String getId() {
return id;
}
public List<Vertex> getNeighbors() {
return neighbors;
}
public void addNeighbor(Vertex neighbor) {
if (!neighbors.contains(neighbor)) {
neighbors.add(neighbor);
}
}
}
public class Graph {
private Map<String, Vertex> vertices;
public Graph() {
vertices = new HashMap<>();
}
public void addVertex(String id) {
if (!vertices.containsKey(id)) {
vertices.put(id, new Vertex(id));
}
}
public void addEdge(String sourceId, String targetId) {
Vertex source = vertices.get(sourceId);
Vertex target = vertices.get(targetId);
if (source == null || target == null) {
throw new IllegalArgumentException("Source or target vertex not found");
}
source.addNeighbor(target);
target.addNeighbor(source); // 如果是无向图,需要添加这行代码
}
public Vertex getVertex(String id) {
return vertices.get(id);
}
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "A");
Vertex a = graph.getVertex("A");
System.out.println("Neighbors of A: " + a.getNeighbors());
}
这个例子创建了一个包含三个节点(A、B和C)的无向图,并添加了相应的边。然后,我们获取节点A的邻居并将其打印出来。