第Java數(shù)據(jù)結(jié)構(gòu)之圖的兩種搜索算法詳解目錄前言深度優(yōu)先搜索算法API設(shè)計代碼實現(xiàn)廣度優(yōu)先搜素算法API設(shè)計代碼實現(xiàn)案例應(yīng)用

前言

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

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

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

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

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

如上圖所示：

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

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

如果沒有搜索，標記為false；

API設(shè)計

類名DepthFirstSearch成員變量1.privateboolean[]marked:索引代表頂點，值表示當前頂點是否已經(jīng)被搜索2.privateintcount：記錄有多少個頂點與s頂點相通構(gòu)造方法DepthFirstSearch(GraphG,ints)：構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中s頂點的所有相通頂點成員方法1.privatevoiddfs(GraphG,intv)：使用深度優(yōu)先搜索找出G圖中v頂點的所有相通頂點2.publicbooleanmarked(intw):判斷w頂點與s頂點是否相通3.publicintcount():獲取與頂點s相通的所有頂點的總數(shù)

代碼實現(xiàn)

/**

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

*@authoralvin

*@date2025/10/31

*@since1.0

publicclassDepthFirstSearch{

//索引代表頂點，值表示當前頂點是否已經(jīng)被搜索

privateboolean[]marked;

//記錄有多少個頂點與s頂點相通

privateintcount;

//構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中s頂點的所有相鄰頂點

publicDepthFirstSearch(GraphG,ints){

//創(chuàng)建一個和圖的頂點數(shù)一樣大小的布爾數(shù)組

marked=newboolean[G.V()];

dfs(G,s);

//使用深度優(yōu)先搜索找出G圖中v頂點的所有相鄰頂點

privatevoiddfs(GraphG,intv){

//把當前頂點標記為已搜索

marked[v]=true;

//遍歷v頂點的鄰接表，得到每一個頂點w

for(Integerw:G.adj(v)){

//遍歷v頂點的鄰接表，得到每一個頂點w

if(!marked[w]){

//如果當前頂點w沒有被搜索過，則遞歸搜索與w頂點相通的其他頂點

dfs(G,w);

//相通的頂點數(shù)量+1

count++;

//判斷w頂點與s頂點是否相通

publicbooleanmarked(intw){

returnmarked[w];

//獲取與頂點s相通的所有頂點的總數(shù)

publicintcount(){

returncount;

}

測試：

publicclassDepthFirstSearchTest{

@Test

publicvoidtest(){

//準備Graph對象

GraphG=newGraph(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);

//準備深度優(yōu)先搜索對象

DepthFirstSearchsearch=newDepthFirstSearch(G,0);

//測試與某個頂點相通的頂點數(shù)量

intcount=search.count();

System.out.println("與起點0相通的頂點的數(shù)量為:"+count);

//測試某個頂點與起點是否相同

booleanmarked1=search.marked(5);

System.out.println("頂點5和頂點0是否相通："+marked1);

booleanmarked2=search.marked(7);

System.out.println("頂點7和頂點0是否相通："+marked2);

}

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

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

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

API設(shè)計

類名BreadthFirstSearch成員變量1.privateboolean[]marked:索引代表頂點，值表示當前頂點是否已經(jīng)被搜索2.privateintcount：記錄有多少個頂點與s頂點相通3.privateQueuewaitSearch:用來存儲待搜索鄰接表的點構(gòu)造方法BreadthFirstSearch(GraphG,ints)：構(gòu)造廣度優(yōu)先搜索對象，使用廣度優(yōu)先搜索找出G圖中s頂點的所有相鄰頂點成員方法1.privatevoidbfs(GraphG,intv)：使用廣度優(yōu)先搜索找出G圖中v頂點的所有相鄰頂點2.publicbooleanmarked(intw):判斷w頂點與s頂點是否相通3.publicintcount():獲取與頂點s相通的所有頂點的總數(shù)

/**

*圖的廣度優(yōu)先搜索算法

*@authoralvin

*@date2025/10/31

*@since1.0

publicclassBreadthFirstSearch{

//索引代表頂點，值表示當前頂點是否已經(jīng)被搜索

privateboolean[]marked;

//記錄有多少個頂點與s頂點相通

privateintcount;

//用來存儲待搜索鄰接表的點

privateQueueIntegerwaitSearch;

//構(gòu)造廣度優(yōu)先搜索對象，使用廣度優(yōu)先搜索找出G圖中s頂點的所有相鄰頂點

publicBreadthFirstSearch(GraphG,ints){

this.marked=newboolean[G.V()];

this.count=0;

this.waitSearch=newArrayDeque();

bfs(G,s);

//使用廣度優(yōu)先搜索找出G圖中v頂點的所有相鄰頂點

privatevoidbfs(GraphG,intv){

//把當前頂點v標識為已搜索

marked[v]=true;

//讓頂點v進入隊列，待搜索

waitSearch.add(v);

//通過循環(huán)，如果隊列不為空，則從隊列中彈出一個待搜索的頂點進行搜索

while(!waitSearch.isEmpty()){

//彈出一個待搜索的頂點

Integerwait=waitSearch.poll();

//遍歷wait頂點的鄰接表

for(Integerw:G.adj(wait)){

if(!marked[w]){

bfs(G,w);

//讓相通的頂點+1；

count++;

//判斷w頂點與s頂點是否相通

publicbooleanmarked(intw){

returnmarked[w];

//獲取與頂點s相通的所有頂點的總數(shù)

publicintcount(){

returncount;

}

測試代碼：

publicclassBreadthFirstSearchTest{

@Test

publicvoidtest(){

//準備Graph對象

GraphG=newGraph(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);

//準備廣度優(yōu)先搜索對象

BreadthFirstSearchsearch=newBreadthFirstSearch(G,0);

//測試與某個頂點相通的頂點數(shù)量

intcount=search.count();

System.out.println("與起點0相通的頂點的數(shù)量為:"+count);

//測試某個頂點與起點是否相同

booleanmarked1=search.marked(5);

System.out.println("頂點5和頂點0是否相通："+marked1);

booleanmarked2=search.marked(7);

System.out.println("頂點7和頂點0是否相通："+marked2);

}

案例應(yīng)用

某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。暢通工程的目標是使全省任何兩個城鎮(zhèn)間都可以實現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。目前的道路狀況，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對象和頂點9，構(gòu)建DepthFirstSearch對象或BreadthFirstSearch對象；調(diào)用搜索對象的marked(10)方法和marked(8)方法，即可得到9和城市與10號城市以及9號城市與8號城市是否相通。

代碼實現(xiàn)：

publicclassTrafficProjectGraph{

publicstaticvoidmain(String[]args)throwsException{

//城市數(shù)量

inttotalNumber=20;

GraphG=newGraph(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)先搜索對象，起