欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)之圖的兩種搜索算法詳解

 更新時間：2022年11月01日 09:07:40   作者：JAVA旭陽  
在很多情況下，我們需要遍歷圖，得到圖的一些性質(zhì)。有關(guān)圖的搜索，最經(jīng)典的算法有深度優(yōu)先搜索和廣度優(yōu)先搜索，接下來我們分別講解這兩種搜索算法，需要的可以參考一下

前言

在很多情況下，我們需要遍歷圖，得到圖的一些性質(zhì)，例如，找出圖中與指定的頂點(diǎn)相連的所有頂點(diǎn)，或者判定某個頂點(diǎn)與指定頂點(diǎn)是否相通，是非常常見的需求。

有關(guān)圖的搜索，最經(jīng)典的算法有深度優(yōu)先搜索和廣度優(yōu)先搜索，接下來我們分別講解這兩種搜索算法。

學(xué)習(xí)本文前請先閱讀這篇文章 【數(shù)據(jù)結(jié)構(gòu)與算法】圖的基礎(chǔ)概念和數(shù)據(jù)模型。

深度優(yōu)先搜索算法

所謂的深度優(yōu)先搜索，指的是在搜索時，如果遇到一個結(jié)點(diǎn)既有子結(jié)點(diǎn)，又有兄弟結(jié)點(diǎn)，那么先找子結(jié)點(diǎn)，然后找兄弟結(jié)點(diǎn)。

如上圖所示：

由于邊是沒有方向的，所以，如果4和5頂點(diǎn)相連，那么4會出現(xiàn)在5的相鄰鏈表中，5也會出現(xiàn)在4的相鄰鏈表中。

為了不對頂點(diǎn)進(jìn)行重復(fù)搜索，應(yīng)該要有相應(yīng)的標(biāo)記來表示當(dāng)前頂點(diǎn)有沒有搜索過，可以使用一個布爾類型的數(shù)組boolean[V] marked,索引代表頂點(diǎn)，值代表當(dāng)前頂點(diǎn)是否已經(jīng)搜索，如果已經(jīng)搜索，標(biāo)記為true，

如果沒有搜索，標(biāo)記為false；

API設(shè)計

類名DepthFirstSearch
成員變量1.private boolean[] marked: 索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索2.private int count：記錄有多少個頂點(diǎn)與s頂點(diǎn)相通
構(gòu)造方法DepthFirstSearch(Graph G,int s)：構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相通頂點(diǎn)
成員方法1.private void dfs(Graph G, int v)：使用深度優(yōu)先搜索找出G圖中v頂點(diǎn)的所有相通頂點(diǎn)2.public boolean marked(int w):判斷w頂點(diǎn)與s頂點(diǎn)是否相通3.public int count():獲取與頂點(diǎn)s相通的所有頂點(diǎn)的總數(shù)

代碼實(shí)現(xiàn)

/**
 * 圖的深度優(yōu)先搜索算法
 *
 * @author alvin
 * @date 2022/10/31
 * @since 1.0
 **/
public class DepthFirstSearch {
    //索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索
    private boolean[] marked;
    //記錄有多少個頂點(diǎn)與s頂點(diǎn)相通
    private int count;

    //構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相鄰頂點(diǎn)
    public DepthFirstSearch(Graph G, int s) {
        //創(chuàng)建一個和圖的頂點(diǎn)數(shù)一樣大小的布爾數(shù)組
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    //使用深度優(yōu)先搜索找出G圖中v頂點(diǎn)的所有相鄰頂點(diǎn)
    private void dfs(Graph G, int v) {
        //把當(dāng)前頂點(diǎn)標(biāo)記為已搜索
        marked[v] = true;
        //遍歷v頂點(diǎn)的鄰接表，得到每一個頂點(diǎn)w
        for (Integer w : G.adj(v)) {
            //遍歷v頂點(diǎn)的鄰接表，得到每一個頂點(diǎn)w
            if (!marked[w]) {
                //如果當(dāng)前頂點(diǎn)w沒有被搜索過，則遞歸搜索與w頂點(diǎn)相通的其他頂點(diǎn)
                dfs(G, w);
            }
        }

        //相通的頂點(diǎn)數(shù)量+1
        count++;
    }

    //判斷w頂點(diǎn)與s頂點(diǎn)是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //獲取與頂點(diǎn)s相通的所有頂點(diǎn)的總數(shù)
    public int count() {
        return count;
    }
}

測試：

public class DepthFirstSearchTest {

