◆王遠(yuǎn)敏

深度優(yōu)先搜索算法的應(yīng)用研究

◆王遠(yuǎn)敏

（興義民族師范學(xué)院信息技術(shù)學(xué)院 貴州 562400）

在算法的應(yīng)用中，深度優(yōu)先搜索算法在圖結(jié)構(gòu)的數(shù)據(jù)類型中有著廣泛的應(yīng)用，本文設(shè)置了兩個(gè)應(yīng)用場景，一個(gè)是信件能否送達(dá)問題，一個(gè)是不重復(fù)打卡夜跑路線的規(guī)劃問題，這兩個(gè)問題都與現(xiàn)實(shí)生活息息相關(guān)。本文通過對這兩個(gè)問題的詳細(xì)分析和解決來說明深度優(yōu)先搜索算法的各種不同使用場合和方法，同時(shí)也分析了在解決問題過程中存在的不足。

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

1 引言

深度優(yōu)先搜索是遍歷圖的其中一種順序，在圖結(jié)構(gòu)的數(shù)據(jù)類型中有著廣泛的應(yīng)用，從最基本的結(jié)點(diǎn)遍歷問題，到判斷圖的連通性問題，再到最短路徑及旅游路線規(guī)劃問題，都可以使用深度優(yōu)先搜索算法進(jìn)行求解。因此深度優(yōu)先搜索算法在各種問題的算法設(shè)計(jì)中有著廣泛的使用，發(fā)揮著極其重要的作用。以下從兩種常用情景討論深度優(yōu)先搜索算法的設(shè)計(jì)使用過程，并進(jìn)行應(yīng)用的比較分析[1]。

2 使用情景

該文選擇了兩種與實(shí)際工作和生活聯(lián)系起來的問題：一是信件能否送達(dá)問題，二是不重復(fù)打卡的夜跑路線規(guī)劃問題。通過問題的分析及實(shí)現(xiàn)來研究深度優(yōu)先搜索的使用方法和過程。

2.1 信件能否送達(dá)問題

假設(shè)現(xiàn)有由x個(gè)信息收集員組成的信件相互交換信息網(wǎng)，在這x個(gè)信息收集員中可直接傳遞信件的路線有y條，路線沒有方向之分，需要判斷每當(dāng)一個(gè)信息收集員退出信息網(wǎng)后，信件還能否送達(dá)到其他信息收集員處。

首先對該問題進(jìn)行數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，將x個(gè)收集員看成是結(jié)點(diǎn)，y條可直接傳遞信件的路線看成是邊，則可得到對應(yīng)的數(shù)據(jù)結(jié)構(gòu)為一個(gè)無向圖。每當(dāng)一個(gè)信息收集員退出信息網(wǎng)，則在該圖中減少一個(gè)對應(yīng)的結(jié)點(diǎn)及與其相連的路線（即對應(yīng)的邊），然后通過判斷剩余信息收集員及路線是否連通來確定信件能否送達(dá)，在此采用深度優(yōu)先搜索遍歷進(jìn)行連通性判斷。

解決該問題的第一步采用鄰接矩陣對映射后的數(shù)據(jù)信息進(jìn)行存儲(chǔ)，這也為后續(xù)采用深度優(yōu)先遍歷做好準(zhǔn)備。設(shè)置存儲(chǔ)類型如下：

typedef struct IGnode *DToG；

struct IGnode{ int x，y； int G[100][100]；}；

接下來設(shè)置深度優(yōu)先搜索算法為單獨(dú)函數(shù)，方便后續(xù)進(jìn)行調(diào)用。算法如下：

void IGS（PToG mailweb，int V，void（* search）（int））

{ int w；

search（v）；

searched[v]=1；

for（w=0；wx；w++）

if（!searched[w]&&（mailweb->G[v][w]

IGS（mailweb，w，search）；

}

最后在每一次信息收集員有變化時(shí)對信件送達(dá)網(wǎng)絡(luò)進(jìn)行搜索、連通性判斷，并給出提示，當(dāng)信息收集員減少到無法連通時(shí)信件將無法進(jìn)行相互送達(dá)，輸出結(jié)論，問題得以解決。設(shè)置數(shù)據(jù)案例，假設(shè)初始信息收集員有10人，即x=10；相互之間可以直接傳遞信件的路線有9條，即y=9。10個(gè)信息收集員用編號(hào)0到9代表，相互之間傳遞信件的路線使用數(shù)據(jù)對來表示，即{（0，1），（0，2），（1，3），（0，4），（2，5），（3，6），（2，7），（4，8），（3，9）}。設(shè)計(jì)一個(gè)函數(shù)LCS通過調(diào)用深度優(yōu)先搜索算法來判斷當(dāng)前信件送達(dá)網(wǎng)絡(luò)的連通分量數(shù)，在主函數(shù)中進(jìn)行判斷，若當(dāng)前連通分量數(shù)大于1則得出結(jié)論信件不能實(shí)現(xiàn)整個(gè)信息網(wǎng)的送達(dá)[2]。LCS算法的主要實(shí)現(xiàn)如下：

