数据结构与算法之图: 图及其深度和广度优先遍历实现 (Typescript版)

图

• 网络结构的抽象模型，是一组由边连接的节点
• 图可以表示任何二元关系，道路，航班
  • 由边连接的节点
  • 图中节点多，但是一条边只能连接两个节点
• js中没有图，但可以用Objct和Array构建图
• 图的表示法：临接矩阵，临接表，关联矩阵…
  • 临接矩阵表示法：用矩阵表示
    • 比如这个图上有n个节点, A,B,C,…N
    • 我们画出一个矩阵，横纵都是A->N这n个节点
    • 这个矩阵默认全部填充0,
    • 如果A能连接到B,则在这个矩阵中以A为横轴，B为纵轴相交的那个点置为1表示
    • 如果B能连接到C,则在这个矩阵中以B为横轴，C为纵轴相交的那个点置为1表示
    • …
  • 邻接表表示法
    • 更形象，更容易理解，如下, 构建一个对象，对象的key是各个节点
    • 各个节点里面都有一个数组，数组中的值就是这些节点中可以连接的节点

    {
        A:["B"],
        B:["C", "D"],
        C:["E"],
        D:["A"],
        E:["D"]
    }
    1
    2
    3
    4
    5
    6
    7

    • 里面除了用数组表示，还可以用链表来表示
    • 只要能表达清楚节点之间的链接关系，就可以了
• 图的常用操作
  • 深度优先遍历
  • 广度优先遍历

深度优先遍历和广度优先遍历

这里有一个图的示例，对其进行深度和广度的优先遍历

// 邻接表表示法
const graph = {
    0: [1,2],
    1: [2],
    2: [0, 3],
    3: [3]
}
1
2
3
4
5
6
7

1 ) 深度优先遍历

• 尽可能深的搜索图的分支
• 访问根节点
• 对根节点的没访问过的相邻节点挨个进行深度优先遍历
  • 这里相邻节点和树中的children差不多，概念上相似
  • 这里，没有访问过的节点(为了不重不漏)是一个重要的限制条件，如果不是这样，会陷入死循环

// 使用上面定义的通用graph变量
const visited = new Set();
const res = [];
// 深度优先遍历函数
const dfs = (n) => {
     // console.log(n); // 访问当前节点
     res.push(n); // 访问过的节点存入结果队列中
     visited.add(n);
     graph[n].forEach(c => {
         if(!visited.has(c)) {
             dfs(c); // 对没有访问过的节点进行递归
         }
     })
}

dfs(2) // 这里指定一个起始节点2 
console.log(res.toString()); // 2,0,1,3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2 ) 广度优先遍历

• 先访问离根节点最近的节点
• 口诀
  • 一、新建一个队列，把根节点入队
  • 二、把队头出队并访问
  • 三、把队头的没访问过的相邻节点入队
  • 重复第二、三步，直到队列为空

// 使用上面定义的通用graph变量
const res = []; // 用于存储最终的结果
// 广度优先遍历函数
const bfs = () => {
    const visited = new Set();
    visited.add(2); // 起始节点 注意这里结合下面的漏洞，先加入起始点
    const q = [2]; // 起始节点
    while(q.length) {
        const n = q.shift(); // 队首出队
        // console.log(n); // 访问当前节点
        res.push(n);
        // visited.add(n); // 这里不能在这里添加，会有漏洞，会漏掉一些在q里，但没有在visited中的元素，它会逃过限制，重复在q中被添加
        // 将相邻节点(孩子节点) 存入队列中
        graph[n].forEach(c => {
            // 没有访问过，push
            if(!visited.has(c)) {
                q.push(c);
                visited.add(c); // 将出队元素添加进入集合 这里结合上面注释掉的漏洞，后添加
            }
        })
    }
}

bfs();
console.log(res.toString()); // 2,0,3,1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25