java 邻接表—代码示例

邻接表是一种常用的图数据结构，它使用链表来表示图中每个顶点的邻接关系。在Java中，我们可以使用链表和哈希表来实现邻接表。

我们需要定义一个节点类来表示图中的每个顶点。节点类包含两个属性：顶点的值和指向下一个邻接顶点的指针。示例代码如下：

class Node {
    int value;
    Node next;
    public Node(int value) {
        this.value = value;
        this.next = null;
    }
}

接下来，我们需要定义一个图类来管理图的顶点和边。图类包含一个哈希表，用于存储每个顶点和其对应的邻接链表。示例代码如下：

import java.util.HashMap;
import java.util.Map;
class Graph {
    private Map<Integer, Node> adjacencyList;
    public Graph() {
        this.adjacencyList = new HashMap<>();
    }
    public void addVertex(int value) {
        if (!adjacencyList.containsKey(value)) {
            adjacencyList.put(value, null);
        }
    }
    public void addEdge(int source, int destination) {
        Node newNode = new Node(destination);
        newNode.next = adjacencyList.get(source);
        adjacencyList.put(source, newNode);
        // Uncomment the following lines if the graph is undirected
        // Node newNode2 = new Node(source);
        // newNode2.next = adjacencyList.get(destination);
        // adjacencyList.put(destination, newNode2);
    }
    public void printGraph() {
        for (Integer vertex : adjacencyList.keySet()) {
            Node currentNode = adjacencyList.get(vertex);
            System.out.print("Vertex " + vertex + " is connected to: ");
            while (currentNode != null) {
                System.out.print(currentNode.value + " ");
                currentNode = currentNode.next;
            }
            System.out.println();
        }
    }
}

在上面的示例代码中，我们定义了一个Graph类，其中包含了添加顶点和边的方法（addVertex和addEdge），以及打印图的方法（printGraph）。

通过使用邻接表，我们可以有效地表示和操作图数据结构。邻接表的优势在于可以快速查找某个顶点的邻接顶点，并且可以节省空间，特别适用于表示稀疏图。

希望以上的示例代码和解释对你理解Java邻接表有所帮助。