int LCS（）

{ int v；int count=0；

for（v=0；v

{ if（vis[v]==false&&lost[v]==false）

{ count++；

IGS（v）；

}

}

return count；

}

在該算法中通過調(diào)用深度優(yōu)先算法來判斷現(xiàn)有信件送達(dá)網(wǎng)絡(luò)的連通性問題，若一個(gè)連通分量結(jié)束則循環(huán)調(diào)用探索另一個(gè)連通分量，以此統(tǒng)計(jì)出信件送達(dá)網(wǎng)絡(luò)存在的連通分量。若連通分量的計(jì)數(shù)器的值為1，則說明整個(gè)網(wǎng)絡(luò)的信件送達(dá)沒有問題；當(dāng)信息收集員減少到使得整個(gè)信件送達(dá)網(wǎng)絡(luò)的連通分量數(shù)大于1時(shí)，則說明整個(gè)網(wǎng)絡(luò)的信件無法相互送達(dá)。接下來是主函數(shù)的設(shè)計(jì)，在主函數(shù)中輸入信件送達(dá)網(wǎng)絡(luò)的原始數(shù)據(jù)，通過調(diào)用LCS來統(tǒng)計(jì)原始網(wǎng)絡(luò)的連通分量數(shù)量，若一開始就不具備信件送達(dá)條件的話，則輸出否定信息之后終止執(zhí)行，不再判斷當(dāng)信息收集員變少的情況；否則在每個(gè)信息收集員減少一個(gè)就循環(huán)調(diào)用LCS函數(shù)進(jìn)行連通分量的計(jì)數(shù)和判斷，若信息收集員減少后連通分量數(shù)還是等于1，則得出結(jié)論信息網(wǎng)正常，若減少一個(gè)信息收集員后連通分量數(shù)大于1，則得出結(jié)論信息網(wǎng)不能再繼續(xù)相互送達(dá)。主要語句及運(yùn)行結(jié)果如下所示：

從第一個(gè)問題可以得出，深度優(yōu)先搜索對于圖結(jié)構(gòu)的連通性相關(guān)問題可以提供一種解題的思路，而很多與路線相關(guān)的問題都可以轉(zhuǎn)換為圖結(jié)構(gòu)進(jìn)行存儲(chǔ)。該題目中需要判斷的是在信息收集員不斷變化的情況下判斷信件是否能送達(dá)，經(jīng)過轉(zhuǎn)換之后設(shè)計(jì)的解決方法是每個(gè)信息收集員減少后就采用深度優(yōu)先搜索判斷剩余的信息收集員組成的圖結(jié)構(gòu)是否是連通的，將信件能否送達(dá)先轉(zhuǎn)換成站點(diǎn)的連通性判斷，再使用深度優(yōu)先搜索算法進(jìn)行連通性判斷，從而解決問題。

當(dāng)然在該問題中，可以對信件送達(dá)網(wǎng)絡(luò)的送達(dá)進(jìn)行擴(kuò)展，當(dāng)信息收集員減少導(dǎo)致整個(gè)網(wǎng)絡(luò)不連通時(shí)，可以通過增加設(shè)置站點(diǎn)管理員，也就是每個(gè)連通分量設(shè)置一個(gè)負(fù)責(zé)人，負(fù)責(zé)人之間可以相互進(jìn)行信件的送達(dá)，這樣就可以避免連通的限制。

2.2 不重復(fù)打卡的夜跑路線規(guī)劃問題

很多人在忙碌的工作和學(xué)習(xí)中都有夜跑的習(xí)慣，以此作為保持身體健康的重要鍛煉手段。夜跑中我們希望不走重復(fù)的景點(diǎn)以提高自身夜跑的積極性，因此在夜跑路線中想規(guī)劃一條從起點(diǎn)出發(fā)經(jīng)過不重復(fù)景點(diǎn)最后再回到起點(diǎn)的路線。假設(shè)夜跑場地如圖1所示，A為起點(diǎn)，B、C、D、E、F、G為可以經(jīng)過的景點(diǎn)，景點(diǎn)間有直達(dá)路線的話則在兩景點(diǎn)間畫一條線表示。

圖2 夜跑場地示意圖

首先對該問題進(jìn)行分析并設(shè)計(jì)其對應(yīng)數(shù)據(jù)結(jié)構(gòu)。將每個(gè)景點(diǎn)看成頂點(diǎn)，可直達(dá)的兩景點(diǎn)間的路線看成邊，則對應(yīng)于一個(gè)圖結(jié)構(gòu)數(shù)據(jù)類型。但與前一種情景不同的是在這個(gè)問題中每個(gè)景點(diǎn)只能經(jīng)過一次，如果對應(yīng)成圖結(jié)構(gòu)需要進(jìn)行拆點(diǎn)，例如景點(diǎn)B對應(yīng)的結(jié)點(diǎn)x要拆成x和x’兩個(gè)結(jié)點(diǎn)，再將x和x’之間連接一條邊，由于每個(gè)中間景點(diǎn)不能重復(fù)經(jīng)過，所以可以設(shè)置邊的容量是1，單位流量費(fèi)用則為0。當(dāng)景點(diǎn)B到景點(diǎn)C有直達(dá)道路時(shí)，設(shè)置結(jié)點(diǎn)x’到結(jié)點(diǎn)y存在一條邊（其中y為結(jié)點(diǎn)C拆成結(jié)點(diǎn)之一），該條邊的容量同樣是1，單位流量費(fèi)用設(shè)置成-1，便于統(tǒng)計(jì)經(jīng)過盡可能多的景點(diǎn)數(shù)。這樣該問題就轉(zhuǎn)化成了最小費(fèi)用最大流問題[3]。

