数据结构 - 图（图的深度优先和广度优先）

叁歲伎倆 2023-07-12 05:11 21阅读 0赞

### 图的基本介绍 ###

**为什么要有图这种数据结构**

> 1.  数据结构有线性表和树
> 2.  线性表局限与一个直接前驱和一个直接后继的关系
> 3.  树也只能右一个直接前驱也就是父节点
> 4.  当我们需要表示多对多的关系时，这里我们就需要用到图这种数据结构

图是一种数据结构，其中节点可以**具有零个或者多个相邻的元素**。2个节点之间的连接称为边。节点也可以称为顶点。 如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]  
**图的常用概念**  
1. 顶点（vertex）  
2. 边（edge）  
3. 路径  
4. 无向图（如图）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 1]  
5. 有向图 （如下图）  
6. 带权图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 2]

### 图的表示方式 ###

图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。

**邻接矩阵**

> 邻接矩阵是表示图形中**顶点之间相邻关系**的矩阵，对于n个顶点的图而言，矩阵是的row和 col表示的是1…n个点。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 3]

**邻接表**

> 1.  邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
> 2.  邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成  
>     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 4]

**图的案例入门**  
要求：代码实现如下图结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 5]  
思路：  
保存顶点用ArrayList集合 ，保存顶点之间相邻关系的用邻接矩阵，即二维数组表示。

public class Graph { 
        // 存放顶点的集合
        private List<String> vertexList;
        // 邻接矩阵，存放顶点关系
        private int[][] edges;
        // 边的数目
        private int numOfEdges;
    
        public Graph(int n) { 
            // n表示顶点的个数
            vertexList = new ArrayList<>(n);
            edges = new int[n][n];
            numOfEdges = 0;
        }
    
        /** * 添加顶点的方法 * @param vertex */
        public void addVertex(String vertex) { 
            vertexList.add(vertex);
        }
    
        /** * 获取顶点个数 */
        public int getVertexNum() { 
            return vertexList.size();
        }
    
        /** * 返回对于下标的顶点 * @param i * @return */
        public String getVertex(int i) { 
            return vertexList.get(i);
        }
    
        /** * 添加边 * @param v1 表示第几个下标的顶点的位置 * @param v2 表示第二个顶点的下标 * @param weight 边的权 */
        public void addEdge(int v1, int v2, int weight) { 
            // 表示下标v1和v2顶点的边
            edges[v1][v2] = weight;
            // 表示下标v2和v1顶点的边
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
        /** * 遍历顶点 */
        public void listVertex() { 
            for (String s : vertexList) { 
                System.out.print(s + " ");
            }
        }
    
        /** * 遍历邻接矩阵，边 */
        public void listEdge() { 
            for (int[] edge : edges) { 
                System.out.println(Arrays.toString(edge));
            }
        }
    }

测试

public class MyTest { 
    
        public static void main(String[] args) { 
            Graph graph = new Graph(5);
         	String[] vertexs = { "A", "B", "C", "D", "E"};
            for (String vertex : vertexs) { 
                // 添加顶点
                graph.addVertex(vertex);
            }
    
            // 添加边 A-B
            graph.addEdge(0,1,1);
            // 添加边 A-C
            graph.addEdge(0,2,1);
            // 添加边 B-C
            graph.addEdge(1,2,1);
            // 添加边 B-D
            graph.addEdge(1,3,1);
            // 添加边 B-E
            graph.addEdge(1,4,1);
    
            // 遍历顶点
            graph.listVertex();
            System.out.println();
            // 遍历边
            graph.listEdge();
        }
    }

输出结果

A B C D E 
    [0, 1, 1, 0, 0]
    [1, 0, 1, 1, 1]
    [1, 1, 0, 0, 0]
    [0, 1, 0, 0, 0]
    [0, 1, 0, 0, 0]

### 图的深度优先遍历 ###

*  图的遍历介绍
    
    > 所谓图的遍历，即使对节点的访问。一个图右很多节点，如何遍历这些节点，我们需要一定的策略，一般有两种策略：1.深度优先遍历，2.广度优先遍历
 *  图的深度优先遍历（Depth First Search）
    
