ACM_程式設計競賽：窮舉法：DFS(深度優先)

DFS的僞碼

• 從頂點v出發；
• 通路v相鄰且未被通路的頂點 w1
• 依次 w2,...., ,直到不能繼續
• 退回到出發點v，
• 若v的領域還有為通路結點，重複上述

//結果：abdceghf

bool visited[MAX_VERTEX_NUM]; //通路數組标記
void DFSTraverse(Graph G)
{
   //對圖G深度周遊，通路函數是visit()
   for(v=; v<G.vexnum;++v)
     visited[v]=FALSE; // 初始化通路标記
   for(v=;v<G,vexnum;++v) //從v=0開始周遊
     if(!visited[v])
        DFS(G,v);
}

void DFS(Graph G, int v)
{ //從頂點v出發，采用遞歸，深度周遊
    visit(v); // 通路頂點v
    visited[v]=TRUE; //标記通路
    for(w=FirstNeighbor(G,v); w>=;w=NextNeighor(G,v,w))
    //FirstNeighbor()=圖G中頂點x的第一個領接點，有則傳回序列号
    //NextNeighor()=如果y是x的一個領接點，傳回除y之外的頂點x的下一個領接點号
      if(!visited[w])
        DFS(G,w);  
}
           

• 複雜度
  1. 借助棧工作：空間複雜度：O(|V|)
  2. 領接矩陣：查找每個頂點的時間複雜度是 O(|v|2)
  3. 領接表：查找的時間(O(|E|)),通路的時間O(|v|); 總時間=O（|V|+|E|）

部分和問題

• 給定整數： a1,a2,...,an ， 判斷是否可以從中選出若幹數，是其和恰好是k

  *限制條件

  1<=n<=20

  −108<=ai<=108

  −108<=k<=108

• 例子

  輸入：

  n=4

  a={1,2,4,7}

  k=13

  輸出：

  YES {13=2+4+7}

• 例子

  輸入：

  n=4

  a={1,2,4,7}

  k=15

  輸出：

  NO

• 僞代碼

//  輸入：
int a[MAX_N];
int n;  //數組個數 
int k； //部分和

//前i項得到了和sum，現在對i項之後分支計算
dfs(項數i，部分和sum)
 如果，i==n ; 判斷是否sum==k；
 不加a[i]；
 如果，dfs（i+，sum）成立，傳回，true；
 加上a[i]
 如果dfs(i+,sum+a[i])成立，傳回，true
 都不成立傳回，false

solve()

  if(dfs(,)), true，列印
  if(dfs(,))，false，列印
           

#include <iostream>
using namespace std;

bool dfs (int i, int sum, int* a, int n, int k) {
    if (i==n) return sum == k;
    if(dfs(i+, sum, a, n, k)) return true;
    if(dfs(i+, sum+a[i], a, n, k)) return true;
    return false;
}

void solve(int* a, int n, int k) {
    if (dfs(,,a,n,k)) 
        cout<<"Yes"<<'\n';
    else 
        cout <<"No"<<'\n';
);
}


int main(void)
{
    const int MAX_N = ;
    int a[MAX_N] = {, , , };
    int n = , k = ; //k位需要找到的數字

    solve(a, n, k);

    return ;
}
           

• 指派度

  O(2n)

lake counting

• 題目

  大小為 N*M 的園子，雨後積水，八連通的積水被認為是聯系在一起的，求園子有多少水窪

//八連通
***
*w*
***
//輸入：N=10，M=12；
（w表示積水，*表示沒有水）

w*********ww*
*www******www
****ww***ww*
*********ww*
*********w**
**w******w**
*w*w*****ww*
w*w*w*****w*
*w*w******w*
**w*******w*

//輸出：3
           

• 算法：
  1. 從任意w開始，将領接部分用”*”替換
  2. 1次DFS後，與初始 w 連接配接的所有w都被替換為∗
  3. 知道圖中沒有w
  4. 總共進行的DFS次數就是水窪數
• 複雜度：O（8*N*M）

#include <iostream>
using namespace std;

const int MAX_N = ;
const int MAX_M = ;

char field[MAX_N][MAX_M+] = {
"+********++*",
"*+++*****+++",
"****++***++*",
"*********++*",
"*********+**",
"**+******+**",
"*+*+*****++*",
"+*+*+*****+*",
"*+*+******+*",
"**+*******+*"
};

//現在位置(x,y)
void dfs(int x, int y){
    field[x][y]='.';

    //循環周遊移動的8個方向
    for(int dx=-;dx<=;dx++){
        for(int dy=-;dy<=;dy++){
            //x方向移動dx，y方向移動dy，移動結果(nx,ny)
            int nx=x+dx,ny=y+dy;
            //判斷(nx,ny)是不是園子内及是否有積水
            if(<=nx && nx<MAX_N && <=ny && ny<MAX_M && field[nx][ny]=='+')
                dfs(nx,ny);
        }
    }
    return ;
}

void solve(){
    int res=;
    for(int i=;i<MAX_N;i++){
        for(int j=;j<MAX_M;j++){
            if(field[i][j]=='+'){
                dfs(i,j);
                res++;
            }
        }
    }
    cout<<res<<'\n'<<endl;
}

int main(int argc, char* argv[])
{
    solve();
    return ;
}