您的位置: 首页  >  文章  >  数据结构之BFS和DFS

数据结构之BFS和DFS

分类: 文章 • 2024-11-30 19:41:04

大佬视频走起：https://www.bilibili.com/video/av25763384

先把图定好

数据结构之BFS和DFS

var graph = {
    A: ['B', 'C'],
    B: ['A', 'C', 'D'],
    C: ['A', 'B', 'D', 'E'],
    D: ['B', 'C', 'E', 'F'],
    E: ['C', 'D'],
    F: ['D'],
}

BFS 广度优先搜索

利用队列实现。
一个节点入队列，接着塞入它的邻节点，接着塞入邻节点的邻节点…
最后输出直至队列为空。
依照这个思想，我写了下面这段代码：

function BFS(graph, s) {
   var set = new Set();
   set.add(s);
	//遍历所有点极其邻居，利用set特性，已经存在的不会塞入，不停往里面塞就行
   for (var i in graph) {
       for (var v of graph[i]) {
           set.add(v);
       }
   }
   console.log(queue);
}
BFS(graph, 'A');

然后发现上面这个代码，只能从起始点是‘A’开始。因为遍历graph就是从A开始的。
加个数组作为队列，每次从队头取值。判断set中是否有值，然后再塞入。

function BFS(graph, s) {
    var seen = new Set();
    seen.add(s);
    var queue = [];
    queue.push(s);
    //这个循环，只能从起始点是‘A’开始
    while (queue.length > 0) {
    	//每次取出队头元素，用pop(0)也可以
        var x = queue.shift();
        for (var v of graph[x]) {
        	//判断这个值是不是访问过了，没有就塞入队列和集合
            if (!seen .has(v)) {
                queue.push(v);
                seen .add(v);
            }
        }

    }
    console.log(seen ); 
    //把集合打印出来就是BFS的结果：Set { 'E', 'C', 'D', 'A', 'B', 'F' }

}
BFS(graph, 'E');

利用BFS求最短路径

数据结构之BFS和DFS
如上图，把图看做一颗树，把每一个节点的父节点确定出来，形成映射。这里A看做根节点，如果要求A到E的最短路径，可以反着来，从E出发，发现E的父节点是C，然后找到C，C的parent是A，A的parent是null。
那么路径即为： E - C - A
那么在上面基础上加上树的构建，代码如下：

 var parent;
function BFSTree(graph, s) {
    var queue = [];
    queue.push(s);
    var seen = new Set();
    seen.add(s);
    //建树的映射
    parent = {};
    parent[s] = null;

    while (queue.length > 0) {
    	//取出第一个点
        var vertex = queue.pop(0); 
        //获得vertex的所有邻居
        for (var v of graph[vertex]) {
            if (!seen.has(v)) {
                //此时点的parent肯定是vertex
                parent[v] = vertex;
                queue.push(v);
                seen.add(v);
            }

        }

    }
    console.log(parent);
  
}
function shortestRoad(graph, x, y) {
    // 构建一颗树， 所有节点都有个父节点
    BFSTree(graph, x);
    // 求某一点x 到 y 的最短路径
    while (y != null) {
        //结果： F D C A
        console.log(y);
        y = parent[y];
    }
}
 // 求点'A' 到 'F' 的最短路径
shortestRoad(graph, 'A', 'F');

 /**输出结果
    {
	    A: null,
	    B: 'A',
	    C: 'A',
	    D: 'C',
	    E: 'C',
	    F: 'D'
	}
	路径： F D C A
    */

DFS 深度优先搜索

利用栈实现。
只要一个节点有邻节点就出栈，并在栈中塞入其邻节点。。。。这样保证输出的节点一定是前一个输出的邻节点，形成一条路径。最后弹出直至栈为空。
比如下面，A节点的邻节点BC压入栈，然后弹出B，找到B的邻节点D压入（C也是邻节点，但它已经在栈中了），然后弹出D，找D的邻节点E，F压入。
数据结构之BFS和DFS

function DFS(graph, s) {
    var stack = [];
    stack.push(s);
    var set = new Set();
    set.add(s);
    while (stack.length > 0) {
        // 弹出栈顶元素
        var x = stack.pop();

        //找这个栈顶元素的邻居，没有出现过的压入栈中
        for (var v of graph[x]) {
            if (!set.has(v)) {
                stack.push(v);
                set.add(v);
            }
        }
        console.log(x);
    }

}
 DFS(graph, 'E');
 //E D F B A C

相关推荐