邻接表图

介绍

实现

创建图架构

:::details 点击查看代码

class Graph {
    constructor(isDirected = false) {
        this.vertices = [];
        this.adjList = {};
        this.isDirected = isDirected;
    }
}

:::

添加顶点

:::details 点击查看代码

addVertex(newVertex) {
    if (!this.vertices.includes(newVertex)) {
    this.vertices.push(newVertex);
    this.adjList[newVertex] = [];
    }
}

:::

添加边

:::details 点击查看代码

addEdge(x, y) {
    if (!this.adjList[x]) {
        this.addVertex(x);
    }
    if (!this.adjList[y]) {
        this.addVertex(y);
    }
    this.adjList[x].push(y);
    if (!this.isDirected) {
        this.adjList[y].push(x);
    }
}

:::

删除顶点

:::details 点击查看代码

removeVertex(vertex) {
    const vertexIndex = this.vertices.includes(vertex);
    if (vertexIndex != -1) {
    for (const i in this.adjList) {
        let tempIndex = this.adjList[i].indexOf(vertex);
        if (tempIndex != -1) {
        this.adjList[i].splice(tempIndex, 1);
        }
    }
    }
    delete this.adjList[vertex];
    this.vertices.splice(vertexIndex, 1);
}

:::

删除边

:::details 点击查看代码

removeEdge(x, y) {
    if (this.adjList[x] && this.adjList[y]) {
    const indexX = this.adjList[x].indexOf(x);
    const indexY = this.adjList[y].indexOf(y);
    this.adjList[x].splice(indexX,1);
    if(!this.isDirected){
        this.adjList[y].splice(indexY,1);
    }
    }
}

:::

广度优先遍历

思路:广度优先遍历是一种从最初的顶点开始，优先访问所有相邻顶点的遍历方法。通过使用队列来暂存访问的顶点，队列遵循先进先出的原则

递归

---

:::details 点击查看代码

:::

迭代

---

:::details 点击查看代码

DFSTraverseByIteration(startVertex) {
    const stack = [startVertex];
    const visited = new Set();
    while (stack.length > 0) {
        const node = stack.pop();
        if (node && !visited.has(node)) {
            visited.add(node);
            const neighbors = this.adjList[node];
            for (let i = 0; i < neighbors.length; i++) {
            stack.push(neighbors[i]);
            }
        }
    }
    return visited
}

:::

深度优先遍历

思路: 深度优先遍历是一种从最初的顶点开始

递归

---

:::details 点击查看代码

:::

迭代

---

:::details 点击查看代码

BFSTraverseByIteration(startVertex) {
    const visited = new Set();
    const queue = [startVertex];
    while (queue.length > 0) {
        const node = queue.shift();
        if (!visited.has(node)) {
            visited.add(node);
            const neighbors = this.adjList[node];
            for (let i = 0; i < neighbors.length; i++) {
            queue.push(neighbors[i]);
            }
        }
    }
    return visited;
}

:::

完整代码

:::details 点击查看代码

class Graph {
    constructor(isDirected = false) {
        this.vertices = [];
        this.adjList = {};
        this.isDirected = isDirected;
    }
    addVertex(newVertex) {
        if (!this.vertices.includes(newVertex)) {
        this.vertices.push(newVertex);
        this.adjList[newVertex] = [];
        }
    }
    addEdge(x, y) {
        if (!this.adjList[x]) {
        this.addVertex(x);
        }
        if (!this.adjList[y]) {
        this.addVertex(y);
        }
        this.adjList[x].push(y);
        if (!this.isDirected) {
        this.adjList[y].push(x);
        }
    }
    removeVertex(vertex) {
        const vertexIndex = this.vertices.includes(vertex);
        if (vertexIndex != -1) {
        for (const i in this.adjList) {
            let tempIndex = this.adjList[i].indexOf(vertex);
            if (tempIndex != -1) {
            this.adjList[i].splice(tempIndex, 1);
            }
        }
        }
        delete this.adjList[vertex];
        this.vertices.splice(vertexIndex, 1);
    }
    removeEdge(x, y) {
        if (this.adjList[x] && this.adjList[y]) {
        const indexX = this.adjList[x].indexOf(x);
        const indexY = this.adjList[y].indexOf(y);
        this.adjList[x].splice(indexX,1);
        if(!this.isDirected){
            this.adjList[y].splice(indexY,1);
        }
        }
    }
    DFSTraverseByIteration(startVertex) {
        const stack = [startVertex];
        const visited = new Set();
        while (stack.length > 0) {
        const node = stack.pop();
        if (node && !visited.has(node)) {
            visited.add(node);
            const neighbors = this.adjList[node];
            for (let i = 0; i < neighbors.length; i++) {
            stack.push(neighbors[i]);
            }
        }
        }
        return visited;
    }
    BFSTraverseByRecursion() {}
    BFSTraverseByIteration(startVertex) {
        const visited = new Set();
        const queue = [startVertex];
        while (queue.length > 0) {
        const node = queue.shift();
        if (!visited.has(node)) {
            visited.add(node);
            const neighbors = this.adjList[node];
            for (let i = 0; i < neighbors.length; i++) {
            queue.push(neighbors[i]);
            }
        }
        }
        return visited;
    }
}

const vertex = ["A", "B", "C", "D", "E", "F"];
const graph = new Graph(true);

for (let i = 0; i < vertex.length; i++) {
graph.addVertex(vertex[i]);
}
graph.addEdge("A", "B");
graph.addEdge("A", "D");
graph.addEdge("B", "E");
graph.addEdge("C", "D");
graph.addEdge("D", "A");
graph.addEdge("E", "D");
graph.addEdge("F", "G");
console.log("深度优先遍历-递归实现");
console.log("深度优先遍历-迭代实现");
console.log(Array.from(graph.DFSTraverseByIteration("C")));
console.log("广度优先遍历-递归实现");
console.log("广度优先遍历-迭代实现");
console.log(Array.from(graph.BFSTraverseByIteration("C")));
console.log("删除顶点 A");
graph.removeVertex("A");
console.log(graph.adjList);
console.log("删除边 B->E");
graph.removeEdge("B","E");
console.log(graph.adjList);

:::

---

参考资料: