图的存储、深度优先遍历和广度优先遍历

Myth丶恋晨 2023-06-12 08:34 10阅读 0赞

### 目录 ###

*  图的存储
 *  深度优先遍历
 *  广度优先遍历
 *  疑问

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]

# 图的存储 #

在考虑代码实现中，我们可以通过一个列表来存储所有的结点，数组来存储所有边。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]

package com.hong.graph;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Graph { 
    
        private ArrayList<String> vertexList; //存储顶点集合
        private int[][] edges; //存储图对应的邻结矩阵
        private int numOfEdges; //表示边的数目
        //定义给数组boolean[], 记录某个结点是否被访问
        private boolean[] isVisited;
    
        //构造器
        public Graph(int n) { 
            //初始化矩阵和vertexList
            edges = new int[n][n];
            vertexList = new ArrayList<String>(n);
            numOfEdges = 0;
    
        }
    
        //图中常用的方法
        //显示图对应的矩阵
        public void showGraph() { 
            for(int[] link : edges) { 
                System.out.println(Arrays.toString(link));
            }
        }
    
        //插入结点
        public void insertVertex(String vertex) { 
            vertexList.add(vertex);
        }
        //添加边
        /** * * @param v1 表示点的下标即使第几个顶点 "A"-"B" "A"->0 "B"->1 * @param v2 第二个顶点对应的下标 * @param weight 表示 */
        public void insertEdge(int v1, int v2, int weight) { 
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    }

# 深度优先遍历 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]  
我们以上面的图来举例说明图的深度优先遍历是怎么样的一个过程。

1.  以A为起始节点，找到它的第一个邻接节点B；
2.  接着以B为起始节点（这里其实是对B的一个递归过程），找到它的第一个邻接节点C；
3.  然后，以B为起始节点（对C的一个递归过程），发现它的邻接节点A和B都已经被访问过了，退出C的递归；
4.  这时候，需要对B进行回溯，找到B的第二个邻接节点D；
5.  再接着，以D为起始节点（对D的一个递归过程），发现它的邻接节点B已经被访问过了，退出D的递归；
6.  继续对B进行回溯，找到B的第三个邻接节点E；
7.  再接着，以E为起始节点（对E的一个递归过程），发现它的邻接节点B已经被访问过了，退出E的递归；
8.  继续对B进行回溯，发现没有其他的邻接节点了，退出B的递归；
9.  此时，就需要对A进行回溯了，找到它的第二个邻接点D，发现它的邻接节点B已经被访问过了，退出D的递归；
10. 最后，又对A进行回溯， 没有其他的邻接节点了，完成对A的整个深度优先遍历；
11. 下面，就是对其他剩下的所有节点，都执行以上10步的操作（但其实很多节点都已经被访问过了，所以很多节点都是跳过的）。

/** * 深度优先遍历主方法 */
    public void deepTraversing(){ 
        isVisited = new boolean[vertexList.size()];
        for (int i=0; i<vertexList.size(); i++){ 
            if (!isVisited[i]){ 
                deepTraversing(i);
            }
        }
    }
    
    /** * 以vertex为起点，进行深度遍历递归 * @param vertex */
    private void deepTraversing(int vertex){ 
        System.out.print(vertexList.get(vertex) + "->");
        isVisited[vertex] = true;
    
        // 获取vertex的第一个邻接节点
        int next = getNextEdges(vertex, 0);
        while (next != -1){ 
            if (!isVisited[next]){ 
                deepTraversing(next);
            } else{ 
                // 如果该邻接节点已经被访问过，则获取下一个邻接节点
                next = getNextEdges(vertex, next+1);
            }
        }
    
    }
    
    /** * 获取vertex从初始位置为start的下一个邻接节点 * @param vertex * @param start * @return */
    private int getNextEdges(int vertex, int start){ 
        for (int j=start; j<vertexList.size(); j++){ 
            if (edges[vertex][j] == 1){ 
                return j;
            }
        }
        return -1;
    }

# 广度优先遍历 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]  
广度优先遍历比深度优先遍历简单很多，比较容易理解。仍然以上面的图为例子：

1.  从第一个节点A开始，依次找到它的所有邻接节点；
2.  然后，轮到第二个节点B，依次找到它的所有邻接节点（未被访问的）；
3.  剩下的节点类似…

/** * 广度优先遍历方法 */
    private void breadthTraversing(){ 
        isVisited = new boolean[vertexList.size()];
        int w;
        for (int v=0; v<vertexList.size(); v++){ 
            // 打印顶点v的所有邻接节点(未被访问过的)
            if (!isVisited[v]){ 
                System.out.print(vertexList.get(v) + "->");
                isVisited[v] = true;
            }
            w = getNextEdges(v, 0); // 获取v的第一个邻接节点
            while (w != -1){ 
                if (!isVisited[w]){ 
                    System.out.print(vertexList.get(w) + "->");
                    isVisited[w] = true;
                }
                w = getNextEdges(v, w+1);
            }
        }
    }

**完整代码已上传至[GitHub][]**

# 疑问 #

为什么很多人对图的广度优先遍历，都是通过队列来实现的。就感觉是对前面的节点进行循环操作时，先帮后面的一些节点完成遍历；  
但，其实不用队列的话，就是每个节点完成自己的遍历。  
有大神看到的帮忙解答一下！！！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114503444.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: /images/20230531/12ec60aef8bb45a08dceea593450751b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/e825c44ba0904441bffc9c834174a0a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]: /images/20230531/e2eaaa5be77144d7a63ea5aea2b35061.png
[GitHub]: https://github.com/SGyuanshi/DataStructures/blob/master/src/com/hong/graph/Graph.java
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]: /images/20230531/3a7cfe6b654841269eec4d922c49f2e6.png
[20200430114503444.jpg]: /images/20230531/9aca7c2ccb8e4979acb02e8d77d5b166.png