    @Test
    public void test() {
        //準(zhǔn)備Graph對象
        Graph G = new Graph(13);
        G.addEdge(0,5);
        G.addEdge(0,1);
        G.addEdge(0,2);
        G.addEdge(0,6);
        G.addEdge(5,3);
        G.addEdge(5,4);
        G.addEdge(3,4);
        G.addEdge(4,6);
        G.addEdge(7,8);
        G.addEdge(9,11);
        G.addEdge(9,10);
        G.addEdge(9,12);
        G.addEdge(11,12);

        //準(zhǔn)備深度優(yōu)先搜索對象
        DepthFirstSearch search = new DepthFirstSearch(G, 0);
        //測試與某個頂點(diǎn)相通的頂點(diǎn)數(shù)量
        int count = search.count();
        System.out.println("與起點(diǎn)0相通的頂點(diǎn)的數(shù)量為:"+count);
        //測試某個頂點(diǎn)與起點(diǎn)是否相同
        boolean marked1 = search.marked(5);
        System.out.println("頂點(diǎn)5和頂點(diǎn)0是否相通："+marked1);
        boolean marked2 = search.marked(7);
        System.out.println("頂點(diǎn)7和頂點(diǎn)0是否相通："+marked2);
    }
}

廣度優(yōu)先搜素算法

所謂的廣度優(yōu)先搜索，指的是在搜索時，如果遇到一個結(jié)點(diǎn)既有子結(jié)點(diǎn)，又有兄弟結(jié)點(diǎn)，那么先找兄弟結(jié)點(diǎn)，然后找子結(jié)點(diǎn)。

  • 可以通過借助一個輔助隊(duì)列實(shí)現(xiàn)，先將1加入到隊(duì)列中
  • 然后取出1，將1的相鄰頂點(diǎn)加入到隊(duì)列中
  • 依次遞歸，如下圖所示：

API設(shè)計

類名BreadthFirstSearch
成員變量1.private boolean[] marked: 索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索2.private int count：記錄有多少個頂點(diǎn)與s頂點(diǎn)相通3.private Queue waitSearch: 用來存儲待搜索鄰接表的點(diǎn)
構(gòu)造方法BreadthFirstSearch(Graph G,int s)：構(gòu)造廣度優(yōu)先搜索對象，使用廣度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相鄰頂點(diǎn)
成員方法1.private void bfs(Graph G, int v)：使用廣度優(yōu)先搜索找出G圖中v頂點(diǎn)的所有相鄰頂點(diǎn)2.public boolean marked(int w):判斷w頂點(diǎn)與s頂點(diǎn)是否相通3.public int count():獲取與頂點(diǎn)s相通的所有頂點(diǎn)的總數(shù)

代碼實(shí)現(xiàn)

/**
 * 圖的廣度優(yōu)先搜索算法
 *
 * @author alvin
 * @date 2022/10/31
 * @since 1.0
 **/
public class BreadthFirstSearch {
    //索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索
    private boolean[] marked;
    //記錄有多少個頂點(diǎn)與s頂點(diǎn)相通
    private int count;
    //用來存儲待搜索鄰接表的點(diǎn)
    private Queue<Integer> waitSearch;

    //構(gòu)造廣度優(yōu)先搜索對象，使用廣度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相鄰頂點(diǎn)
    public BreadthFirstSearch(Graph G, int s) {
        this.marked = new boolean[G.V()];
        this.count = 0;
        this.waitSearch = new ArrayDeque<>();

        bfs(G, s);
    }

    //使用廣度優(yōu)先搜索找出G圖中v頂點(diǎn)的所有相鄰頂點(diǎn)
    private void bfs(Graph G, int v) {
        //把當(dāng)前頂點(diǎn)v標(biāo)識為已搜索
        marked[v] = true;
        //讓頂點(diǎn)v進(jìn)入隊(duì)列，待搜索
        waitSearch.add(v);
        //通過循環(huán)，如果隊(duì)列不為空，則從隊(duì)列中彈出一個待搜索的頂點(diǎn)進(jìn)行搜索
        while (!waitSearch.isEmpty()) {
            //彈出一個待搜索的頂點(diǎn)
            Integer wait = waitSearch.poll();
            //遍歷wait頂點(diǎn)的鄰接表
            for (Integer w : G.adj(wait)) {
                if (!marked[w]) {
                    bfs(G, w);
                }
            }
        }
        //讓相通的頂點(diǎn)+1；
        count++;

    }

