/************************************************************************* 
  > File Name: DFS.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<list> 
using namespace std; 
 
/* 圖 */ 
class Graph 
{ 
  int V;                // 頂點(diǎn)數(shù) 
  list<int> *adj;           // 鄰接表 
  void DFSUtil(int v, bool visited[]); // 從頂點(diǎn)v深度優(yōu)先遍歷 
public: 
  Graph(int V);            // 構(gòu)造函數(shù) 
  void addEdge(int v, int w);     // 向圖中添加邊 
  void DFS(int v);           // 從v開始深度優(yōu)先遍歷圖 
}; 
 
/* 構(gòu)造函數(shù) */ 
Graph::Graph(int V) 
{ 
  this->V = V; 
  adj = new list<int>[V]; 
} 
 
/* 添加邊，構(gòu)造鄰接表 */ 
void Graph::addEdge(int v, int w) 
{ 
  adj[v].push_back(w);         // 將w添加到v的鏈表 
} 
 
/* 從v開始深度優(yōu)先遍歷 */ 
void Graph::DFSUtil(int v, bool visited[]) 
{ 
  // 訪問頂點(diǎn)v并輸出 
  visited[v] = true; 
  cout << v << " "; 
 
  list<int>::iterator i; 
 
  for(i=adj[v].begin(); i!=adj[v].end(); ++i) 
    if(!visited[*i])       // 若鄰接點(diǎn)尚未訪問 
      DFSUtil(*i, visited);   // 遞歸 
} 
 
/* 對(duì)圖進(jìn)行深度優(yōu)先遍歷，調(diào)用遞歸函數(shù)DFSUtil() */ 
void Graph::DFS(int v) 
{ 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
 
  // 假設(shè)從給定頂點(diǎn)v可以到達(dá)圖的所有頂點(diǎn) 
  DFSUtil(v, visited); 
} 
 
/* 測(cè)試 */ 
int main() 
{ 
  Graph g(4); 
  g.addEdge(0, 1); 
  g.addEdge(0, 2); 
  g.addEdge(1, 2); 
  g.addEdge(2, 0); 
  g.addEdge(2, 3); 
  g.addEdge(3, 3); 
 
  cout << "Depth First Traversal (starting from vertex 2) \n"; 
  g.DFS(2); 
  cout << endl; 
   
  return 0; 
}

void Graph::DFS() 
{ 
  bool *visited = new bool[V]; 
  for(int i=0; i<V; ++i) 
    visited[i] = false; 
   
  // 對(duì)每個(gè)頂點(diǎn)調(diào)用DFSUtil()，從0開始 
  for(int i=0; i<V; ++i) 
    if(!visited[i]) 
      DFSUtil(i, visited); 
} 

void Graph::addEdge(int v, int w) 
{ 
  adj[v].push_back(w);     // 將w加到v的list 
  adj[w].push_back(v); 
}