Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
depth_first_search.cpp File Reference

Depth First Search Algorithm (Depth First Search) More...

#include <algorithm>
#include <iostream>
#include <vector>
Include dependency graph for depth_first_search.cpp:

Namespaces

 graph
 Graph algorithms.
 

Functions

void graph::addEdge (std::vector< std::vector< size_t >> *adj, size_t u, size_t v)
 Adds and edge between two vertices of graph say u and v in this case. More...
 
void graph::explore (const std::vector< std::vector< size_t >> &adj, size_t v, std::vector< bool > *visited)
 Explores the given vertex, exploring a vertex means traversing over all the vertices which are connected to the vertex that is currently being explored. More...
 
void graph::depth_first_search (const std::vector< std::vector< size_t >> &adj, size_t start)
 initiates depth first search algorithm. More...
 
int main ()
 

Detailed Description

Depth First Search Algorithm (Depth First Search)

Author
Ayaan Khan

Depth First Search also quoted as DFS is a Graph Traversal Algorithm. Time Complexity O(|V| + |E|) where V is number of vertices and E is number of edges in graph.

Application of Depth First Search are

  1. Finding connected components
  2. Finding 2-(edge or vertex)-connected components.
  3. Finding 3-(edge or vertex)-connected components.
  4. Finding the bridges of a graph.
  5. Generating words in order to plot the limit set of a group.
  6. Finding strongly connected components.

And there are many more...

Working

  1. Mark all vertices as unvisited first
  2. start exploring from some starting vertex.

    While exploring vertex we mark the vertex as visited and start exploring the vertices connected to this vertex in recursive way.

Function Documentation

◆ main()

int main ( void  )

Main function

creating graph

taking input for edges

running depth first search over graph

109  {
110  size_t vertices = 0, edges = 0;
111  std::cout << "Enter the Vertices : ";
112  std::cin >> vertices;
113  std::cout << "Enter the Edges : ";
114  std::cin >> edges;
115 
116  /// creating graph
118 
119  /// taking input for edges
120  std::cout << "Enter the vertices which have edges between them : "
121  << std::endl;
122  while (edges--) {
123  size_t u = 0, v = 0;
124  std::cin >> u >> v;
125  graph::addEdge(&adj, u, v);
126  }
127 
128  /// running depth first search over graph
130 
131  std::cout << std::endl;
132  return 0;
133 }
Here is the call graph for this function:
std::vector
STL class.
graph::depth_first_search
void depth_first_search(const std::vector< std::vector< size_t >> &adj, size_t start)
initiates depth first search algorithm.
Definition: depth_first_search.cpp:99
std::cout
graph::addEdge
void addEdge(std::vector< std::vector< int >> *adj, int u, int v)
Function that add edge between two nodes or vertices of graph.
Definition: connected_components.cpp:46
std::endl
T endl(T... args)
std::cin