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

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

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

一、BFS

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

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

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

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

二、DFS

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

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

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

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

 

三、代码示例

①目标图（注意此图来自https://blog.csdn.net/qq_36525906/article/details/77387717）

②代码：

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("");
    }
}

③结果截图：