    >  *  深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
    >  *  我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
    >  *  显然，深度优先搜索是一个递归的过程
 *  深度优先遍历算法步骤
    
    > 1.  访问初始节点V，并标记该节点V为已访问。
    > 2.  查找节点V的第一个邻接节点W。
    > 3.  若W存在，则执行步骤4，若W不存在，则回到步骤1，将从V的下一个连接节点继续
    > 4.  若W未被访问，对W进行深度优先遍历递归（即把 W当做另一个V，然后进行步骤123）。
    > 5.  若W已被访问，则查找V的W的邻接节点的下一个邻接节点，然后转到步骤3。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 6]

### 图的广度优先遍历 ###

图的广度优先搜索类似于一个分成搜索过程，广度优先遍历需要使用一个队列以保持访问过节点的顺序，以便按这个顺序来访问这些节点的邻接节点

*  广度优先遍历算法步骤
    
    > 1.  访问初始节点V，并标记节点V为已访问。
    > 2.  节点V入队列
    > 3.  当队列非空时，继续执行，否则算法结束
    > 4.  出队列，取得队头结点u。
    > 5.  查找结点u的第一个邻接结点w。
    > 6.  若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个 步骤  
    >     6.1 若结点w尚未被访问，则访问结点w并标记为已访问。  
    >     6.2 结点w入队列  
    >     6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

### 深度优先遍历和广度优先遍历代码示例 ###

主要方法：深度优先（dfs），广度优先（bfs）

public class Graph { 
        // 存放顶点的集合
        private List<String> vertexList;
        // 邻接矩阵，存放顶点关系
        private int[][] edges;
        // 边的数目
        private int numOfEdges;
        // 是否被访问
        private boolean[] isVisited;
    
        public Graph(int n) { 
            // n表示顶点的个数
            vertexList = new ArrayList<>(n);
            edges = new int[n][n];
            numOfEdges = 0;
    
        }
    
        /** * 添加顶点的方法 * @param vertex */
        public void addVertex(String vertex) { 
            vertexList.add(vertex);
        }
    
        /** * 查找下标为index顶点的的第一个邻接节点 * @param index * @return 返回找到的下标 ,没有找到就返回-1 */
        public int getFirstNeighbor(int index) { 
            for (int i = 0; i < vertexList.size(); i++) { 
                if (edges[index][i] == 1){ 
                    return i;
                }
            }
            return -1;
        }
    
        /** * * @param index 初始顶点下标 * @param firstNeighbor 初始顶点的第一个个邻接节点 * @return 返回初始节点的下一个邻接节点的下标，没有就返回-1 */
        public int getNextNeighbor(int index, int firstNeighbor) { 
            for (int i = firstNeighbor + 1; i < vertexList.size(); i++) { 
                if (edges[index][i] == 1) { 
                    return i;
                }
            }
            return -1;
        }
    
        /** * 深度优先遍历 * @param isVisited 要访问的节点是否被访问 * @param index 要访问的初始节点 */
        private void dfs(boolean[] isVisited, int index) { 
            isVisited = new boolean[vertexList.size()];
            // 1. 访问初始节点，并把该节点标记为已访问
            System.out.print(vertexList.get(index) + "->");
            isVisited[index] = true;
            //2. 查找节点index的第一个邻接节点
            int firstNeighbor = getFirstNeighbor(index);
            //3. firstNeighbor != -1 说明有邻接节点
            while ( firstNeighbor != -1) { 
                // 判断这邻接节点是否被访问
                if (!isVisited[firstNeighbor]) { 
                    //4. 没有被访问，则进行递归,把firstNeighbor当成初始节点进行递归访问
                    dfs(isVisited, firstNeighbor);
                }
                // 5.该邻接节点已被访问，则查找index除了firstNeighbor节点的下一个邻接节点
                firstNeighbor = getNextNeighbor(index, firstNeighbor);
            }
        }
    
        /** * 深度优先遍历 */
        public void dfs () { 
            for (int i = 0; i < vertexList.size(); i++) { 
                if (!isVisited[i]) { 
                    dfs(isVisited, i);
                }
            }
        }
    
