编写一个函数，实现一个简单的图 (Graph)

推荐答案

// www.javascriptcn.com code example
class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }

    addVertex(vertex) {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }

    addEdge(vertex1, vertex2) {
        if (!this.adjacencyList.has(vertex1)) {
            this.addVertex(vertex1);
        }
        if (!this.adjacencyList.has(vertex2)) {
            this.addVertex(vertex2);
        }
        this.adjacencyList.get(vertex1).push(vertex2);
        this.adjacencyList.get(vertex2).push(vertex1);
    }

    removeEdge(vertex1, vertex2) {
        this.adjacencyList.set(
            vertex1,
            this.adjacencyList.get(vertex1).filter(v => v !== vertex2)
        );
        this.adjacencyList.set(
            vertex2,
            this.adjacencyList.get(vertex2).filter(v => v !== vertex1)
        );
    }

    removeVertex(vertex) {
        while (this.adjacencyList.get(vertex).length) {
            const adjacentVertex = this.adjacencyList.get(vertex).pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        this.adjacencyList.delete(vertex);
    }

    dfs(start) {
        const result = [];
        const visited = new Set();
        const adjacencyList = this.adjacencyList;

        (function dfsHelper(vertex) {
            if (!vertex) return null;
            visited.add(vertex);
            result.push(vertex);
            adjacencyList.get(vertex).forEach(neighbor => {
                if (!visited.has(neighbor)) {
                    return dfsHelper(neighbor);
                }
            });
        })(start);

        return result;
    }

    bfs(start) {
        const queue = [start];
        const result = [];
        const visited = new Set();
        visited.add(start);

        while (queue.length) {
            const vertex = queue.shift();
            result.push(vertex);

            this.adjacencyList.get(vertex).forEach(neighbor => {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            });
        }

        return result;
    }
}

// 使用示例
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "C");

console.log(graph.dfs("A")); // ["A", "B", "C"]
console.log(graph.bfs("A")); // ["A", "B", "C"]

本题详细解读

数据结构选择

在这个实现中，我们使用了 Map 来存储图的邻接表。Map 的键是顶点，值是与该顶点相连的其他顶点的数组。这种数据结构非常适合表示图，因为它可以快速查找和更新顶点的邻接关系。

添加顶点

addVertex 方法用于向图中添加一个新的顶点。如果顶点已经存在，则不会重复添加。

添加边

addEdge 方法用于在两个顶点之间添加一条边。如果顶点不存在，则会先调用 addVertex 方法添加顶点。然后，将两个顶点分别添加到对方的邻接表中。

删除边

removeEdge 方法用于删除两个顶点之间的边。它通过过滤邻接表中的顶点来实现。

删除顶点

removeVertex 方法用于删除一个顶点及其所有相关的边。它首先删除该顶点的所有邻接边，然后从邻接表中删除该顶点。

深度优先搜索 (DFS)

dfs 方法实现了深度优先搜索算法。它从指定的起始顶点开始，递归地访问所有未访问的邻接顶点，并将访问顺序存储在 result 数组中。

广度优先搜索 (BFS)

bfs 方法实现了广度优先搜索算法。它使用队列来存储待访问的顶点，并按照层级顺序访问所有顶点，将访问顺序存储在 result 数组中。

使用示例

在示例中，我们创建了一个包含三个顶点的图，并添加了三条边。然后，我们分别使用 DFS 和 BFS 遍历图，并输出遍历结果。