Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Codes

DFS in a directed graph. Using linked lists representation.
With additional bonus: Makes a topological ordering when the graph is a DAG.

vector<vector<int> > arc;  // edge == arc in a directed graph
vector<bool> visited;      // needed for DFS
vector<int> topSort;       // nodes in topological order
 
void DFS_rec( int node ){
  visited[node] = true;
  for( int j = 0; j < arc[node].size(); j++ )
    if( !visited[arc[node][j]] )
      DFS_rec( arc[node][j] );
  topSort.push_back( node ); 
}
 
void DFS(){
  std::fill( visited.begin(), visited.end(), false );
  topSort.clear();
 
  for( int start = 0; start < N; start++ )
    if( !visited[start] )
      DFS_rec( start );
}
 
// DFS close times of nodes not used here, 
// the order of nodes in the array topSort
// defines a topological order.
// Because of the main fact:  
//       The nodes in DAG during DFS are being closed 
//       in reverse topological order.

courses/a4b36acm1/2022_ls/code.txt · Last modified: 2022/03/17 14:01 by berezovs