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

BFS(广度优先搜索算法)和DFS(深度优先搜索算法)

程序员文章站 2022-07-13 08:42:42
...

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

          ②存储图的两种方式:邻接表和邻接矩阵(本质就是二维数组)

一、BFS

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

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

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

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

二、DFS

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

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

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

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

 

三、代码示例

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

BFS(广度优先搜索算法)和DFS(深度优先搜索算法)

②代码:

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

③结果截图:

BFS(广度优先搜索算法)和DFS(深度优先搜索算法)

相关标签: 算法 算法实现

上一篇: Set集合

下一篇: Set集合