复旦大学961-数据结构-第五章-图（二）图的遍历,广度度优先遍历和深度优先遍历

野性酷女 2022-12-13 14:29 113阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  图的遍历
 *   *  广度优先遍历（BFS）
     *   *  实现方式
         *  性能分析
         *  应用1：求无权图单源最短路径
         *  应用2：广度优先生成树
     *  深度优先搜索（DFS）
     *   *  实现方式
         *  性能分析
         *  应用：深度优先生成树

# 图的遍历 #

## 广度优先遍历（BFS） ##

**广度优先搜索**（Breadth-First-Search，**BFS**）类似于树中的层序遍历。基本思想为：  
 1. 首 先 访 问 起 始 顶 点 v ， 然 后 依 次 访 问 顶 点 v 的 邻 接 顶 点 w 1 , w 2 , ⋯   , w i 2. 访 问 w 1 顶 点 的 邻 接 顶 点 w 11 , w 12 , ⋯ 3. 访 问 w 2 顶 点 的 邻 接 顶 点 4. 依 次 循 环 下 去 ， 直 到 该 连 通 分 量 的 顶 点 全 部 访 问 完 毕 。 5. 若 还 存 在 其 他 未 访 问 的 顶 点 （ 其 他 未 访 问 的 连 通 分 量 ） ， 则 重 复 1 , 2 , 3 , 4 ， 直 到 所 有 节 点 都 被 访 问 \\begin\{aligned\} & 1. 首先访问起始顶点v，然后依次访问顶点v的邻接顶点w\_1,w\_2,\\cdots,w\_i \\\\ & 2. 访问w\_1顶点的邻接顶点w\_\{11\},w\_\{12\},\\cdots \\\\ & 3. 访问w\_2顶点的邻接顶点 \\\\ & 4. 依次循环下去，直到该连通分量的顶点全部访问完毕。\\\\ & 5. 若还存在其他未访问的顶点（其他未访问的连通分量），则重复1,2,3,4，直到所有节点都被访问 \\end\{aligned\} 1.首先访问起始顶点v，然后依次访问顶点v的邻接顶点w1,w2,⋯,wi2.访问w1顶点的邻接顶点w11,w12,⋯3.访问w2顶点的邻接顶点4.依次循环下去，直到该连通分量的顶点全部访问完毕。5.若还存在其他未访问的顶点（其他未访问的连通分量），则重复1,2,3,4，直到所有节点都被访问

该算法类似树中的层序遍历。若该图为一棵树，那么该图的广度优先遍历的结果就是树的层序遍历结果。

举例：  
![在这里插入图片描述][20201012170018912.png_pic_center]  
该图的广度优先遍历结果为：1,2,5,6,3,7,4,8

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]  
该图（树）的广度优先遍历结果为：1,2,3,4,5,6,7,8

### 实现方式 ###

与树的层序遍历类似，需要借助一个辅助队列。具体操作为：

1.  先选择一个节点入队，然后开始进循环
2.  出队一个元素，若该元素没有被访问过，则访问，并将其邻接顶点入队。
3.  循环2过程，直到该连通分量被访问完毕
4.  判断是否还有剩余节点没有访问，若存在，则继续1,2,3过程，直到所有节点都访问完毕。

Java代码如下：

public static void bsfSearch(Graph graph) { 
        HashSet visited = new HashSet(); // 记录已经访问的顶点
    
        for (int i = 0; i < graph.getVertexNumber(); i++) {   // 遍历所有节点，若节点没有被访问过，那么就对这个节点进行BSF操作。
            if (!visited.contains(graph.getVertexByIndex(i)))
                bsf(graph, graph.getVertexByIndex(i), visited);
        }
    
    }
    
    private static void bsf(Graph graph, Object vertex, HashSet visited) {  
        Queue queue = new ArrayDeque(); // 初始化队列
        queue.add(vertex);  
        while (!queue.isEmpty()) {   // 当队列为空时，说明该连通分量的BSF结束了
            Object head = queue.remove();
            if (visited.contains(head)) continue;  // 如果该节点访问过，则不需要再访问。
            System.out.println(head);  // 访问节点
            visited.add(head); // 将访问过的节点增添到已访问列表中
            Object[] neighborVertex = graph.neighbors(head);  // 获取该节点的邻接节点。 
            for (int i = 0; i < neighborVertex.length; i++) {   // 将该节点的所有邻接入队
                queue.add(neighborVertex[i]);
            }
        }
    }

### 性能分析 ###

空间复杂度：因为要申请一个队列，还需要申请一个空间保存被访问过的节点。所以时间复杂度是O(|V|)，其中|V|为图中节点的数量

时间复杂度：对于采用不同的方式实现，时间复杂度不一致。不一致的来源主要是为“访问节点的邻接节点”这一步。该步骤一共需要做 |V| 次。 若采用邻接矩阵进行实现，则每次访问邻接节点时，要扫描那一行为1的元素，时间复杂度为O(|V|^2)。若采用邻接表方式实现，则访问所有的邻接节点，一共访问了|E|次（|E|是总的边数）。所以时间复杂度为O(|V|+|E|)

