BFS（广度优先搜索算法）和DFS（深度优先搜索算法）

港控/mmm° 2022-05-18 08:16 325阅读 0赞

### **注意：①BFS和DFS都是对图的遍历(按照某种次序访问图的每一顶点一次仅且一次)** ###

### **          ②存储图的两种方式：邻接表和邻接矩阵（本质就是二维数组）** ###

### **一、BFS** ###

### **   ①也就是我们说的广度搜索算法** ###

### **   ②实现方式：利用队列和递归来实现** ###

### **   ③思路：通过队列来实现的，找到一个起点A，并将A相邻的点放入队列中，这时将队首元素B取出，并将B相邻且没有访问过的点放入队列中，不断重复这个操作，直至队列清空，这时候，依次访问的顶点就是遍历的顺序。** ###

### **   ④适用场景：寻找最短路径的问题** ###

### **二、DFS** ###

### **   ①也就是我们说的深度搜索算法** ###

### **   ②实现方式：利用栈和递归来实现** ###

### **   ③思路：通过栈来实现的，找到一个起点A，并将A相邻的点放入栈中，将栈顶元素B取出,并将B相邻且没有访问过的点放入栈中，不断重复这个操作，直至栈清空，这时候，依次访问的顶点就是遍历的顺序。** ###

### **   ④适用场景：于快速发现底部节点** ###

## ##

### **三、代码示例** ###

### **①目标图（注意此图来自**[https://blog.csdn.net/qq\_36525906/article/details/77387717][https_blog.csdn.net_qq_36525906_article_details_77387717]**）** ###

![70][]

### **②代码：** ###

package com.atlihao;
    
    //节点类
    class Node {
        int x;
        Node next;
        public Node(int x) {
            this.x = x;
            this.next = null;
        }
    }
    
    
    //DFS算法
    class DFS {
        public Node first;
        public Node last;
    
        public static int run[] = new int[11];
        public static DFS head[] = new DFS[11];
    
        public static void dfs(int current) {
            run[current] = 1;
            System.out.print("[" + current + "]");
    
            while (head[current].first != null) {
                if(run[head[current].first.x] == 0) { //如果顶点尚未遍历，就进行dfs递归
                    dfs(head[current].first.x);
                }
                head[current].first = head[current].first.next;
            }
        }
    
        public boolean isEmpty() {
            return first == null;
        }
        public void print() {
            Node current = first;
            while(current != null) {
                System.out.print("[" + current.x + "]");
                current = current.next;
            }
            System.out.println();
        }
        public void insert(int x) {
            Node newNode = new Node(x);
            if(this.isEmpty()) {
                first = newNode;
                last = newNode;
            }
            else {
                last.next = newNode;
                last = newNode;
            }
        }
    }
    
    
    //BFS算法
    class BFS {
        public Node first;
        public Node last;
    
        public static int run[] = new int[11];
        public static BFS head[] = new BFS[11];
        public final static int MAXSIZE = 12;
        static int[] queue = new int[MAXSIZE];
        static int front = -1;
        static int rear = -1;
    
        public static void enqueue(int value) {
            if(rear>=MAXSIZE) return;
            rear++;
            queue[rear] = value;
        }
    
        public static int dequeue() {
            if(front == rear) return -1;
            front++;
            return queue[front];
        }
    
        public static void bfs(int current) {
            Node tempnode;
            enqueue(current);
            run[current] = 1;
            System.out.print("[" + current + "]");
            while (front != rear) {
                current = dequeue();
                tempnode = head[current].first;
                while (tempnode != null) {
                    if(run[tempnode.x] == 0) {
                        enqueue(tempnode.x);
                        run[tempnode.x] = 1;
                        System.out.print("[" + tempnode.x + "]");
                    }
                    tempnode = tempnode.next;
                }
            }
        }
    
        public boolean isEmpty() {
            return first == null;
        }
        public void insert(int x) {
            Node newNode = new Node(x);
            if(this.isEmpty()) {
                first = newNode;
                last = newNode;
            }
            else {
                last.next = newNode;
                last = newNode;
            }
        }
    }
    
    
    
    public class BFSAndDFSTest {
        public static void main(String[] args) {
            int Data[][] = { {1,2},{1,8},{2,1},{2,3},{3,2},
            		{2,4},{4,2},{4,5},{4,6},{4,7}
            		,{5,4},{5,6},{6,4},{6,5},{6,7},{7,4},{7,6}
            		,{8,1},{8,9},{8,10},{9,8},{9,10},{10,9},{10,8}};
            int DataNum;
            int i,j;
            System.out.println("图形的邻接表内容为：");
            for(i=1;i<11;i++) {
                DFS.run[i] = 0;
                DFS.head[i] = new DFS();
                System.out.print("顶点" + i + "=>");
                for (j=0;j<Data.length;j++) {
                    if(Data[j][0] == i) {
                        DataNum = Data[j][1];
                        DFS.head[i].insert(DataNum);
                    }
                }
                DFS.head[i].print();
            }
            System.out.println("深度优先遍历顶点：");
            DFS.dfs(1);
            System.out.println("");
    
            for(i=1;i<11;i++) {
                BFS.run[i] = 0;
                BFS.head[i] = new BFS();
                for (j=0;j<Data.length;j++) {
                    if(Data[j][0] == i) {
                        DataNum = Data[j][1];
                        BFS.head[i].insert(DataNum);
                    }
                }
            }
            System.out.println("广度优先遍历顶点：");
            BFS.bfs(1);
            System.out.println("");
        }
    }

### **③结果截图：** ###

![70 1][]

[https_blog.csdn.net_qq_36525906_article_details_77387717]: https://blog.csdn.net/qq_36525906/article/details/77387717
[70]: /images/20220518/ce7af3c49d384362a17f5c42df7c9a72.png
[70 1]: /images/20220518/57c0f06c2aaf44c08a67b5283ede3879.png