DFS-創(chuàng)新互聯(lián)

圖描述的是一些個體之間的關(guān)系。與線性表之間和二叉樹之間不同的是，這些個體之間即不是前驅(qū)后繼的順序關(guān)系，也不是祖先后代的層次關(guān)系，而是錯綜復(fù)雜的網(wǎng)狀關(guān)系。在圖中一個比較重要的算法就是，小編接下來將要介紹的DFS算法。
下面通過一個具體的例子來介紹DFS算法——用DFS算法求聯(lián)通塊。
問題描述如下：油田（Oil Deposits UVa 572）
輸入一個m行n列的字符矩陣，統(tǒng)計字符的“@”組成多少個八聯(lián)塊。如果兩個字符“@”所在的格子相鄰（橫，豎，對角線方向）就說他們屬于一個連通塊。例如下圖有兩個八連塊。

創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站設(shè)計制作、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的三元網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
        • @
  • @ @ * @
  • @ @
    @ @ @ @
    @ @     * @
    分析如下：
    和二叉樹的遍歷一樣，圖也有DFS和BFS遍歷。由于DFS更容易編寫，一般用DFS找聯(lián)通塊：從每個“@”格子出發(fā)，遞歸遍歷它周圍的“@”格子。每次訪問一個格子是就給它寫上一個“聯(lián)通分量編號”（即下面代碼中的idx數(shù)組），這樣就可以在訪問之前檢查它是否已經(jīng)有了編號，從而避免同一個格子訪問多次。 
    #include<cstdio>
#include<cstring>
const int maxn=100+5;
char pic[maxn][maxn];
int m,n,idx[maxn][maxn];
void dfs(int r,int c,int id)
{
if(r<0||r>=m||c<0||c>=n) return;//“出界”的格子
if(idx[r][c]>0||pic[r][c]!='@') return;//不是@或者已經(jīng)訪問過的格子
idx[r][c]=id;//聯(lián)通分量編號
for(int dr=-1;dr<=1;dr++)
for(int dc=-1;dc<=1;dc++)
if(dr!=0||dc!=0) dfs(r+dr,c+dc,id); 
} 
int main()
{
while(scanf("%d%d",&m,&n)==2&&m&&n)
{
    for(int i=0;i<n;i++) scanf("%s",pic[i]);
    memset(idx,0,sizeof(idx));
    int cnt=0;
    for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
    if(idx[i][j]==0&&pic[i][j]=='@') dfs(i,j,++cnt);
    printf("%d\n",cnt);
}
return 0;   
}

    這道題目的算法有個好聽的名字：種子填充（floodfill）。有興趣的讀者，可以在網(wǎng)絡(luò)上查找相關(guān)資源。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)頁標題：DFS-創(chuàng)新互聯(lián)
標題網(wǎng)址：http://bm7419.com/article48/ddpdhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、微信小程序、網(wǎng)站維護、小程序開發(fā)、用戶體驗、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)公司