java鄰接表怎樣實(shí)現(xiàn)圖結(jié)構(gòu)

在Java中，使用鄰接表實(shí)現(xiàn)圖結(jié)構(gòu)需要以下幾個(gè)步驟：

1. 創(chuàng)建一個(gè)節(jié)點(diǎn)類（Vertex）來表示圖中的每個(gè)節(jié)點(diǎn)。這個(gè)類應(yīng)該包含一個(gè)標(biāo)識符（例如，一個(gè)字符串或整數(shù)）以及一個(gè)鄰接節(jié)點(diǎn)列表。

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);
        }
    }
}

2. 創(chuàng)建一個(gè)圖類（Graph）來表示整個(gè)圖結(jié)構(gòu)。這個(gè)類應(yīng)該包含一個(gè)節(jié)點(diǎn)列表以及一些方法來添加節(jié)點(diǎn)、添加邊和獲取節(jié)點(diǎn)。

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);
    }
}

3. 使用這兩個(gè)類來創(chuàng)建和操作圖結(jié)構(gòu)。

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());
}

這個(gè)例子創(chuàng)建了一個(gè)包含三個(gè)節(jié)點(diǎn)（A、B和C）的無向圖，并添加了相應(yīng)的邊。然后，我們獲取節(jié)點(diǎn)A的鄰居并將其打印出來。