欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深度优先搜索算法(java语言)

程序员文章站 2022-06-11 11:10:22
...

           我们在学习了图之后,需要一种机制来遍历图,图的遍历算法也叫图搜索算法。与树的遍历算法(中序、前序、后序以及层序遍历)一样,图搜索算法也可以看做从图的某个源点开始,通过遍历和标记顶点来搜索图。下面讨论两种遍历图的算法:

          (1)深度优先搜索(DFS)。

          (2)广度优先搜索(BFS)。

一、深度优先搜索

       例子如下图所示:

         深度优先搜索算法(java语言)

从该图的基础上遍历该图:

                        使用深度优先搜索算法(DFS),使用了两种方法,递归和非递归方法:

import java.util.Stack;

public class DFSTest {

    // 存储节点信息
    private char[] vertices;

    // 存储边信息(邻接矩阵)
    private  int[][] arcs;  

    // 图的节点数
    private int vexnum;

    // 记录节点是否已被遍历
    private boolean[] visited;

    // 初始化
    public DFSTest(int n) {
          vexnum = n;
          vertices = new char[n];
          arcs = new int[n][n];
          visited = new boolean[n];
          for (int i = 0; i < vexnum; i++) {
             for (int j = 0; j < vexnum; j++) {
                 arcs[i][j] = 0;
             }
          }
    }

    // 添加边(无向图)
    public void addEdge(int i, int j) {
          // 边的头尾不能为同一节点
          if (i == j)return;

          arcs[i][j] = 1;
          arcs[j][i] = 1;
    }

    // 设置节点集
    public void setVertices(char[] vertices) {
        this.vertices = vertices;
    }

    // 设置节点访问标记
    public void setVisited(boolean[] visited) {
        this.visited = visited;
    }

    // 打印遍历节点
    public void visit(int i){
        System.out.print(vertices[i] + " ");
    }

    // 从第i个节点开始深度优先遍历
    private void traverse(int i){
        // 标记第i个节点已遍历
        visited[i] = true;
        // 打印当前遍历的节点
        visit(i);

        // 遍历邻接矩阵中第i个节点的直接联通关系
        for(int j=0;j<vexnum;j++){
            // 目标节点与当前节点直接联通,并且该节点还没有被访问,递归
            if(arcs[i][j]==1 && visited[j]==false){
                traverse(j);
            }
        }
    }

    // 图的深度优先遍历(递归)
    public void DFSTraverse(){
        // 初始化节点遍历标记
        for (int i = 0; i < vexnum; i++) {
            visited[i] = false;
        }

        // 从没有被遍历的节点开始深度遍历
        for(int i=0;i<vexnum;i++){
            if(visited[i]==false){
                // 若是连通图,只会执行一次
                traverse(i);
            }
        }
    }

    // 图的深度优先遍历(非递归)
    public void DFSTraverse2(){
        // 初始化节点遍历标记
        for (int i = 0; i < vexnum; i++) {
            visited[i] = false;
        }

        Stack<Integer> s = new Stack<Integer>();
        for(int i=0;i<vexnum;i++){
            if(!visited[i]){
                //连通子图起始节点
                s.add(i);
                do{ 
                    // 出栈
                    int curr = s.pop();

                    // 如果该节点还没有被遍历,则遍历该节点并将子节点入栈
                    if(visited[curr]==false){
                        // 遍历并打印
                        visit(curr);
                        visited[curr] = true;

                        // 没遍历的子节点入栈
                        for(int j=vexnum-1; j>=0 ; j-- ){
                            if(arcs[curr][j]==1 && visited[j]==false){
                                s.add(j);
                            }
                        }
                    }
                }while(!s.isEmpty());
            }
        }
    }

    public static void main(String[] args) {
        DFSTest g = new DFSTest(9);
        char[] vertices = {'A','B','C','D','E','F','G','H','I'};
        g.setVertices(vertices);

        g.addEdge(0, 1);
        g.addEdge(0, 5);
        g.addEdge(1, 0);
        g.addEdge(1, 2);
        g.addEdge(1, 6);
        g.addEdge(1, 8);
        g.addEdge(2, 1);
        g.addEdge(2, 3);
        g.addEdge(2, 8);
        g.addEdge(3, 2);
        g.addEdge(3, 4);
        g.addEdge(3, 6);
        g.addEdge(3, 7);
        g.addEdge(3, 8);
        g.addEdge(4, 3);
        g.addEdge(4, 5);
        g.addEdge(4, 7);
        g.addEdge(5, 0);
        g.addEdge(5, 4);
        g.addEdge(5, 6);
        g.addEdge(6, 1);
        g.addEdge(6, 3);
        g.addEdge(6, 5);
        g.addEdge(6, 7);
        g.addEdge(7, 3);
        g.addEdge(7, 4);
        g.addEdge(7, 6);
        g.addEdge(8, 1);
        g.addEdge(8, 2);
        g.addEdge(8, 3);

        System.out.print("深度优先遍历(递归):");
        g.DFSTraverse();

        System.out.println();

        System.out.print("深度优先遍历(非递归):");
        g.DFSTraverse2();
    }

}

执行结果截图为:

深度优先搜索算法(java语言)


如果使用邻接表来表示图,则DFS算法的时间复杂度为O(V+E),如果用邻接矩阵来表示图,时间复杂度为O(V平方)

DFS的应用:生成森林、连同分量、路径、环路且内存开销比BFS要小很多。


ps:BFS算法和这两者的区别下一节我会介绍!  

最后:欢迎大家评论交流,互相学习,共同进步!