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
namespace	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.
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.
void	graph::depth_first_search (const std::vector< std::vector< size_t > > &adj, size_t start)
	initiates depth first search algorithm.
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

           {
    size_t vertices = 0, edges = 0;
    std::cout << "Enter the Vertices : ";
    std::cin >> vertices;
    std::cout << "Enter the Edges : ";
    std::cin >> edges;
 
    /// creating graph
    std::vector<std::vector<size_t>> adj(vertices, std::vector<size_t>());
 
    /// taking input for edges
    std::cout << "Enter the vertices which have edges between them : "
              << std::endl;
    while (edges--) {
        size_t u = 0, v = 0;
        std::cin >> u >> v;
        graph::addEdge(&adj, u, v);
    }
 
    /// running depth first search over graph
    graph::depth_first_search(adj, 2);
 
    std::cout << std::endl;
    return 0;
}

Here is the call graph for this function: