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:

Go to the source code of this file.

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.

Definition in file depth_first_search_with_stack.cpp.

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

Definition at line 64 of file depth_first_search_with_stack.cpp.

                                                                    {
    /*
    *
    * 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

Definition at line 87 of file depth_first_search_with_stack.cpp.

                                                                                {
    std::vector<size_t> checked(graph.size(), WHITE), traversed_path;
 
    checked[start] = GREY;
    std::stack<size_t> stack;
    stack.push(start);
 
    while (!stack.empty()) {
        int act = stack.top();
        stack.pop();
 
        if (checked[act] == GREY) {
            traversed_path.push_back(act + 1);
 
            for (auto it : graph[act]) {
                stack.push(it);
                if (checked[it] != BLACK) {
                    checked[it] = GREY;
                }
            }
            checked[act] = BLACK;  
        }
    }
    return traversed_path;
}

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

Definition at line 173 of file depth_first_search_with_stack.cpp.

           {
    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;
 
    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::depth_first_search::addEdge(&adj, u, v);
    }
 
    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);
 
    for (auto x : traversal) {
        std::cout << x << ' ';
    }
 
    return 0;
}

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

Definition at line 123 of file depth_first_search_with_stack.cpp.

                    {
    size_t start_pos;
 
    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}; 
    assert(graph::depth_first_search::dfs(g1, start_pos - 1) == expected1);
    std::cout << "Passed" << std::endl;
 
    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}; 
    assert(graph::depth_first_search::dfs(g2, start_pos - 1) == expected2);
    std::cout << "Passed" << std::endl;
 
    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}; 
    assert(graph::depth_first_search::dfs(g3, start_pos - 1) == expected3);
    std::cout << "Passed" << std::endl;
 
}

Variable Documentation

BLACK

int BLACK = 2

constexpr

indicates node is in stack waiting to be explored

Definition at line 40 of file depth_first_search_with_stack.cpp.

GREY

int GREY = 1

constexpr

indicates the node hasn't been explored

Definition at line 39 of file depth_first_search_with_stack.cpp.

INF

int64_t INF = std::numeric_limits<int16_t>::max()

constexpr

indicates node has already been explored

Definition at line 41 of file depth_first_search_with_stack.cpp.

WHITE

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

Definition at line 38 of file depth_first_search_with_stack.cpp.