数据结构系列之图的应用

图

==Graph==

图：节点和边的组合

• 分类
  • 有向图(directed graph)
  • 无向图(undirected graph)
• 遍历方式
  • depth first traversal
  • stack
  • 遍历的过程需遵循图中节点的箭头
  • breadth first traversal
    • queue
• 有路径
• 无向路径
• 连接组件计数
• 最大的组件
• 最短路径
  • 推荐使用广度优先搜索
• 岛屿数量
• 最小岛屿

代码实现

• 深度优先栈遍历

// const depthFirstPrint = (graph,source) => {
//     const stack = [source];
//     while(stack.length > 0){
//         const current = stack.pop();
//         console.log(current);
//         for(let neighbor of graph[current]){
//             stack.push(neighbor);
//         }
//     }
// };
// recrusive 
const depthFirstPrint = (graph, source) => {
    console.log(source);

    for (let neighbor of graph[source]) {
        depthFirstPrint(graph,neighbor);
    }

};

const graph = {
    a: ['c', 'b'],
    b: ['d'],
    c: ['e'],
    d: ['f'],
    e: [],
    f: [],
}

depthFirstPrint(graph, 'a'); //a b d f c e

• 广度优先队列遍历

const breathFirstPrint = (graph,source) => {
    const queue = [source];
    while(queue.length > 0){
        const current = queue.shift();
        console.log(current);
        for(let neighbor of graph[current]){
            queue.push(neighbor);
        }
    }
};
// recrusive 
// const breathFirstPrint = (graph, source) => {
//     console.log(source);

//     for (let neighbor of graph[source]) {
//         breathFirstPrint(graph,neighbor);
//     }

// };

const graph = {
    a: ['c', 'b'],
    b: ['d'],
    c: ['e'],
    d: ['f'],
    e: [],
    f: [],
}

breathFirstPrint(graph, 'a'); //a c b e d f

无向路径(has-path)

// const hasPath = (graph, src, dst) => {
//     if (src === dst) return true;
//     for (let neighbor of graph[src]) {
//         if (hasPath(graph, neighbor, dst) === true) {
//             return true;
//         }
//     }
//     return false;
// };
const hasPath = (graph, src, dst) => {
    const queue = [src];
    while (queue.length > 0) {
        const current = queue.shift();
        if (current === dst) return true;
        for (let neighbor of graph[current]) {
            queue.push(neighbor);
        }
    }
    return false;
};
const graph = {
    f: ['g', 'i'],
    g: ['h'],
    h: [''],
    i: ['g', 'k'],
    j: ['i'],
    k: [''],
}

hasPath(graph, 'f', 'k');
console.log(hasPath(graph, 'f', 'k'));

无向路径(undirected-path)

const undirectedPath = (edges, nodeA, nodeB) => {
    const graph = buildGraph(edges);
    console.log(graph);
    return hasPath(graph, nodeA, nodeB, new Set());
};

const hasPath = (graph, src, dst, visited) => {
    if (src === dst) return true;
    if (visited.has(src)) return false;
    visited.add(src);
    for (let neighbor of graph[src]) {
        if (hasPath(graph, neighbor, dst, visited) === true) {
            return true;
        }
    }
    return false;
};

const buildGraph = (edges) => {
    const graph = {};
    for (let edge of edges) {
        const [a, b] = edge;
        if (!(a in graph)) graph[a] = [];
        if (!(b in graph)) graph[b] = [];
        graph[a].push(b);
        graph[b].push(a);
    }
    return graph;
}
const edges = [
    ['i', 'j'],
    ['k', 'i'],
    ['m', 'k'],
    ['k', 'l'],
    ['o', 'm']
];



undirectedPath(edges, 'j', 'm')
// {
//     i: [ 'j', 'k' ],
//     j: [ 'i' ],
//     k: [ 'i', 'm', 'l' ],
//     m: [ 'k', 'o' ],
//     l: [ 'k' ],
//     o: [ 'm' ]
// }

连接组件计数

const connectedComponentsCount = (graph) => {
    const visited = new Set();
    let count = 0;
    for(let node in graph){
        console.log(visited);
        explore(graph,node,visited);
        count++;
    }
    return count;
};

const explore = (graph,current,visited) => {
    if(visited.has(String(current))) return false;
    visited.add(String(current));
    for(let neighbor of graph[current]){
        explore(graph,neighbor,visited);
    }
    return true;
};

let result  = connectedComponentsCount({
    0: [8,1,5],
    1: [0],
    5: [0,8],
    8: [0,5],
    2: [3,4],
    3: [2,4],
    4: [3,2]
});
console.log(result);

