【数据结构与算法之图结构】图的遍历

ゝ一纸荒年。 2024-03-25 16:38 110阅读 0赞

#### 【数据结构与算法之图结构】图的遍历 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之图结构】图的遍历
         *   *   *  1 深度优先搜索遍历
                 *  2 广度优先搜索遍历

###### 1 深度优先搜索遍历 ######

深度优先，从图中一个顶点出发，先访问该顶点，再依次从该顶点未被访问过的邻接点开始继续深搜，递归。

Java代码实现：

// 定义一个成员变量数组, 记录遍历图时已访问的节点
    int[] visited;
    
    /**
     * 从vNodes[vIndex] 节点开始深度优先遍历
     *
     * @param vIndex
     */
    private void DFS(int vIndex) {
        
        visit(vIndex); // 访问打印vIndex 节点数据信息
        visited[vIndex] = 1;  // 置1表示已经访问过
    
        // 找到顶点v 的第1个邻接点, 如果有返回顶点下标，如果没有，返回-1
        int w = getFirstAdj(vIndex);
    
        while (w != -1) {
        
            if (visited[w] == 0) {
         // 该顶点未被访问
                DFS(w); // 递归深搜
            }
    
            // 找到顶点v的 下一个邻接点
            w = getNextAdj(vIndex, w);
        }
    }
    
    /**
     * 主算法
     */
    public void travelByDFS() {
        
        // 创建访问数组, 记录已访问节点
        visited = new int[vNodes.length];
        for (int i = 0; i < vNodes.length; i++) {
        
            visited[i] = 0; // 全部初始化为0
        }
    
        for (int i = 0; i < vNodes.length; i++) {
        
            if (visited[i] == 0) {
        
                DFS(i);
            }
        }
    }
    
    private int getFirstAdj(int vIndex) {
        
        if (vNodes[vIndex].firstArc != null) {
        
            return vNodes[vIndex].firstArc.adjvex;
        }
        return -1;
    }
    
    private int getNextAdj(int vIndex, int w) {
        
        ArcNode p;
        p = vNodes[vIndex].firstArc;
    
        while (p != null) {
        
            if (p.adjvex == w && p.next != null) {
        
                return p.next.adjvex;
            }
    
            p = p.next;
        }
        return -1;
    }
    
    
    //访问函数
    private void visit(int vIndex) {
        
        System.out.print(vNodes[vIndex].data + " ");
    }

测试

public static void main(String[] args) {
        
    
        int v[] = {
        2, 9, 6, 3, 7};
        int arc[] = {
        1, 2, 3, -1, 0, 2, -1, 1, 0, -1, 0, 4, -1, 3};
        MyGragh gragh = new MyGragh();
    
        gragh.createGragh(v, arc);
        System.out.println("深搜结果");
        gragh.travelByDFS();
    
    }

运行结果

![在这里插入图片描述][271a367f6c77441b9c30242467c91a38.png_pic_center]

###### 2 广度优先搜索遍历 ######

广度优先搜索遍历是一种按层次遍历的算法。它的遍历顺序是先访问顶点 v 0 v\_0 v0，再访问离顶点 v 0 v\_0 v0 最近的顶点  v 1 , v 2 , . . , v n v\_1,v\_2,..,v\_n v1,v2,..,vn ，然后依次遍历离 v 1 , v 2 , . . . , v n v\_1,v\_2,...,v\_n v1,v2,...,vn 最近的顶点。

【以 v 0 v\_0 v0 为中心，一层一层向外扩展】

Java实现：

void BFS(int vIndex) {
        
            visit(vIndex); // 访问vIndex 顶点信息
            visited[vIndex] = 1; // 置1表示已访问
    
            MyQueue queue = new MyQueue(); // 创建一个队列来存放图顶点对象
            queue.enQueue(vIndex); // 顶点下标vIndex 入队
    
            while (queue.getQueueLength() != 0) {
        
                int v = queue.deQueue(); // 队头元素取出
                int w = getFirstAdj(v); // 找到顶点v 的第一个邻接点，如果没有返回-1
                while (w != -1) {
        
                    if (visited[w] == 0) {
        
                        visit(w);
                        queue.enQueue(w);
                        visited[w] = 1;
                    }
                    w = getNextAdj(v, w);
                }
    
            }
        }
    
        // 主算法
        public void travelByBFS() {
        
            // 广度优先搜索遍历图
            visited = new int[vNodes.length];
            for (int i = 0; i < vNodes.length; i++) {
        
                visited[i] = 0;
            }
    
            for (int i = 0; i < vNodes.length; i++) {
        
                if (visited[i] == 0) {
        
                    BFS(i);
                }
            }
        }

测试

public static void main(String[] args) {
        
    
        int v[] = {
        2, 9, 6, 3, 7};
        int arc[] = {
        1, 2, 3, -1, 0, 2, -1, 1, 0, -1, 0, 4, -1, 3};
        MyGragh gragh = new MyGragh();
    
        gragh.createGragh(v, arc);
        System.out.println("广搜结果");
        gragh.travelByBFS();
    
    }

运行结果

![在这里插入图片描述][bd592a36624749d6af3552c02b23540d.png_pic_center]

当然这里很巧的是和深搜结果一样了。

[271a367f6c77441b9c30242467c91a38.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/adf938d8bbba41b28c42663feb00b027.png
[bd592a36624749d6af3552c02b23540d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/945cc16a0acf425da57557de551cf709.png