图的遍历DFS&BFS

约定不等于承诺〃 2022-05-09 15:18 266阅读 0赞

版权声明：本文为博主原创文章，未经博主允许不得转载。	https://blog.csdn.net/qq_24486393/article/details/50270481
    图的深度优先遍历(DFS)和广度优先遍历(BFS），DFS利用递归来实现比较易懂，DFS非递归就是将需要的递归的元素利用一个栈Stack来实现，以达到递归时候的顺序，而BFS则是利用一个队列Queue来实现。
    
    package DataStructure;
    
    import java.util.LinkedList;  
    import java.util.Queue;  
    import java.util.Stack;
    
    public class Graph {   
        private int number = 9;  
        private boolean[] flag;  
        private String[] vertexs = { "A", "B", "C", "D", "E", "F", "G", "H", "I" };  
        private int[][] edges = {   
                { 0, 1, 0, 0, 0, 1, 1, 0, 0 }, 
                { 1, 0, 1, 0, 0, 0, 1, 0, 1 }, 
                { 0, 1, 0, 1, 0, 0, 0, 0, 1 },  
                { 0, 0, 1, 0, 1, 0, 1, 1, 1 }, 
                { 0, 0, 0, 1, 0, 1, 0, 1, 0 }, 
                { 1, 0, 0, 0, 1, 0, 1, 0, 0 },  
                { 0, 1, 0, 1, 0, 1, 0, 1, 0 }, 
                { 0, 0, 0, 1, 1, 0, 1, 0, 0 }, 
                { 0, 1, 1, 1, 0, 0, 0, 0, 0 }   
                };  
    
        void DFSTraverse() {  
            flag = new boolean[number];  
            for (int i = 0; i < number; i++) {  
                if (flag[i] == false) {// 当前顶点没有被访问  
                    DFS(i);  
                }  
            }  
        }  
    
        void DFS(int i) {  
            flag[i] = true;// 第i个顶点被访问  
            System.out.print(vertexs[i] + " ");  
            for (int j = 0; j < number; j++) {  
                if (flag[j] == false && edges[i][j] == 1) {  
                    DFS(j);  
                }  
            }  
        }  
    
        void DFS_Map(){
            flag = new boolean[number];
            Stack<Integer> stack =new Stack<Integer>();
            for(int i=0;i<number;i++){
                if(flag[i]==false){
                    flag[i]=true;
                    System.out.print(vertexs[i]+" ");
                    stack.push(i);
                }
                while(!stack.isEmpty()){
                    int k = stack.pop();
                    for(int j=0;j<number;j++){
                        if(edges[k][j]==1&&flag[j]==false){
                            flag[j]=true;
                            System.out.print(vertexs[j]+" ");
                            stack.push(j);
                            break;
                        }
                    }
    
                }
            }
        }
    
        void BFS_Map(){
            flag = new boolean[number];
            Queue<Integer> queue = new LinkedList<Integer>();
            for(int i=0;i<number;i++){
                if(flag[i]==false){
                    flag[i]=true;
                    System.out.print(vertexs[i]+" ");
                    queue.add(i);
                    while(!queue.isEmpty()){
                        int k=queue.poll();
                        for(int j=0;j<number;j++){
                            if(edges[k][j]==1&&flag[j]==false){
                                flag[j] = true;
                                System.out.print(vertexs[j]+" ");
                                queue.add(j);
                            }
                        }
                    }
                }
            }
        }
    
        public static void main(String[] args) {  
            Graph graph = new Graph();  
            System.out.println("DFS递归:");  
            graph.DFSTraverse();
            System.out.println();
            System.out.println("DFS非递归:");  
            graph.DFS_Map();
            System.out.println();  
            System.out.println("BFS非递归:");  
            graph.BFS_Map();
        }  
    } 
    1
    99
    程序运行结果： 
    
    --------------------- 
    作者：边城Online 
    来源：CSDN 
    原文：https://blog.csdn.net/qq_24486393/article/details/50270481?utm_source=copy 
    版权声明：本文为博主原创文章，转载请附上博文链接！