最大的组件

const largestComponent = (graph) => {
    const visited = new Set();
    let longest = 0;
    for(let node in graph){
        const size = explorSize(graph,node,visited);
        if(size > longest) longest = size;

    }
    return longest;
};

const explorSize = (graph,node,visited) => {
    if(visited.has(node)) return 0;
    visited.add(node);
    let size = 1;
    for(let neighbor of graph[node]){
        size += explorSize(graph,neighbor,visited);
    }
    return size;
};

let result  = largestComponent({
    0: ['8','1','5'],
    1: ['0'],
    5: ['0','8'],
    8: ['0','5'],
    2: ['3','4'],
    3: ['2','4'],
    4: ['3','2']
});
console.log(result);
module.exports = {
    largestComponent
};

最短路径==推荐使用广度优先搜索==

const shortPath = (edges, nodeA, nodeB) => {
    const graph = buildGraph(edges);
    const visited = new Set([nodeA]);
    // console.log(graph);
    const queue = [
        [nodeA, 0]
    ];
    while (queue.length > 0) {
        const [node, distance] = queue.shift();
        if (node === nodeB) return distance;
        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, distance + 1]);

            }
        }
    }
    return -1;  //there is no short path
};

const buildGraph = (edges) => {
    const graph = {};
    for (let edge of edges) {
        const [a, b] = edge;
        if (!(a in graph)) graph[a] = [];
        if (!(b in graph)) graph[b] = [];
        graph[a].push(b);
        graph[b].push(a);
    }
    return graph;
}

const edges = [
    ['w', 'x'],
    ['x', 'y'],
    ['z', 'y'],
    ['z', 'v'],
    ['w', 'v'],
];

console.log(shortPath(edges, 'w', 'z'));

岛屿数量

const islandCount = (grid) => {
    const visited = new Set();
    //记录岛屿个数
    let count = 0;
    for (let r = 0; r < grid.length; r++) {
        for (let c = 0; c < grid.length; c++) {
            if (explore(grid, r, c, visited) === true) {
                count++;
            }
        }
    }
    //返回岛屿个数
    return count;
};
//返回值为布尔类型
const explore = (grid, r, c, visited) => {
    //处理边界
    const rowBounds = 0 <= r && r < grid.length;
    const colBounds = 0 <= c && c < grid.length;
    if (!rowBounds || !colBounds) return false;
    if (grid[r][c] === 'W') return false;
    const pos = r + ',' + c;
    if (visited.has(pos)) return false;
    visited.add(pos);
    // depth first search
    explore(grid, r - 1, c, visited);
    explore(grid, r + 1, c, visited);
    explore(grid, r, c - 1, visited);
    explore(grid, r, c + 1, visited);
    return true;
};


const grid = [
    ['W','L','W','W','W'],
    ['W','L','W','W','W'],
    ['W','W','W','L','W'],
    ['W','W','L','L','W'],
    ['L','W','W','L','L'],
    ['L','L','W','W','W'],
];

console.log("岛屿个数为: " + islandCount(grid));    //3

最小岛屿(==DFS + Loop==)

// nested loop + dfs
// time  : O(rc)
// space : O(rc)
const minimumIsland = (grid) => {
    const visited = new Set();
    let minSize = Infinity;
    for (let r = 0; r < grid.length; r++) {
        for (let c = 0; c < grid.length; c++) {
           const size = exploreSize(grid, r, c, visited);
           if(size > 0 && size < minSize){
               minSize = size;
           }
        }
    }
    //返回最小区域的岛屿
    return minSize;
};

const exploreSize = (grid, r, c, visited) => {
    const rowBounds = 0 <= r && r < grid.length;
    const colBounds = 0 <= c && c < grid[0].length;
    if (!rowBounds || !colBounds) return 0;
    if (grid[r][c] === 'W') return 0;

    const pos = r + ',' + c;
    if (visited.has(pos)) return 0;
    visited.add(pos);

    // depth first search
    //记录每个岛屿区域的大小
    let size = 1;
    size += exploreSize(grid, r - 1, c, visited);
    size += exploreSize(grid, r + 1, c, visited);
    size += exploreSize(grid, r, c - 1, visited);
    size += exploreSize(grid, r, c + 1, visited);
    return size;
};
const grid = [
    ['W','L','W','W','L'],
    ['W','L','W','W','W'],
    ['W','W','W','L','W'],
    ['W','W','L','L','W'],
    ['L','W','W','L','L'],
    ['L','L','W','W','W'],
];
console.log("最小岛屿的区域大小为：" + minimumIsland(grid));