算法笔记（五）图的广度优先遍历和深度优先遍历

喜欢ヅ旅行 2022-06-10 06:47 238阅读 0赞

# 你对图的理解是什么？ #

你是否经常听到这句话，在两个开发之间交流时常说 “有纸么？画个图看看”，可见图在我们的日常生活、工作中发挥的巨大作用，对于图的理解还有很多场景，都是来自于生活 如电视剧中的藏宝图为得到而群雄争霸、名人名画也称为图，综上所述图更明确的含义是带有某种信息的画叫做图，图可以比文字表达更多的信息，语言表达、文字远远没有一幅图生动形象具体，这也是为什么很多人用图来展示自己的想法。

# 为什么有图这种数据结构？ #

大家都使用过数组，数组中的元素都是按着物理地址空间串连起来的，像一条线一样，每个元素只有一个直接前驱和直接后驱，等到了树形结构呢，数据之间具有了明显的层次关系并且每一层上的数据元素可能会下一层多个节点之间存在关系，且只和上一层一个节点有关系，这有点像一对多不过这种一对多是有方向的，如同我们的家谱中一对双亲可能有多个孩子。

现实生活是复杂多变的，拿和我们息息相关的高铁来说，每一列车连通了两个或多个城市的连接，每个城市和其它各个城市都可能连接，这是错综复杂的关系，非线性也非层次关系，然而这种复杂关系可以用图来形象的表示，说到这里你是否理解了为什么会有图这种数据结构呢？

说的更通俗一些图这种数据结构是因为它可以表达数据之间更为复杂的逻辑关系，这种数据间的逻辑关系是数组、链表不能表达或者表达不方便的关系，给解决特定问题或编写程序带来了很大的便利，它的产生是现实生活中特定问题催化出来的，如同java 设计模式一样，设计模式是对于类之间关系抽象总结升华的结果。以后随着计算机运算速度飞速提高、量子计算机的发展，也可能会出现新的数据结构来应对。

# 定义 #

*  标准定义：图（Graph）是由顶点(Vertex)的有穷集合和顶点之间的边（Edge）的集合组成，通常表示为：G(V,E)，其中G表示一个图，V 是图G中顶点的集合，E是图G中边的集合。
 *  无向图：任意两个顶点之间的边都是无向的。
 *  有向图：任意两个顶点之间的边都是有向的。
 *  简单图：无连接自身的边并且任意两个顶点之间只有一条边
 *  无向完全图：任意两个顶点之间都存在一条边
 *  有向完全图：任意两个顶点之间都存在一条有向边
 *  稀疏图：边少的图
 *  稠密图：边多的图
 *  权：边有值得图
 *  子图：顶点和边包含在图中
 *  连通图：任意一点v存在到达顶点v’的路径

如下面图所示，表达了上面概念的关系，画图容易记忆：  
![这里写图片描述][SouthEast]

# 创建、存储 #

我们已经对图结构的定义有了解，主要是由顶点和边组成，存储图的问题也就是对顶点和边的存储了，那么我们如何来存储这些顶点和边呢？

顶点在图中不仅仅只顶点，还有顶点之间边的关系，顶点可以使用数组存储，对于边总共有n的平方个边，即完全有向图最少一个边都没有，由此边的范围是\[0-n^2\]即存储,常见的两种方法是使用邻接矩阵和邻接链表形式，除了这两种还有很多种表示方法，在这里不一一列出，我们用无向完全图来举例：  
![这里写图片描述][SouthEast 1]  
     如上图我们来创建一个具有5个顶点，且每个顶点都和其它4个顶点有边的无向完全图。

该图共有5个顶点各个顶点之间并没有访问先后顺序，所以没有写标出顶点编号，各个顶点他们是一样的通过创建一个实体类来表示这个图的存储结构：

## 实体类 ##

该实体类有属性主要有两个属性一维数组来存储图的各个顶点、二维数组来存储顶点之间的表关系，该实体类可以表示一个图的存储，这个思路主要就是用一维数组和二维数组来存储顶点和边关系，当然除了利用数组存储，还有很多其它方式 如链表等

/** * Created by lilongsheng on 2017/8/2. * 图结构存储实体类 */
    public class GraphEntity { 
    
        /* 顶点数 默认值 */
        public static int MAX_VEX = 5 ;
        /* 存储顶点的一维数组 */
        public String[] vexs = new String[MAX_VEX];
        /* 邻接矩阵 表示顶点之间的表关系 二维数组 */
        public String[][] arc = new String[MAX_VEX][MAX_VEX];
        /* 图中当前节点的顶点数 、边数 */
        private int numVertexes;//图中当前的顶点数
        private int numEdges;//图中当前边数
    
        public String[] getVexs() {
            return vexs;
        }
    
        public void setVexs(String[] vexs) {
            this.vexs = vexs;
        }
    
        public String[][] getArc() {
            return arc;
        }
    
        public void setArc(String[][] arc) {
            this.arc = arc;
        }
    
        public int getNumVertexes() {
            return numVertexes;
        }
    
        public void setNumVertexes(int numVertexes) {
            this.numVertexes = numVertexes;
        }
    
        public int getNumEdges() {
            return numEdges;
        }
    
        public void setNumEdges(int numEdges) {
            this.numEdges = numEdges;
        }
    }

