快捷導(dǎo)航

java圖搜索算法之DFS與BFS詳解

更新時間：2021年11月09日 08:56:40 作者：愛敲代碼的小黃

這篇文章主要為大家介紹了java數(shù)據(jù)結(jié)構(gòu)中可以秒殺一切圖算法的DFS與BFS作用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助

你好，我是小黃，一名獨(dú)角獸企業(yè)的Java開發(fā)工程師。
感謝茫茫人海中我們能夠相遇，
俗話說：當(dāng)你的才華和能力，不足以支撐你的夢想的時候，請靜下心來學(xué)習(xí)，
希望優(yōu)秀的你可以和我一起學(xué)習(xí)，一起努力，實(shí)現(xiàn)屬于自己的夢想。

一、前言

上一篇文章我們提到了關(guān)于圖的形象化描述方法，不知道大家還有沒有印象。沒有印象的話，可以去看一下上期的內(nèi)容

對于圖來說，搜索的方法無外乎兩種，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）

兩種搜索算法也不太相同，今天我們就來看一下這兩個搜索算法

二、深度優(yōu)先搜索

我們一提到深度優(yōu)先搜索，腦子里第一時間想到的就是遞歸

沒錯，深搜就是依靠遞歸的方法來進(jìn)行的搜索，我們來看一個例題：

在這里插入圖片描述

對于上圖來說，使用深度優(yōu)先搜索的路線為：0 -> 3 - > 2 -> 4 -> 5 -> 1

這里不懂深搜的小伙伴可以看下這篇：深度優(yōu)先搜索

遞歸版本：

	/**
     * 深度優(yōu)先搜索
     * 
     * @param node
     * @param set
     */
	public void DFS(Node node, Set<Node> set) {
        if (node == null) {
            return;
        }
        if (!set.contains(node)) {
            set.add(node);
            System.out.print(node.value + " ");
            for (Node node1 : node.nexts) {
                DFS(node1, set);
            }
        }
    }

迭代版本：

	/**
     * 深度優(yōu)先搜索
     *
     * @param node
     */
	public void DFS(Node node) {
        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        stack.add(node);
        set.add(node);
        System.out.print(node.value + " ");
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            for (Node next : cur.nexts) {
                if (!set.contains(next)) {
                    stack.add(cur); // 用來做記憶化的
                    stack.add(next);
                    System.out.print(next.value + " ");
                    set.add(next);
                    break;
                }
            }
        }
    }

測試結(jié)果：

迭代版本：
0 3 2 4 5 1
遞歸版本：
0 3 2 4 5 1

三、廣度優(yōu)先搜索

對于廣度優(yōu)先搜索的話，簡單的來說，像走地圖一樣，一圈一圈的擴(kuò)展開來

我們來看一個例題：

在這里插入圖片描述

對于上圖來說，使用深度優(yōu)先搜索的路線為：0 -> 3 -> 1 -> 2 -> 4 -> 5

這里不懂廣搜的小伙伴可以看下這篇：廣度優(yōu)先搜索

	/**
     * 廣度優(yōu)先搜索
     *
     * @param node
     */
    public static void BFS(Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        // 代表是否被使用
        Set<Node> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.value + " ");
            for (Node next : cur.nexts) {
                if (!set.contains(next)) {
                    queue.add(next);
                    set.add(next);
                }
            }
        }
    }