解決該問題的思路是先設(shè)置數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，根據(jù)預(yù)設(shè)的數(shù)據(jù)，景點(diǎn)總數(shù)n等于7，景點(diǎn)之間直達(dá)路線的條數(shù)m等于7，采用二維數(shù)組存儲(chǔ)頂點(diǎn)及其路線信息，采用結(jié)構(gòu)體數(shù)組存儲(chǔ)路線信息，其中包括路線連接的兩個(gè)景點(diǎn)信息、路線邊的容量和單位流量費(fèi)用。這樣的話便于統(tǒng)計(jì)最多可以經(jīng)過的不重復(fù)景點(diǎn)的個(gè)數(shù)。數(shù)據(jù)類型設(shè)置如下：

將夜跑路線所構(gòu)成的圖結(jié)構(gòu)基本信息輸入進(jìn)行初始化以后，從夜跑起始點(diǎn)A出發(fā)，沿著路線容量為1的景點(diǎn)進(jìn)行深度優(yōu)先搜索，最終返回到夜跑起點(diǎn)，在進(jìn)行設(shè)置的時(shí)候只有夜跑起點(diǎn)的路線容量為2，這樣就可以實(shí)現(xiàn)不經(jīng)過重復(fù)的景點(diǎn)進(jìn)行夜跑路線的設(shè)置。其次需要解決的是如何經(jīng)過最多景點(diǎn)的問題，在進(jìn)行深度優(yōu)先搜索的同時(shí)帶入單位流量費(fèi)用的判斷，也就是借助最大流算法來進(jìn)行規(guī)劃。在此過程中，深度優(yōu)先搜索是主要的路線規(guī)劃算法。

void DFS_Flow（PToG run，int V，void（* search）（int））

{ int w；

search（v）；

searched[v]=1；

for（w=0；wx；w++）

if（!searched[w]&&（run->G[v][w]

DFS_Flow（run，w，search）；

}

最后得出根據(jù)初始設(shè)置的地圖得到的夜跑路線規(guī)劃為以下輸出結(jié)果（圖3）：

從該案例可以看出，深度優(yōu)先搜索在夜跑路線規(guī)劃問題中的應(yīng)用是一種擴(kuò)展式的應(yīng)用，除了搜索連通分量以外還結(jié)合了最大流算法來進(jìn)行使用。

3 比較分析

對這兩個(gè)不同的使用情景進(jìn)行比較分析，第一個(gè)場景使用了深度優(yōu)先搜索算法來進(jìn)行圖的連通分量的統(tǒng)計(jì)，使用方法更加的直接，通過循環(huán)調(diào)用該算法來進(jìn)行，在深度優(yōu)先算法中沒有其他的擴(kuò)展。在第二個(gè)場景中，問題相對復(fù)雜，除了進(jìn)行圖的連通性判斷以外，還要計(jì)算經(jīng)過的景點(diǎn)的數(shù)目，且不允許經(jīng)過重復(fù)的景點(diǎn)，因此在使用深度優(yōu)先搜索算法時(shí)增加了最大流算法，可以說是一種融會(huì)貫通的算法設(shè)計(jì)思路。

4 小結(jié)

在以上兩個(gè)案例中，題目的初始數(shù)據(jù)都是圖形結(jié)構(gòu)的，且在題目的要求中都涉及圖的路線的問題，以此可以從遍歷來考慮，而深度優(yōu)先搜索遍歷則是一種可以結(jié)合隊(duì)列和堆棧來進(jìn)行的遍歷方法，因此可以用來解決很多的問題，在實(shí)際應(yīng)用中也有很多其他擴(kuò)展的用法。當(dāng)然在以上案例中的初始數(shù)據(jù)設(shè)置都較為簡單，并且在解題的過程中忽略了很多其他的影響因素，因此還有很多需要改進(jìn)的地方，將在以后的研究中進(jìn)行改進(jìn)和擴(kuò)充。

[1]陳越.數(shù)據(jù)結(jié)構(gòu)（第2版）[M].北京：高等教育出版社，2016.

[2]陳越.數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)與實(shí)驗(yàn)指導(dǎo)（第2版）[M].北京：高等教育出版社，2019.

[3]陳小玉.趣學(xué)算法[M].北京：人民郵電出版社，2017.