### 应用1：求无权图单源最短路径 ###

单源最短路径：一个节点（单源）u到其他节点的最短路径，就是他的单源最短路径。

思想：因为广度优先遍历（BSF）是层序遍历的思想，假设从u出发，那么v节点相对于u节点的最浅层次，就是它的最短路径。

![在这里插入图片描述][20201012170018912.png_pic_center]  
如图，假设求 (6,8) 的最短路径，有很多路径，比如 “6,7,8”，“6,3,7,8”，“6,3,4,8”。但是把它们想成一棵树，然后进行层序遍历，即BFS。这样的话，对于“6,7,8”这条路径，8在6的第三层。对于路径“6,3,7,8”，“6,3,4,8”，8相当于6的第四层。所以按照BFS算法，一定会先通过“678”这条路径访问8。

Java代码如下：

/** * 返回vertex顶点到其他所有顶点的距离 * @param graph 图 * @param vertex 要求的顶点 * @return Map<顶点, vertex到顶点的距离> */
    public static Map<Object, Integer> bsfMinDistance(Graph graph, Object vertex) { 
        HashSet visited = new HashSet(); // 记录访问过的节点
        Queue queue = new ArrayDeque();  // bsf辅助队列
        Map<Object, Integer> result = new HashMap<>();
    
        for (int i = 0; i < graph.getVertexNumber(); i++) { 
            result.put(graph.getVertexByIndex(i), -1); // 初始化结果，-1代表不可达
        }
    
        result.put(vertex, 0); // 将要求的顶点的距离初始化为0，因为自己到自己的距离是0
    
        // 开始进行bsf
        queue.add(vertex);
        visited.add(vertex);
        while(!queue.isEmpty()) { 
            Object head = queue.remove(); // 队头出队
            Object[] neighbors = graph.neighbors(head); // 求出队头节点的邻接节点
    
            for (int i = 0; i < neighbors.length; i++) { 
                if (!visited.contains(neighbors[i])) { 
                    visited.add(neighbors[i]);
                    result.put(neighbors[i], result.get(head) + 1); //将其邻接节点的距离设置为vertex节点到队头节点的距离再加1。
                    queue.add(neighbors[i]); // 队头节点的邻接节点入队
                }
            }
        }
        return result;
    }

### 应用2：广度优先生成树 ###

因为广度优先遍历是从某一个顶点出发，然后进行层序遍历，所以广度优先算法可以对一个连通分量生成一棵树。如果是邻接矩阵存储，只要节点的顺序定下来了，那么访问邻接节点的顺序就是固定的，那么生成的树也是固定的。若使用邻接表进行存储，即是节点顺序固定下来，邻接表也是不唯一的，所以生成的树也是不唯一的。这个应该不考代码，了解即可。

## 深度优先搜索（DFS） ##

### 实现方式 ###

深度优先搜索类似树的先序遍历，基本思想为：  
首先访问节点v，然后访问v的第一个邻接节点w1,然后访问w1的邻接节点w2，一直访问下去，直到该条路走到底。然后接着访问v的第二个邻接节点w2，然后再次进行，直到所有的节点都访问完毕

Java代码如下：

public static void dsfSearch(Graph graph) { 
        HashSet visited = new HashSet(); // 存储已经访问过的节点
    
        for (int i = 0; i < graph.getVertexNumber(); i++) {   // 对所有未访问过的节点进行DSF
            dsf(graph, graph.getVertexByIndex(i), visited);
        }
    }
    
    private static void dsf(Graph graph, Object vertex, HashSet visited) { 
        if (visited.contains(vertex)) return;  // 若该节点已经访问过了，则退出。
    
        System.out.println(vertex);  // 访问该节点
        visited.add(vertex);  // 将该节点标记为已访问
        Object[] neighborVertexes = graph.neighbors(vertex);  // 查找该节点的邻接顶点
        for (int i = 0; i < neighborVertexes.length; i++) {   // 对该节点的所有邻接节点进行DFS
            dsf(graph, neighborVertexes[i], visited);
        }
    }

### 性能分析 ###

空间复杂度：要借助一个集合来存储已经访问过的顶点。因为是递归，还会有一个递归工作栈。最坏的情况下，递归工作栈的深度就是顶点的数量。所以空间复杂度为 O(|V|)

时间复杂度：与BFS算法一样，不同存储方式的时间消耗差异主要在查找邻接节点上。所以，当使用邻接矩阵进行存储时，时间复杂度为 O(|V|^2)，但使用邻接表进行查找时，时间复杂度为O(|V|+|E|)

### 应用：深度优先生成树 ###

与广度优先搜索一样，对图进行深度优先搜索也会产生一棵树。若该图有多个连通分量，则会产生多个树，即森林。同样，邻接矩阵存储时，树是唯一的。邻接表存储时，树不唯一。

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370
[20201012170018912.png_pic_center]: /images/20221123/0b229a2b7df54540885ecf6ca018c189.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/2cae3234ab074eccaf7922450f848ebf.png