JS实现图

た入场券 2023-02-20 13:40 13阅读 0赞

## 实现队列 ##

##  ##

## 实现字典 ##

## 图 ##

### 图的遍历 ###

*  广度优先搜索（Breadth-First Search，**BFS**）
 *  深度优先搜索（Depth-First Search，**DFS**）
 *  两个遍历算法，都需要明确指定**第一个被访问的顶点**

**记录状态**

白色：表示该顶点还没有被访问

灰色：表示该顶点被访问过，但并未探索过

黑色：表示该顶点被访问过且完全探索过

### 广度 优先搜索 ###

*  广度优先算法从指定的第一个顶点开始遍历图，先访问其所有的相邻接点，就像一次访问图的一层
 *  先宽后深的访问顶点

![BFS][]

// 广度优先搜索（BFS）
        Graph.prototype.bfs = function (initV, handler) { 
            // 1.初始化颜色
            var color = this.initializeColor();
            // 2.创建队列
            var queue = new Queue();
            // 3.将顶点加入队列中
            queue.enqueue(initV);
            // 4.循环从队列中取出元素
            while (!queue.isEmpty()) { 
                // 4.1.从队列取出一个顶点
                var v = queue.dequeue();
                // 4.2.获取顶点和相连的另外顶点
                var vList = this.edges.get(v);
                // 4.3.将v的颜色设置灰色
                color[v] = 'gray';
                // 4.4.遍历所有的顶点，并且加入到队列中
                for (var i = 0; i < vList.length; i++) { 
                    var e = vList[i];
                    if (color[e] == 'white') { 
                        color[e] = 'gray';
                        queue.enqueue(e);
                    }
                }
                // 4.5.v已经被探测，并且返回
                handler(v);
                // 4.6.将顶点设置为黑色
                color[v] = 'black';
            }
        //
        }
    }
    var result = '';
    g.bfs(g.vertices[0], function (v) { 
        result += v + ' ';
    })
    print(result) // A B C D E F G H I

### 深度 优先搜索 ###

*  深度优先搜索算法会从第一个指定的顶点开始遍历图，沿着路径知道这条路径最后被访问了
 *  接着原路回退并探索一条路径

![DFS][]

// 深度优先搜索（DFS）
        Graph.prototype.dfs = function (initV, handler) { 
            // 1.初始化颜色
            var color = this.initializeColor();
            // 2.从某个顶点开始依次递归访问
            this.dfsVisit(initV, color, handler);
        }
        Graph.prototype.dfsVisit = function (v, color, handler) { 
            // 1.将颜色设置为灰色
            color[v] = 'gray';
            // 2.处理v顶点
            handler(v);
            // 3.访问v相连的顶点
            var vList = this.edges.get(v);
            for (var i = 0; i < vList.length; i++) { 
                var e = vList[i];
                if (color[e] == 'white') { 
                    this.dfsVisit(e, color, handler);
                }
            }
            // 4.将v设置为黑色
            color[v] = 'black';
        }
    var result = '';
    g.dfs(g.vertices[0], function (v) { 
        result += v + ' ';
    })
    print(result); // A B E I F C D G H

### 总代码 ###

**输出：**

![输出][20200627153156850.png]

[BFS]: https://img-blog.csdnimg.cn/20200627145845929.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[DFS]: https://img-blog.csdnimg.cn/20200627150103343.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4Njg5Mzk1,size_16,color_FFFFFF,t_70
[20200627153156850.png]: https://img-blog.csdnimg.cn/20200627153156850.png