Skip to content

1. 从关系到邻接表 ​

图由顶点与边组成。有向边区分起终点;无向边可以双向走。顶点的出度是向外的边数,入度是进入的边数。路径长度可指边数或权重和,必须先约定。无向连通分量是极大的连通子图;有向强连通要求各点相互可达。

树是连通且无环的无向图,非空树有 V - 1 条边。仅检查一个点入度为零、其余为一,不能证明有向图是一棵树,还需从根可达全部节点且无环。无向简单完全图有 V(V - 1)/2 条边,有向简单完全图有 V(V - 1) 条边。

表示空间适用情况
邻接矩阵O(V²)频繁判断两点之间是否有边、稠密图
邻接表O(V + E)遍历邻居、稀疏图
边列表O(E) 加顶点信息遍历或排序所有边

以下用数组 adj 表示邻接表,顶点编号为 0 到 adj.length - 1,每项为相邻顶点编号数组。无向图必须在两端都记录;自环、重复边允许。输入须结构合法,起点是有效编号;函数只读输入,标记每次重新创建。空图的全图遍历返回空数组;指定起点的函数要求非空图。

2. 深度优先:覆盖整个图 ​

遍历方法解释见遍历对比。外层枚举起点,确保不连通部分也被访问。此实现保存邻居迭代位置,模拟递归逐分支深入,且在首次发现时标记。

js
function dfsAll(adj) {
    const seen = new Array(adj.length).fill(false);
    const order = [];
    for (let start = 0; start < adj.length; start++) {
        if (seen[start]) continue;
        seen[start] = true;
        order.push(start);
        const stack = [[start, 0]];
        while (stack.length) {
            const frame = stack[stack.length - 1];
            const vertex = frame[0];
            if (frame[1] === adj[vertex].length) {
                stack.pop();
                continue;
            }
            const next = adj[vertex][frame[1]++];
            if (!seen[next]) {
                seen[next] = true;
                order.push(next);
                stack.push([next, 0]);
            }
        }
    }
    return order;
}

时间为 O(V + E),辅助空间为 O(V)。在有向图中,外层启动次数不是强连通分量数量;不能把这份遍历误当强连通算法。

3. 广度优先与无权最短路 ​

第一次入队时记录距离与前驱。先标记再入队,使每个顶点最多加入一次。此函数只访问起点可达部分。

js
function bfs(adj, start) {
    const distance = new Array(adj.length).fill(-1);
    const previous = new Array(adj.length).fill(-1);
    const order = [start];
    distance[start] = 0;
    for (let head = 0; head < order.length; head++) {
        const vertex = order[head];
        for (const next of adj[vertex]) {
            if (distance[next] !== -1) continue;
            distance[next] = distance[vertex] + 1;
            previous[next] = vertex;
            order.push(next);
        }
    }
    return { order, distance, previous };
}

返回距离按边数计,不可达为 -1,起点距离为零。所有边代价相同且为正时,最少边数也对应最小代价。反向沿前驱直到起点,再翻转,可恢复路径;目标不可达则返回空路径。

js
function restorePath(previous, start, target) {
    if (target !== start && previous[target] === -1) return [];
    const path = [];
    for (let vertex = target; vertex !== start; vertex = previous[vertex]) path.push(vertex);
    path.push(start);
    return path.reverse();
}

previous 必须来自同一起点的上述搜索,端点合法,不接受任意含环的前驱数组。搜索时间为 O(V + E),辅助与返回空间为 O(V);恢复路径时间和结果空间与路径长度成正比。

4. 拓扑排序:先做没有前置依赖的任务 ​

只适用于有向图。计算入度,将零入度点加入队列;取出它时删除其出边影响。若最终不足 V 个节点,说明存在环,不应把部分顺序当成合法完整结果。

js
function topologicalSort(adj) {
    const indegree = new Array(adj.length).fill(0);
    for (const neighbors of adj) for (const next of neighbors) indegree[next]++;
    const order = [];
    for (let vertex = 0; vertex < adj.length; vertex++) {
        if (indegree[vertex] === 0) order.push(vertex);
    }
    for (let head = 0; head < order.length; head++) {
        for (const next of adj[order[head]]) {
            indegree[next]--;
            if (indegree[next] === 0) order.push(next);
        }
    }
    return order.length === adj.length ? order : null;
}

时间为 O(V + E),辅助空间为 O(V)。空图返回 [],有环返回 null;无环图可能存在多个正确顺序。验收应检查每条边起点在终点之前,不强求某个唯一顺序。

5. 并查集:只关心是否连通 ​

静态无向图也可以遍历计数;边逐步加入时,并查集适合维护集合合并。下面直接解决无向连通分量数量:初始每个点独立,每次真正合并减少一个分量。

js
function countComponents(n, edges) {
    const parent = Array.from({ length: n }, (_, i) => i);
    const size = new Array(n).fill(1);
    let count = n;
    function find(vertex) {
        while (parent[vertex] !== vertex) {
            parent[vertex] = parent[parent[vertex]];
            vertex = parent[vertex];
        }
        return vertex;
    }
    for (const [u, v] of edges) {
        let a = find(u);
        let b = find(v);
        if (a === b) continue;
        if (size[a] < size[b]) [a, b] = [b, a];
        parent[b] = a;
        size[a] += size[b];
        count--;
    }
    return count;
}

约定 n 为非负整数,边端点为有效编号。路径压缩加按大小合并,初始化 O(V),操作总时间为 O(E α(V)) 的均摊界,辅助空间 O(V)。重复边、自环不会重复减少分量;它不求路径,不解决有向强连通或任意删边。

6. 非负权最短路:朴素 Dijkstra ​

带权邻接表每项为 [终点, 权重]。每次从未确定的顶点中选择当前距离最小者,再尝试更新其邻居;非负权保证它不可能经尚未确定的路径变得更短。

js
function dijkstra(adj, start) {
    for (const neighbors of adj) {
        for (const [, weight] of neighbors) {
            if (!Number.isFinite(weight) || weight < 0) throw new RangeError('Nonnegative finite weights required');
        }
    }
    const distance = new Array(adj.length).fill(Infinity);
    const done = new Array(adj.length).fill(false);
    distance[start] = 0;
    for (let step = 0; step < adj.length; step++) {
        let vertex = -1;
        for (let i = 0; i < adj.length; i++) {
            if (!done[i] && (vertex === -1 || distance[i] < distance[vertex])) vertex = i;
        }
        if (vertex === -1 || distance[vertex] === Infinity) break;
        done[vertex] = true;
        for (const [next, weight] of adj[vertex]) {
            distance[next] = Math.min(distance[next], distance[vertex] + weight);
        }
    }
    return distance;
}

起点与端点须合法;数值累加不能溢出,整数题保持安全整数范围。负权立即报错,即使负边不可达也不接受;不可达距离为 Infinity。允许零权和平行边。

时间为 O(V² + E),辅助空间 O(V)。这份教学版不用堆,稀疏大图再考虑优先队列优化。负权图应改选合适算法,不要仅删除检查继续运行。

7. 进阶边界与验收 ​

最小生成树是在无向带权连通图中选择连接所有顶点且总权最小的树,不同于单源最短路。可在理解排序和并查集后练习按权重排序边、跳过成环边的 Kruskal 思路;不连通时只能得到生成森林。强连通分量与负权最短路同属主线之后的扩展。

先用含环、重复边与孤立点的小图验证遍历;检查无权距离与前驱一致、拓扑依赖顺序、并查集合并幂等以及带权路径可能边数更多但总权更小。

sh
node --test tests/algorithm-tree-graph-examples.test.mjs

评论

正在加载评论…