Java实现图的广度优先遍历和深度优先遍历

2021/7/27 14:06:26

编程Tag： node 遍历 Java 访问优先 bfs 顶点 tmpArcNode

本文主要是介绍Java实现图的广度优先遍历和深度优先遍历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本文所有代码全部基于Java实现图的存储和创建一文所实现的带权无向图。

广度优先遍历

广度优先搜索(Breadth-First-Search,BFS) 类似于二叉树的层序遍历。基本思想是：首先访问起始顶点v，接着由v出发，依次访问未访问过的邻接顶点w1,w2,…wi,然后依次访问w1,w2,…wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问他们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时仍有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点都被访问过。

很明显每一次BFS只能遍历到一个连通分量的所有顶点，如果图不是连通图的话，一次BFS就无法遍历所有顶点了，于是为了遍历非连通图，我们引入一个辅助数组private static boolean[] visited;,visited[i]表示下标未i的顶点是否已被访问过，这样每执行完一次BFS后，检查该数组中是否还有值未false的值，如果有就从该下标开始继续BFS，如果没有则说明图已经遍历完成。

BFS代码

public ArrayList<String> BFSTraverse(){
    //对图进行广度优先遍历
    //访问标记数组初始化
    graph_t.visited = new boolean[this.vexNum];
    for (int i = 0; i < this.vexNum; i++) {
        visited[i] = false;
    }
    ArrayList<String> res = new ArrayList<>();
    for (int i = 0; i < this.vexNum; i++) {
        if(!graph_t.visited[i]){
            res =  this.BFS(i,res);
        }
    }
    return res;
}

private ArrayList<String> BFS(int vnodeIndex,ArrayList<String> tmpRes){
    //tmpRes保存临时结果，该方法执行一次只能遍历一个连通分量，需要上一个方法才能遍历整个非连通图
    //初始化辅助队列
    LinkedList<VNode> queue = new LinkedList<>();
    //讲遍历起点放入
    queue.offer(this.vertices.get(vnodeIndex));
    while (!queue.isEmpty()){
        //从队列中弹出一个顶点并访问
        VNode node = queue.remove();
        //获取该顶点的下标
        int curIndex = this.containVnode(node.getName());
        if (!graph_t.visited[curIndex]){
            //如果该店还未被访问则访问它
            graph_t.visited[curIndex] = true;
            tmpRes.add(node.getName());
            //利用临时变量遍历node的所有邻接点，并加入队列
            ArcNode tmpArcNode = new ArcNode(node.first);
            while (tmpArcNode != null){
                //小的设计缺陷，无法通过边点快速找到与node相连的顶点
                if (node.getName().equals(tmpArcNode.getNode1().getName())){
                    //此时node2试邻接点
                    queue.offer(tmpArcNode.getNode2());
                }else{
                    //否则node1为邻接点
                    queue.offer(tmpArcNode.getNode1());
                }
                tmpArcNode = tmpArcNode.next;
            }
        }
    }
    return tmpRes;
}

深度优先遍历

与广度优先搜索不同，深度优先搜索(Depth-First-Search,DFS) 类似于树的先序遍历。如其名称中所暗含的意思一样，这中搜索算法搜索策略是尽可能“深”地搜索一个图。
他的基本思想如下：首先访问图中某一起始点v，然后由v出发，访问与v邻接且未被访问任一顶点w1,再访问与w1邻接且未被访问地任一顶点w2…重复上述过程，依次退回到最近被访问的顶点，若它还有邻接点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

一次DFS和一次BFS一样都具有不能完全遍历非连通图的问题，所有采取了和BFS相同的处理方法。

DFS代码

public ArrayList<String> DFSTraverse(){
    //对图进行深度优先遍历
    //访问标记数组初始化
    graph_t.visited = new boolean[this.vexNum];
    for (int i = 0; i < this.vexNum; i++) {
        visited[i] = false;
    }
    ArrayList<String> res = new ArrayList<>();
    for (int i = 0; i < this.vexNum; i++) {
        if(!graph_t.visited[i]){
            res =  this.DFS(i,res);
        }
    }
    return res;
}
private ArrayList<String> DFS(int vnodeIndex,ArrayList<String> tmpRes){
    //该方法与BFS思路一样只是将队列改为栈
    Stack<VNode> stack = new Stack<>();
    stack.push(this.vertices.get(vnodeIndex));
    while (!stack.isEmpty()){
        VNode node = stack.pop();
        int curIndex = this.containVnode(node.getName());
        if (!graph_t.visited[curIndex]){
            tmpRes.add(node.getName());
            graph_t.visited[curIndex] = true;
            ArcNode tmpArcNode = node.first == null ? null : new ArcNode(node.first);
            while (tmpArcNode != null){
                if (node.getName().equals(tmpArcNode.getNode1().getName())){
                    //此时node2试邻接点,精确获取当前图中的顶点对象
                    stack.push(this.getVNodeByName(tmpArcNode.getNode2().getName()));
                }else{
                    //否则node1为邻接点
                    stack.push(this.getVNodeByName(tmpArcNode.getNode1().getName()));
                }
                tmpArcNode = tmpArcNode.next;
            }
        }
    }
    return tmpRes;
}

运行结果

测试运行的代码如下：

public static void main(String[] args) {
    graph_t g = new graph_t();
    g.create();
    g.showGraph();
    System.out.println("---------------BFS-----------------------");
    ArrayList<String> bfsRes = g.BFSTraverse();
    for (int i = 0; i < g.getVexNum(); i++) {
        System.out.print(bfsRes.get(i) + " ");
    }
    System.out.println();
    System.out.println("---------------DFS-----------------------");
    ArrayList<String> dfsRes = g.DFSTraverse();
    for (int i = 0; i < g.getVexNum(); i++) {
        System.out.print(dfsRes.get(i) + " ");
    }
}