深度優(yōu)先搜索(Depth-First-Search)

從起點(diǎn)出發(fā)，走過的點(diǎn)要做標(biāo)記，發(fā)現(xiàn)沒有走過的點(diǎn)，就隨意挑一個(gè)往前走，走不了就回退，此種路徑搜索策略就稱為“深度優(yōu)先搜索”，簡稱“深搜”

1.判斷從V出發(fā)是否能走到終點(diǎn)

int main()
{
  將所有點(diǎn)標(biāo)記為新點(diǎn)
  起點(diǎn) = 1;
  終點(diǎn) = 8;
  cout<<Dfs(起點(diǎn));
}

bool Dfs(V){
  if(V為終點(diǎn))
      return true;
  if(V為舊點(diǎn))
      return false;
  將V標(biāo)記為舊點(diǎn)
  對(duì)和V相鄰的每個(gè)節(jié)點(diǎn)U{
      if(Dfs(U)==true)
          return true;
}
  return fasle;
}

2.判斷從V出發(fā)是否能走到終點(diǎn)，如果能，要記錄路徑:

int main()
{
  將所有點(diǎn)標(biāo)記為新點(diǎn);
  depth = 0;
  if(Dfs(起點(diǎn)))
  {
      for(int i=0;i<=depth;++i)
        cout<<path[i]<<endl;
  }
}

Node path[MAX_LEN];//MAX_LEN取節(jié)點(diǎn)總數(shù)即可
int depth;
bool Dfs(V){
    if(V為終點(diǎn))
        path[depth]=V;
        return true;
}
    if(V為舊點(diǎn))
        return false;
    將V標(biāo)記為舊點(diǎn);
    path[depth]=V;
    ++depth;
    對(duì)和V相鄰的每個(gè)節(jié)點(diǎn)U{
        if(Dfs(U)==true)
            return true;
}
  --depth;
   return false;
}

3.深度優(yōu)先遍歷圖上所有節(jié)點(diǎn)

Dfs (V) { 
  if( V是舊點(diǎn) )
    return; 
  將V標(biāo)記為舊點(diǎn) ;
  對(duì)和 V相鄰的每個(gè)點(diǎn) U { 
    Dfs (U);
  }
}
int main() {
  將所有點(diǎn) 都標(biāo)記為新;
  while( 在圖中能找到新點(diǎn) k)
  Dfs (k);
}

4.圖的表示方法--鄰接矩陣

用一個(gè)二維數(shù)組G存放圖，G[i][j]表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間邊的情況（如有無邊，邊方向，權(quán)值大小）
遍歷復(fù)雜度(O(n^2)) n為節(jié)點(diǎn)數(shù)目

5.圖的表示方法--鄰接表

每個(gè)節(jié)點(diǎn)V對(duì)應(yīng)一個(gè)一維數(shù)組(vector),里面存放從V連出去的邊，邊的信息包括另一頂點(diǎn)，還可能包含邊權(quán)值等
遍歷復(fù)雜度(O(n+e)) n為節(jié)點(diǎn)數(shù)目，e為邊數(shù)目