        /** * 广度优先遍历 * @param isVisited * @param index */
        private void bfs(boolean[] isVisited, int index) { 
            isVisited = new boolean[vertexList.size()];
            // 定义一个队列，来保存访问过节点的顺序
            LinkedList<Integer> queue = new LinkedList<>();
    
            // 1. 访问初始节点，标记为已访问
            System.out.println(vertexList.get(index) + "->");
            isVisited[index] = true;
            // 将访问过的节点入队列,注意加 到最后一个，取的时候是第一个
            queue.addLast(index);
            // 当队列不为空时，一直循环执行
            int v;  // 用来存放队列里去除的节点下标
            while (!queue.isEmpty()) { 
                // 取出队列的头节点
                v = queue.removeFirst();
                // 查找节点v的邻接节点
                int neighbor = getFirstNeighbor(v);
                // 若邻接节点存在
                while (neighbor != -1) { 
                    // 若该节点未被访问
                    if (!isVisited[neighbor]) { 
                        System.out.print(vertexList.get(neighbor) + "->");
                        // 标记为已访问
                        isVisited[neighbor] = true;
                        // 加入队列
                        queue.addLast(neighbor);
                    }
                    // 查找v的继neighbor的下一个邻接节点
                    neighbor = getNextNeighbor(v, neighbor);
                }
            }
        }
    
        public void bfs() { 
            for (int i = 0; i < vertexList.size(); i++) { 
                if (!isVisited[i]) { 
                    bfs(isVisited,i);
                }
            }
        }
    
        /** * 获取顶点个数 */
        public int getVertexNum() { 
            return vertexList.size();
        }
    
        /** * 返回对于下标的顶点 * @param i * @return */
        public String getVertex(int i) { 
            return vertexList.get(i);
        }
    
        /** * 添加边 * @param v1 表示第几个下标的顶点的位置 * @param v2 表示第二个顶点的下标 * @param weight 边的权 */
        public void addEdge(int v1, int v2, int weight) { 
            // 表示下标v1和v2顶点的边
            edges[v1][v2] = weight;
            // 表示下标v2和v1顶点的边
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
        /** * 遍历顶点 */
        public void listVertex() { 
            for (String s : vertexList) { 
                System.out.print(s + " ");
            }
        }
    
        /** * 遍历邻接矩阵，边 */
        public void listEdge() { 
            for (int[] edge : edges) { 
                System.out.println(Arrays.toString(edge));
            }
        }
    }

测试类

public class MyTest { 
        public static void main(String[] args) { 
            Graph graph = new Graph(5);
            String[] vertexs = { "A", "B", "C", "D", "E"};
            for (String vertex : vertexs) { 
                // 添加顶点
                graph.addVertex(vertex);
            }
    
            // 添加边 A-B
            graph.addEdge(0,1,1);
            // 添加边 A-C
            graph.addEdge(0,2,1);
            // 添加边 B-C
            graph.addEdge(1,2,1);
            // 添加边 B-D
            graph.addEdge(1,3,1);
            // 添加边 B-E
            graph.addEdge(1,4,1);
    
            System.out.println("对图进行深度优先遍历：");
            graph.dfs();
    
            System.out.println();
            System.out.println("广度优先遍历");
            graph.bfs();
        }
    }

测试结果

对图进行深度优先遍历：
    A->B->C->D->E->
    广度优先遍历
    A->B->C->D->E->

**总结**：注意分析代码，深度优先和广度优先主要区别在于：

1.  深度优先是先从初始节点开始，寻找到他的下一个邻节点，然后在以这个**邻接点为初始节点**，继续重复这些操作。
2.  广度优先是从初始节点开始，寻找他的邻节点，然后再继续寻找他下一个邻节点，**直到把他所有的邻节点找到**，在换成队列另一个节点继续重复上面的操作，

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030709582938.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200307100153648.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200307100333767.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200307100907587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200307101424248.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200307101616314.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200307121031133.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z5ajEzOTI1NDc1OTU3,size_16,color_FFFFFF,t_70