数据结构 | 图

概念

图是网络结构的抽象模型，是一组由边连接的节点。

avaScript 中没有图，但可用Object和Array构建图。

上述图可用邻接矩阵表示为：

上述图可用邻接表表示为：

const graph = {
    A: ['B'],
    B: ['C', 'D'],
    C: ['E'],
    D: ['A'],
    E: ['D'],
};

遍历

有如下图，起点为节点2：

// start:2
const graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3],
};

深度优先遍历

尽可能深地搜索图的分支，深搜就是依靠递归的方法来进行的搜索。

1. 访问根节点
2. 对根节点的未访问过的相邻节点依次进行深度优先遍历

// 深度优先遍历图
// 已访问过的节点集合
const visited = new Set();
const dfs = n => {
    visited.add(n);//start 结点
    graph[n].array.forEach(e => {
        if(!visited.has(e))
        dfs(e);//递归深度遍历结点
    });
};

广度优先遍历

先访问离根节点最近的节点。

1. 新建队列，根节点入队
2. 队头出队并访问
3. 队头的未访问过的相邻接点入队
4. 重复 2、3 步骤，直至队列为空

// 广度优先遍历图
// 已访问过的节点集合
const graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3],
};
const visited = new Set();
const list=[];
const bfs = n => {
    visited.add(n);//start 结点
    list.push(n);
    console.log(n)
    while(list.length){
        let curvisit = list.shift();//队头出队，再遍历它的子结点
        graph[curvisit].forEach(e => {
            if(!visited.has(e)){
                visited.add(e);//遍历最近结点
                list.push(e);//结点入队
                console.log(e)
            }
           
        });

    }
};
bfs(2)