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:

Go to the source code of this file.

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.

Definition in file depth_first_search.cpp.

Function Documentation

main()

int main

(

void

)

Main function

creating graph

taking input for edges

running depth first search over graph

Definition at line 109 of file depth_first_search.cpp.

           {
    size_t vertices = 0, edges = 0;
    std::cout << "Enter the Vertices : ";
    std::cin >> vertices;
    std::cout << "Enter the Edges : ";
    std::cin >> edges;
 
    std::vector<std::vector<size_t>> adj(vertices, std::vector<size_t>());
 
    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);
    }
 
    graph::depth_first_search(adj, 2);
 
    std::cout << std::endl;
    return 0;
}