JavaScript 邻接表

邻接表是一种图的存储结构，通过数组与链表相结合的方式表示图中的节点和边。对于无向图来说，邻接表中的每个顶点都对应一个单链表，链表中的节点表示与该顶点相邻的其他顶点。对于有向图，可以将邻接表看成是出边表，即链表中的节点表示从当前顶点出发指向的其他顶点。

创建邻接表

创建一个邻接表需要首先定义节点的数据结构，通常包括节点的值和指向下一个节点的引用。接下来，定义一个类来表示整个图，这个类中包含一个数组，数组的每一个元素都是一个链表，用来表示每个节点的邻接关系。

// www.javascriptcn.com code example
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class AdjacencyListGraph {
    constructor() {
        this.adjList = [];
    }

    addVertex(vertex) {
        if (!this.adjList.includes(vertex)) {
            this.adjList.push(new Node(vertex));
        }
    }

    addEdge(v1, v2) {
        let node = this.adjList[this.getIndex(v1)];
        while (node.next) {
            node = node.next;
        }
        node.next = new Node(v2);
    }

    getIndex(vertex) {
        for (let i = 0; i < this.adjList.length; i++) {
            if (this.adjList[i].value === vertex) return i;
        }
        return -1;
    }

    display() {
        for (let i = 0; i < this.adjList.length; i++) {
            console.log(`${this.adjList[i].value}:`);
            let node = this.adjList[i].next;
            while (node) {
                console.log(`-> ${node.value}`);
                node = node.next;
            }
        }
    }
}

图的基本操作

添加顶点

添加顶点的操作实际上是往邻接表数组中添加一个新的链表头部节点，这个节点代表新的顶点。

添加边

添加边的操作是将一个顶点添加到另一个顶点的邻接列表中，这通常涉及到在链表中添加一个新的节点。

显示图

显示图的操作是遍历邻接表数组，并打印每个链表的内容，从而直观地展示图的结构。

实例演示

// www.javascriptcn.com code example
let graph = new AdjacencyListGraph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "C");

graph.display();

输出结果：

A:
-> B
-> C
B:
-> C
C:

以上代码展示了如何使用邻接表数据结构来创建和操作一个简单的无向图。通过这种结构，我们可以方便地添加、删除顶点或边，并能够高效地遍历图的所有节点及其邻接关系。邻接表对于处理稠密图特别有效，因为它只存储实际存在的边，避免了大量不必要的空间浪费。