    //判斷w頂點(diǎn)與s頂點(diǎn)是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //獲取與頂點(diǎn)s相通的所有頂點(diǎn)的總數(shù)
    public int count() {
        return count;
    }
}

測試代碼：

public class BreadthFirstSearchTest {

    @Test
    public void test() {
        //準(zhǔn)備Graph對象
        Graph G = new Graph(13);
        G.addEdge(0, 5);
        G.addEdge(0, 1);
        G.addEdge(0, 2);
        G.addEdge(0, 6);
        G.addEdge(5, 3);
        G.addEdge(5, 4);
        G.addEdge(3, 4);
        G.addEdge(4, 6);
        G.addEdge(7, 8);
        G.addEdge(9, 11);
        G.addEdge(9, 10);
        G.addEdge(9, 12);
        G.addEdge(11, 12);

        //準(zhǔn)備廣度優(yōu)先搜索對象
        BreadthFirstSearch search = new BreadthFirstSearch(G, 0);
        //測試與某個頂點(diǎn)相通的頂點(diǎn)數(shù)量
        int count = search.count();
        System.out.println("與起點(diǎn)0相通的頂點(diǎn)的數(shù)量為:" + count);
        //測試某個頂點(diǎn)與起點(diǎn)是否相同
        boolean marked1 = search.marked(5);
        System.out.println("頂點(diǎn)5和頂點(diǎn)0是否相通：" + marked1);
        boolean marked2 = search.marked(7);
        System.out.println("頂點(diǎn)7和頂點(diǎn)0是否相通：" + marked2);
    }
}

案例應(yīng)用

某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。“暢通工程”的目標(biāo)是使全省任何兩個城鎮(zhèn)間都可以實(shí)現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達(dá)即可）。目前的道路狀況，9號城市和10號城市是否相通？9號城市和8號城市是否相通？

測試數(shù)據(jù)格式如上圖所示，總共有20個城市，目前已經(jīng)修改好了7條道路，問9號城市和10號城市是否相通？9號城市和8號城市是否相通？

解題思路：

  • 創(chuàng)建一個圖Graph對象，表示城市；
  • 分別調(diào)用addEdge(0,1),addEdge(6,9),addEdge(3,8),addEdge(5,11),addEdge(2,12),addEdge(6,10),addEdge(4,8)，表示已經(jīng)修建好的道路把對應(yīng)的城市連接起來；
  • 通過Graph對象和頂點(diǎn)9，構(gòu)建DepthFirstSearch對象或BreadthFirstSearch對象；
  • 調(diào)用搜索對象的marked(10)方法和marked(8)方法，即可得到9和城市與10號城市以及9號城市與8號城市是否相通。

代碼實(shí)現(xiàn)：

public class TrafficProjectGraph {

    public static void main(String[] args) throws Exception{
        //城市數(shù)量
        int totalNumber =  20;
        Graph G = new Graph(totalNumber);
        //添加城市的交通路線
        G.addEdge(0,1);
        G.addEdge(6,9);
        G.addEdge(3,8);
        G.addEdge(5,11);
        G.addEdge(2,12);
        G.addEdge(6,10);
        G.addEdge(4,8);

        //構(gòu)建一個深度優(yōu)先搜索對象，起點(diǎn)設(shè)置為頂點(diǎn)9
        DepthFirstSearch search = new DepthFirstSearch(G, 9);

        //調(diào)用marked方法，判斷8頂點(diǎn)和10頂點(diǎn)是否與起點(diǎn)9相通
        System.out.println("頂點(diǎn)8和頂點(diǎn)9是否相通："+search.marked(8));
        System.out.println("頂點(diǎn)10和頂點(diǎn)9是否相通："+search.marked(10));

    }
}

結(jié)果：

以上就是Java數(shù)據(jù)結(jié)構(gòu)之圖的兩種搜索算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java圖搜索算法的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

最新評論