depth_first_search_with_stack.cpp File Reference

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

#include <iostream>
#include <stack>
#include <vector>
#include <cassert>
#include <limits>

Include dependency graph for depth_first_search_with_stack.cpp:

Namespaces
namespace	graph
	Graph Algorithms.
namespace	depth_first_search
	Functions for Depth First Search algorithm.

Functions
void	graph::depth_first_search::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.
std::vector< size_t >	graph::depth_first_search::dfs (const std::vector< std::vector< size_t > > &graph, size_t start)
	Explores the given vertex, exploring a vertex means traversing over all the vertices which are connected to the vertex that is currently being explored and push it onto the stack.
static void	tests ()
int	main ()
	Main function.

Variables
constexpr int	WHITE = 0
constexpr int	GREY = 1
	indicates the node hasn't been explored
constexpr int	BLACK = 2
	indicates node is in stack waiting to be explored
constexpr int64_t	INF = std::numeric_limits<int16_t>::max()
	indicates node has already been explored

Detailed Description

Depth First Search Algorithm using Stack (Depth First Search Algorithm)

Author

Ayaan Khan

Saurav Uppoor

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.

Working

1. Mark all vertices as unvisited (colour it WHITE).
2. Push starting vertex into the stack and colour it GREY.
3. Once a node is popped out of the stack and is coloured GREY, we colour it BLACK.
4. Push all its neighbours which are not coloured BLACK.
5. Repeat steps 4 and 5 until the stack is empty.

Function Documentation

addEdge()

void graph::depth_first_search::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.

Parameters

adj	Adjacency list representation of graph
u	first vertex
v	second vertex

                                                                    {
    /*
    *
    * Here we are considering undirected graph that's the
    * reason we are adding v to the adjacency list representation of u
    * and also adding u to the adjacency list representation of v
    *
    */
    (*adj)[u - 1].push_back(v - 1);
}

dfs()

std::vector< size_t > graph::depth_first_search::dfs	(	const std::vector< std::vector< size_t > > &	graph,
		size_t	start )

Explores the given vertex, exploring a vertex means traversing over all the vertices which are connected to the vertex that is currently being explored and push it onto the stack.

Parameters

adj	graph
start	starting vertex for DFS

Returns

vector with nodes stored in the order of DFS traversal

checked[i] stores the status of each node

while stack is not empty we keep exploring the node on top of stack

push the node to the final result vector

exploring the neighbours of the current node

Node has been explored

                                                                                {
    /// checked[i] stores the status of each node
    std::vector<size_t> checked(graph.size(), WHITE), traversed_path;
 
    checked[start] = GREY;
    std::stack<size_t> stack;
    stack.push(start);
 
    /// while stack is not empty we keep exploring the node on top of stack
    while (!stack.empty()) {
        int act = stack.top();
        stack.pop();
 
        if (checked[act] == GREY) {
            /// push the node to the final result vector
            traversed_path.push_back(act + 1);
 
            /// exploring the neighbours of the current node
            for (auto it : graph[act]) {
                stack.push(it);
                if (checked[it] != BLACK) {
                    checked[it] = GREY;
                }
            }
            checked[act] = BLACK;  /// Node has been explored
        }
    }
    return traversed_path;
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

creating a graph

taking input for the edges

taking input for the starting position

Printing the order of traversal

           {
    tests();  // execute the tests
 
    size_t vertices = 0, edges = 0, start_pos = 1;
    std::vector<size_t> traversal;
 
    std::cout << "Enter the Vertices : ";
    std::cin >> vertices;
    std::cout << "Enter the Edges : ";
    std::cin >> edges;
 
    /// creating a graph
    std::vector<std::vector<size_t> > adj(vertices, std::vector<size_t>());
 
    /// taking input for the 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::depth_first_search::addEdge(&adj, u, v);
    }
 
    /// taking input for the starting position
    std::cout << "Enter the starting vertex [1,n]: " << std::endl;
    std::cin >> start_pos;
    start_pos -= 1;
    traversal = graph::depth_first_search::dfs(adj, start_pos);
 
    /// Printing the order of traversal
    for (auto x : traversal) {
        std::cout << x << ' ';
    }
 
    return 0;
}

Here is the call graph for this function:

tests()

static void tests ( )

static

Self-test implementations

Returns

none

Test 1

for the above sample data, this is the expected output

Test 2

for the above sample data, this is the expected output

Test 3

for the above sample data, this is the expected output

                    {
    size_t start_pos;
 
    /// Test 1
    std::cout << "Case 1: " << std::endl;
    start_pos = 1;
    std::vector<std::vector<size_t> > g1(3, std::vector<size_t>());
 
    graph::depth_first_search::addEdge(&g1, 1, 2);
    graph::depth_first_search::addEdge(&g1, 2, 3);
    graph::depth_first_search::addEdge(&g1, 3, 1);
 
    std::vector<size_t> expected1 {1, 2, 3}; /// for the above sample data, this is the expected output
    assert(graph::depth_first_search::dfs(g1, start_pos - 1) == expected1);
    std::cout << "Passed" << std::endl;
 
    /// Test 2
    std::cout << "Case 2: " << std::endl;
    start_pos = 1;
    std::vector<std::vector<size_t> > g2(4, std::vector<size_t>());
 
    graph::depth_first_search::addEdge(&g2, 1, 2);
    graph::depth_first_search::addEdge(&g2, 1, 3);
    graph::depth_first_search::addEdge(&g2, 2, 4);
    graph::depth_first_search::addEdge(&g2, 4, 1);
 
    std::vector<size_t> expected2 {1, 3, 2, 4}; /// for the above sample data, this is the expected output
    assert(graph::depth_first_search::dfs(g2, start_pos - 1) == expected2);
    std::cout << "Passed" << std::endl;
 
    /// Test 3
    std::cout << "Case 3: " << std::endl;
    start_pos = 2;
    std::vector<std::vector<size_t> > g3(4, std::vector<size_t>());
 
    graph::depth_first_search::addEdge(&g3, 1, 2);
    graph::depth_first_search::addEdge(&g3, 1, 3);
    graph::depth_first_search::addEdge(&g3, 2, 4);
    graph::depth_first_search::addEdge(&g3, 4, 1);
 
    std::vector<size_t> expected3 {2, 4, 1, 3}; /// for the above sample data, this is the expected output
    assert(graph::depth_first_search::dfs(g3, start_pos - 1) == expected3);
    std::cout << "Passed" << std::endl;
 
}

Here is the call graph for this function:

Variable Documentation

WHITE

constexpr int WHITE = 0

constexpr

for IO operations header for std::stack header for std::vector header for preprocessor macro assert() header for limits of integral types