🕸️ 图 Graph 可视化

图由节点和边组成。BFS 用队列逐层扩散，DFS 用栈深入探索，Dijkstra 求最短路径

遍历策略：从节点 0 出发。BFS 用队列（先进先出），层层扩散； DFS 用栈（后进先出），一路深入到底再回溯。
在队列/栈中 当前处理 已访问
队列/栈：
选择遍历算法开始演示
访问顺序将在这里显示

Dijkstra 单源最短路径（从节点 0 出发）

Dijkstra 思想：每次从未确定的节点中选距离最小者， 标记为"已确定"（绿色），然后用它松弛（relax）邻居： 若 dist[u] + w < dist[v] 则更新 dist[v]。 边上的数字是权值（距离）。
点击按钮观看 Dijkstra 逐步确定最短距离

JavaScript 实现

// 图的邻接表表示
const adj = new Map();  // 节点 → [{to, weight}]

// BFS - O(V + E)，队列
function bfs(start) {
    const visited = new Set();
    const queue = [start];
    visited.add(start);
    while (queue.length) {
        const u = queue.shift();      // 出队
        process(u);
        for (const { to } of adj.get(u)) {
            if (!visited.has(to)) {
                visited.add(to);
                queue.push(to);            // 入队
            }
        }
    }
}

// DFS - O(V + E)，栈（或递归）
function dfs(start) {
    const visited = new Set();
    const stack = [start];
    visited.add(start);
    while (stack.length) {
        const u = stack.pop();        // 出栈
        process(u);
        for (const { to } of adj.get(u)) {
            if (!visited.has(to)) {
                visited.add(to);
                stack.push(to);            // 入栈
            }
        }
    }
}

// Dijkstra - O((V+E) log V)，优先队列优化
function dijkstra(start) {
    const dist = new Map();      // 距离表
    const done = new Set();       // 已确定集合
    nodes.forEach(v => dist.set(v, Infinity));
    dist.set(start, 0);

    while (done.size < nodes.length) {
        // 选未确定中距离最小的节点（可用最小堆优化）
        let u = -1, minD = Infinity;
        for (const v of nodes) {
            if (!done.has(v) && dist.get(v) < minD) {
                minD = dist.get(v); u = v;
            }
        }
        if (u === -1) break;
        done.add(u);
        // 松弛邻居
        for (const { to, weight } of adj.get(u)) {
            if (dist.get(u) + weight < dist.get(to)) {
                dist.set(to, dist.get(u) + weight);
            }
        }
    }
    return dist;
}

时间复杂度分析（V 节点数，E 边数）

算法时间复杂度空间复杂度说明
BFSO(V + E)O(V)队列 + visited 集合
DFSO(V + E)O(V)栈 + visited 集合
Dijkstra（堆优化）O((V+E) log V)O(V)dist 数组 + 优先队列
Dijkstra（朴素）O(V²)O(V)每轮线性扫描最小距离

实际应用场景

  • 🕷️ 爬虫：BFS 逐层抓取网页链接
  • 🗺️ 导航：Dijkstra 计算地图最短路径
  • 🤝 社交网络：BFS 找最短关系链（六度分隔）
  • 🧩 迷宫求解：DFS 回溯探索
  • 🌐 网络路由：OSPF 协议基于 Dijkstra