温馨提示×

java邻接表怎样实现图结构

小樊
86
2024-09-15 02:03:21
栏目: 编程语言

在Java中,使用邻接表实现图结构需要以下几个步骤:

  1. 创建一个节点类(Vertex)来表示图中的每个节点。这个类应该包含一个标识符(例如,一个字符串或整数)以及一个邻接节点列表。
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);
        }
    }
}
  1. 创建一个图类(Graph)来表示整个图结构。这个类应该包含一个节点列表以及一些方法来添加节点、添加边和获取节点。
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);
    }
}
  1. 使用这两个类来创建和操作图结构。
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的邻居并将其打印出来。

0