JavaScript 有向图和无向图-JavaScript中文网-JavaScript教程资源分享门户

在本章中，我们将深入探讨如何使用 JavaScript 来实现有向图和无向图。这两种图结构在计算机科学、网络分析、社交网络等领域都有着广泛的应用。我们不仅会介绍基本的概念和术语，还会通过实际的例子来展示如何在 JavaScript 中构建和操作这些图。

图的基本概念

节点与边

图是由节点（也称为顶点）和连接这些节点的边组成的集合。节点表示实体，而边则表示这些实体之间的关系。在有向图中，边具有方向性，从一个节点指向另一个节点；而在无向图中，边没有方向性，表示的是双向关系。

图的类型

有向图：在有向图中，边是有方向的。这意味着如果存在一条从节点A到节点B的边，这并不意味着可以从节点B到节点A。例如，在社交网络中，用户A可以关注用户B，但用户B不一定关注用户A。
无向图：无向图中的边没有方向性。这意味着如果存在一条连接节点A和节点B的边，则可以从A到B，也可以从B到A。例如，在人际关系网络中，如果A是B的朋友，那么B也是A的朋友。

实现图的数据结构

邻接矩阵

邻接矩阵是一种常用的图表示方法，特别适用于稠密图（即图中边的数量接近于节点数量的平方）。对于一个具有n个节点的图，我们可以使用一个n x n的二维数组来表示。数组中的每个元素表示对应节点之间是否存在边。对于有向图，这个值可以是0或1，而对于有权重的图，这个值还可以表示边的权重。

// www.javascriptcn.com code example
class Graph {
    constructor(numVertices) {
        this.numVertices = numVertices;
        this.adjMatrix = new Array(numVertices);
        for (let i = 0; i < numVertices; i++) {
            this.adjMatrix[i] = new Array(numVertices).fill(0);
        }
    }

    addEdge(v, w) {
        this.adjMatrix[v][w] = 1;
    }

    removeEdge(v, w) {
        if (this.adjMatrix[v][w] === 0) {
            console.log("No edge between %d and %d", v, w);
            return;
        }
        this.adjMatrix[v][w] = 0;
    }

    toString() {
        let resultStr = "";
        for (let i = 0; i < this.numVertices; i++) {
            for (let j = 0; j < this.numVertices; j++) {
                resultStr += this.adjMatrix[i][j] + " ";
            }
            resultStr += "\n";
        }
        return resultStr;
    }
}

邻接表

邻接表是另一种常用的图表示方法，它特别适合于稀疏图（即图中边的数量远小于节点数量的平方）。邻接表是一个数组，其中每个元素都是一个链表，表示与相应节点相连的所有其他节点。这种表示方法更加节省空间，并且在添加和删除节点时效率更高。

// www.javascriptcn.com code example
class AdjacencyListGraph {
    constructor(numVertices) {
        this.numVertices = numVertices;
        this.adjList = new Map();
    }

    addVertex(v) {
        if (!this.adjList.has(v)) {
            this.adjList.set(v, []);
        }
    }

    addEdge(v, w) {
        if (!this.adjList.has(v)) {
            this.addVertex(v);
        }
        if (!this.adjList.has(w)) {
            this.addVertex(w);
        }
        this.adjList.get(v).push(w);
    }

    toString() {
        let resultStr = "";
        this.adjList.forEach((vertices, key) => {
            let adjString = vertices.join(" ");
            resultStr += `${key} -> ${adjString}\n`;
        });
        return resultStr;
    }
}

图的遍历算法

深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

// www.javascriptcn.com code example
function dfs(graph, startVertex) {
    const visited = new Set();
    function dfsRecursive(vertex) {
        if (visited.has(vertex)) return;
        visited.add(vertex);
        console.log(`Visited: ${vertex}`);
        const neighbors = graph.adjList.get(vertex);
        for (const neighbor of neighbors) {
            dfsRecursive(neighbor);
        }
    }
    dfsRecursive(startVertex);
}

广度优先搜索（BFS）

广度优先搜索是一种用于遍历或搜索树或图的算法。从根节点开始，沿着树的宽度遍历树的节点，如果所有节点均被访问，则算法终止。广度优先搜索的实现一般采用open-closed表，把从根节点开始层序遍历所有节点的过程用一个队列来记录。

// www.javascriptcn.com code example
function bfs(graph, startVertex) {
    const visited = new Set();
    const queue = [];
    queue.push(startVertex);
    visited.add(startVertex);

    while (queue.length > 0) {
        const vertex = queue.shift();
        console.log(`Visited: ${vertex}`);

        const neighbors = graph.adjList.get(vertex);
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

图的应用场景

社交网络分析

社交网络分析是图论应用的一个重要领域。通过构建用户之间的连接图，我们可以分析用户的行为模式、群体动态以及信息传播路径等。

导航系统

导航系统如Google Maps使用图数据结构来表示地图上的道路网络。每个交叉口或路标被视为一个节点，而每条道路则被视为连接两个节点的边。通过这种方式，系统可以计算出最短路径或者最快路径。

小结

通过本章的学习，我们了解了图的基本概念及其在JavaScript中的实现方式。我们介绍了两种主要的图表示方法——邻接矩阵和邻接表，以及如何使用它们来构建和操作图。此外，我们还探讨了几种常见的图遍历算法，包括深度优先搜索（DFS）和广度优先搜索（BFS），这些都是解决实际问题时非常有用的工具。最后，我们简要讨论了图在不同领域的应用，包括社交网络分析、导航系统和推荐系统等。希望这些知识能够帮助你在未来的项目中更好地理解和应用图数据结构。