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

在山亭等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需設(shè)計(jì)網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),營銷型網(wǎng)站,成都外貿(mào)網(wǎng)站制作,山亭網(wǎng)站建設(shè)費(fèi)用合理。

• • • • @
• @ @ * @
• @ @
  @ @ @ @
  @ @ * @
  分析如下：
  和二叉樹的遍歷一樣，圖也有DFS和BFS遍歷。由于DFS更容易編寫，一般用DFS找聯(lián)通塊：從每個(gè)“@”格子出發(fā)，遞歸遍歷它周圍的“@”格子。每次訪問一個(gè)格子是就給它寫上一個(gè)“聯(lián)通分量編號”（即下面代碼中的idx數(shù)組），這樣就可以在訪問之前檢查它是否已經(jīng)有了編號，從而避免同一個(gè)格子訪問多次。

  #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;   
  }

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

名稱欄目：DFS
標(biāo)題路徑：http://vcdvsql.cn/article40/gdggho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、商城網(wǎng)站、網(wǎng)站設(shè)計(jì)、品牌網(wǎng)站制作、搜索引擎優(yōu)化

廣告

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