🕸️ 图结构深度解析

// 广度优先搜索 (BFS) - 使用队列
function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    const result = [];
    
    while (queue.length > 0) {
        const vertex = queue.shift();
        if (!visited.has(vertex)) {
            visited.add(vertex);
            result.push(vertex);
            for (const neighbor of graph[vertex]) {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                }
            }
        }
    }
    return result;
}

// 深度优先搜索 (DFS) - 使用递归/栈
function dfs(graph, start, visited = new Set()) {
    const result = [];
    
    function traverse(vertex) {
        if (visited.has(vertex)) return;
        visited.add(vertex);
        result.push(vertex);
        for (const neighbor of graph[vertex]) {
            traverse(neighbor);
        }
    }
    
    traverse(start);
    return result;
}

// Dijkstra算法 - 使用优先队列优化
function dijkstra(graph, start) {
    const distances = {};
    const visited = new Set();
    const pq = [[0, start]]; // [距离, 顶点]
    
    // 初始化距离为无穷大
    for (const vertex in graph) {
        distances[vertex] = vertex === start ? 0 : Infinity;
    }
    
    while (pq.length > 0) {
        // 取出当前最小距离的顶点
        pq.sort((a, b) => a[0] - b[0]);
        const [dist, vertex] = pq.shift();
        
        if (visited.has(vertex)) continue;
        visited.add(vertex);
        
        // 更新邻居的距离
        for (const [neighbor, weight] of graph[vertex]) {
            const newDist = dist + weight;
            if (newDist < distances[neighbor]) {
                distances[neighbor] = newDist;
                pq.push([newDist, neighbor]);
            }
        }
    }
    return distances;
}