# 图的操作 #

1.  新增顶点
2.  删除顶点
3.  返回图中指定顶点的坐标位置
4.  返回图中指定顶点的值
5.  图的深度遍历
6.  图的广度遍历
7.  ………………等等

由图的操作大家是否会想到数组、队列等操作，可以对比一下，其它他们的操作都是类似的，都是结合自身结构特点对数据的操作，只不过表现形式不同而已。

同样是数据,在线性表中叫元素，在树中叫节点，在图中叫顶点；对于关系，在线性表中相邻元素之间有线性关系，树中相邻两层节点间有层次关系，图中任意两顶点之间可能有关系；

# 两种遍历算法 #

## 深度遍历 ##

/** * 邻接矩阵的深度遍历操作 * @param G */
        public void DFSTraverse(GraphEntity G) {
            int i;
            for (i = 0; i < G.getNumVertexes(); i++) {
                visited[i] = false; //初始化所有顶点状态为未访问过
            }
    
            for (i = 0; i < G.getNumVertexes(); i++) {
                //对未访问过的顶点调用DFS,若是连通图只会执行一次
                if (!visited[i]) {
                    DFS(G, i);
                }
            }
        }
    
        /** * 深度遍历未访问的顶点 * @param G * @param i */
        public void DFS(GraphEntity G, int i) {
            int j;
            visited[i] = true;
            //打印顶点信息
            for (j = 0; j < G.getNumVertexes(); j++) {
                if (G.arc[i][j] == "1" && !visited[j]) {
                    DFS(G, j);//对未访问的邻接顶点递归调用
                }
            }
        }

## 广度遍历 ##

/** * Created by lilongsheng on 2017/8/2. * 图的广度遍历 */
    public class BreadthFirstSearchTraverse { 
    
        boolean[] visited = new boolean[GraphEntity.MAX_VEX];
    
        public void BFSTraverse(GraphEntity G){
    
            int i , j;
            Queue queue;
            //将图的所有顶点标记为未访问
            for (i = 0; i < G.getNumVertexes(); i++){
                visited[i] = false;
            }
    
            //对每一个顶点做循环
            for (i = 0; i < G.getNumVertexes(); i++){
    
                //若是未访问过的顶点就处理
                if (!visited[i]){
    
                    visited[i] = true;//设置当前顶点访问过
                    System.out.println("顶点{"+i+"}");
                    //将此顶点入队
                    enterQueue(i);
                    //若当前队列不为空
                    while (!queryEmptyQueue()){
    
                        //元素出队列，遍历该出队元素的所有没有访问过的邻接顶点
                        deleteQueue(i);
    
                        for (j = 0; j < G.getNumVertexes(); j++){
                            //判断其它顶点与该顶点存在边且未访问过
                            if (G.arc[i][j] == "1" && !visited[j]){
    
                                visited[j] = true;//将找到的顶点标记为已访问
                                System.out.println("顶点{"+ j +"}");
    
                                deleteQueue(i);//将找到的顶点入队
    
                            }
                        }
                    }
                }
            }
        }

# 与网络爬虫关系 #

我们可以把互联网上的网页看成一个节点，连接各个网页的超链接看做边，有了超链接我们可以从任何一个节点出发利用图遍历算法访问每一个网页，这是最简单的“网络爬虫”，互联网上的网页数量级都在亿级别，为提高效率一般用利用散列表来存储哪些网页下载过，一个商业的网络爬虫由成千上万个服务器组成。  
     这里面有几个问题需要思考，选择哪一个遍历算法好些？网站频繁建立连接？浏览器内核工程师解析内页与url？好爬虫需要在有限的时间里最多的爬下最重要的内容。

### 广度遍历问题 ###

#### 第一个循环的作用？ ####

对于代码里面的每行需要知道它的意思我们才能够写出来代码，刚开始看了代码不太理解，有第一个循环是因为图并不一定是连通图，可能它的一部分并没有连通这样如果从一个顶点开始，其它顶点就会有遗漏，为了充分遍历到每一个顶点，我们首先写了一个循环，该循环对于连通图其实是循环一次里面，我们会通过visited数组来判断该顶点是否被访问过，如果访问过，不会再执行后面的逻辑。

#### 广度遍历的原则是如何把握？ ####

既然是广度遍历那么在遍历图的时候就需要遵从这个原则，代码是怎么控制访问顺序符合这一原则的，我觉得主要是通过两点来达到这个目的，第一个是队列先进先出的这种性格；第二个是当前访问顶点的所有未访问邻接顶点访问完时，终止改成循环，从队列取出元素继续循环；这两个条件保证拿出来上一层某个节点A时，和A同一层的B节点的未访问邻接顶点已经都入队且在后面，出来的元素都是A层同层节点。

# 总结 #

图这种数据结构应用范围很广泛，在各种算法设计中也是基本的数据结构，它的重要性在解决某些重要问题的时候会显示出来重要作用。

[SouthEast]: /images/20220610/247abcdf9f4a489eaed20ddbd29df18e.png
[SouthEast 1]: /images/20220610/17502596b32544d89adc2c051d6a4fc2.png