JavaScript 图算法

引入图的概念

图是一种非线性数据结构，它由一系列顶点（也称为节点）和连接这些顶点的边组成。图可以分为有向图和无向图。在有向图中，边具有方向性；而在无向图中，边没有方向性。

图的表示方法通常有两种：邻接矩阵和邻接表。邻接矩阵使用二维数组来表示，而邻接表使用链表或数组列表来表示。选择哪种表示方法取决于具体的应用场景和需求。

邻接矩阵表示法

邻接矩阵是一种通过二维数组来表示图的方法。对于一个有n个顶点的图，邻接矩阵是一个n×n的二维数组。如果两个顶点之间存在边，则对应的数组元素为1或权重值；否则为0。

创建邻接矩阵

function createAdjacencyMatrix(numVertices) {
    const matrix = new Array(numVertices);
    for (let i = 0; i < numVertices; i++) {
        matrix[i] = new Array(numVertices).fill(0);
    }
    return matrix;
}

添加边

function addEdge(matrix, vertex1, vertex2, weight = 1) {
    if (vertex1 >= 0 && vertex1 < matrix.length && vertex2 >= 0 && vertex2 < matrix.length) {
        matrix[vertex1][vertex2] = weight;
        // 如果是无向图，还需要添加反向边
        matrix[vertex2][vertex1] = weight;
    }
}

查找边

function hasEdge(matrix, vertex1, vertex2) {
    return matrix[vertex1][vertex2] !== 0;
}

邻接表表示法

邻接表是一种通过数组或链表来表示图的方法。每个顶点都有一个列表，列表中的元素是与该顶点相邻的顶点。这种表示方法特别适合稀疏图。

创建邻接表

function createAdjacencyList(numVertices) {
    return new Array(numVertices).fill(null).map(() => []);
}

添加边

function addEdgeToList(list, vertex1, vertex2, weight = 1) {
    list[vertex1].push({ vertex: vertex2, weight });
    // 如果是无向图，还需要添加反向边
    list[vertex2].push({ vertex: vertex1, weight });
}

查找边

// www.javascriptcn.com code example
function hasEdgeInList(list, vertex1, vertex2) {
    const neighbors = list[vertex1];
    for (const neighbor of neighbors) {
        if (neighbor.vertex === vertex2) {
            return true;
        }
    }
    return false;
}

深度优先搜索（DFS）

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

实现DFS

// www.javascriptcn.com code example
function dfs(graph, startVertex, visited = new Set()) {
    visited.add(startVertex);
    console.log(startVertex); // 访问当前顶点

    graph.forEach((neighbors, vertex) => {
        if (!visited.has(vertex)) {
            dfs(graph, vertex, visited);
        }
    });
}

广度优先搜索（BFS）

广度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的宽度遍历树的节点，如果所有节点均被访问，则算法终止。广度优先搜索是完成这种任务的最佳方法之一。

实现BFS

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

    while (queue.length > 0) {
        const currentVertex = queue.shift();
        console.log(currentVertex); // 访问当前顶点

        graph[currentVertex].forEach(({ vertex }) => {
            if (!visited.has(vertex)) {
                visited.add(vertex);
                queue.push(vertex);
            }
        });
    }
}

最短路径算法

最短路径问题是指在加权图中找到两个节点之间的最短路径的问题。常见的最短路径算法有Dijkstra算法和Bellman-Ford算法。

Dijkstra算法

Dijkstra算法是一种用于寻找给定起点的最短路径的贪心算法。

实现Dijkstra算法

// www.javascriptcn.com code example
function dijkstra(graph, startVertex) {
    const distances = {};
    const previousVertices = {};

    // 初始化距离
    for (const vertex in graph) {
        distances[vertex] = Infinity;
    }
    distances[startVertex] = 0;

    // 主循环
    while (Object.keys(distances).length) {
        let currentVertex = null;
        for (const vertex of Object.keys(distances)) {
            if (currentVertex === null || distances[vertex] < distances[currentVertex]) {
                currentVertex = vertex;
            }
        }

        const neighbors = graph[currentVertex];
        for (const { vertex, weight } of neighbors) {
            const alternativeRoute = distances[currentVertex] + weight;
            if (alternativeRoute < distances[vertex]) {
                distances[vertex] = alternativeRoute;
                previousVertices[vertex] = currentVertex;
            }
        }
        delete distances[currentVertex];
    }

    return { distances, previousVertices };
}

Bellman-Ford算法

Bellman-Ford算法是一种用于寻找最短路径的动态规划算法，能够处理负权重边。

实现Bellman-Ford算法

// www.javascriptcn.com code example
function bellmanFord(graph, startVertex) {
    const distances = {};
    const previousVertices = {};

    // 初始化距离
    for (const vertex in graph) {
        distances[vertex] = Infinity;
    }
    distances[startVertex] = 0;

    // 执行V-1次松弛操作
    for (let i = 0; i < Object.keys(graph).length - 1; i++) {
        for (const currentVertex in graph) {
            const neighbors = graph[currentVertex];
            for (const { vertex, weight } of neighbors) {
                const alternativeRoute = distances[currentVertex] + weight;
                if (alternativeRoute < distances[vertex]) {
                    distances[vertex] = alternativeRoute;
                    previousVertices[vertex] = currentVertex;
                }
            }
        }
    }

    // 检查是否有负权重环
    for (const currentVertex in graph) {
        const neighbors = graph[currentVertex];
        for (const { vertex, weight } of neighbors) {
            const alternativeRoute = distances[currentVertex] + weight;
            if (alternativeRoute < distances[vertex]) {
                throw new Error("Graph contains a negative-weight cycle");
            }
        }
    }

    return { distances, previousVertices };
}

拓扑排序

拓扑排序是对有向无环图(DAG)进行排序的一种算法，它使得对于每一条有向边(u,v)，u都排在v的前面。拓扑排序不是唯一的，不同的算法可能会产生不同的结果。

实现拓扑排序

// www.javascriptcn.com code example
function topologicalSort(graph) {
    const inDegree = {};
    const queue = [];
    const result = [];

    // 初始化入度
    for (const vertex in graph) {
        inDegree[vertex] = 0;
    }

    // 计算每个顶点的入度
    for (const vertex in graph) {
        graph[vertex].forEach(({ vertex: neighbor }) => {
            inDegree[neighbor]++;
        });
    }

    // 将入度为0的顶点加入队列
    for (const vertex in inDegree) {
        if (inDegree[vertex] === 0) {
            queue.push(vertex);
        }
    }

    // 进行拓扑排序
    while (queue.length > 0) {
        const currentVertex = queue.shift();
        result.push(currentVertex);

        graph[currentVertex].forEach(({ vertex: neighbor }) => {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        });
    }

    // 检查是否所有顶点都被访问
    if (result.length !== Object.keys(graph).length) {
        throw new Error("Graph contains a cycle");
    }

    return result;
}

总结

本章详细介绍了图的基本概念、表示方法、遍历算法和最短路径算法。理解这些基本知识有助于我们更好地利用图来解决实际问题。接下来我们将继续深入探讨更多图相关的算法和应用。