Graph Traversal in Data Structure

A graph, a non-linear data structure represented by vertices (nodes) and edges, is defined as an ordered set (V, E) where V represents the set of vertices and E represents the set of edges connecting these vertices. Every pair of vertices is connected by one edge. Graph traversal, a fundamental operation in graph theory and computer science, involves systematically visiting all nodes in a graph. This graph traversal process is crucial in various applications such as network routing, web crawling, and social network analysis.

Methods of Graph Traversal in Data Structure

In simple words, traversal means the process of visiting every node in the graph.
There are two standard methods of graph traversal in data structure Breadth-First Search and Depth First Search

BFS Graph Traversal

Breadth-First Search (BFS) is a graph traversal algorithm, where we start from a selected(source) node and traverse the graph level by level, by exploring the neighbor nodes at each level.

Algorithm

Breadth-First Search (BFS) is a crucial algorithm for graph traversal, prioritizing the exploration of a node’s immediate neighbors before advancing to their next-level neighbors. This strategy enables efficient searching for the shortest paths in unweighted graphs and ensures all nodes are visited systematically, starting from the closest. Employing a FIFO queue, BFS initiates from a chosen source node, exploring and marking each node by visiting adjacent unvisited ones, adding them to the queue for subsequent exploration. This process continues until the queue empties, signifying the completion of traversal.

Let’s see how to use a Breadth-First Search from Node A.

We need to use two data structures a Queue (for FIFO property) and a Set visited (to mark the visited nodes).

Step: 1
We pick A as the starting point and add A to the Queue. To prevent cycles, we also mark A as visited(by adding it to the visited set).

Step: 2
We remove the head of the Queue (i.e. A now). The Node was First In (inserted first) in the Queue.
We process A and pick all its neighbours that have not been visited yet(i.e., not in the visited set). Those are D, C, and E.
We add D, C, and E to the Queue and these to the visited set.

Step :3
Next, we pull the head of the Queue, , i.e. D.
We process D and consider all neighbours of D, which are A and E, but since both A and E are in the visited set, we ignore them and move forward.

Step :4
Next, we pull the head of the Queue, i.e. E.
We process E.
Then we need to consider all neighbours of E, which are A and D, but since both A and D are in the visited set, we ignore them and move forward.

Next, we pull the head of the Queue, i.e. C.
We process C.
Then we consider all neighbours of C, which are A and B. Since A is in the visited set, we ignore it. But as B has not yet been visited, we visit B and add it to the Queue.

Step 5:
Finally, we pick B from Queue, and its neighbour is C, which has already visited. We have nothing else in Queue to process, so we are done traversing the graph.

So the order in which we processed/explored the elements are: A, D, E, C, B which is the Breadth-First Search of the above Graph.

Pseudocode of Breadth-First Search

Create a Queue (say Q)
Mark Vertex V as Visited.
Put V into the Queue

While Q is not empty
	Remove the head of Q (Let it be Vertex U)
	Iterate all Unvisited Neighbours of U 
		Mark the neighbour as Visited
		Enqueue the Neighbour into Q.

Code Implementation

#include<iostream>
#include <list>

using namespace std;

// This class represents an undirected graph using adjacency list representation
class Graph
{
	int numberOfVertices; // No. of vertices

	// Pointer to an array containing adjacency lists
	list<int> *adjacencyList;
public:
	Graph(int numberOfVertices); // Constructor

	void addEdge(int from, int to);

	void bfsTraversal(int startingVertex);
};

Graph::Graph(int numberOfVertices)
{
	this->numberOfVertices = numberOfVertices;
	adjacencyList = new list<int>[numberOfVertices];
}

void Graph::addEdge(int v, int w)
{
	adjacencyList[v].push_back(w);
	adjacencyList[w].push_back(v);
}

void Graph::bfsTraversal(int vertex)
{
	// Mark all the vertices as not visited
	bool *visited = new bool[numberOfVertices];
	for(int i = 0; i < numberOfVertices; i++)
		visited[i] = false;

	// Create a queue for bfsTraversal
	list<int> queue;

	visited[vertex] = true;
	queue.push_back(vertex);

	list<int>::iterator i;

	while(!queue.empty())
	{
		// Dequeue a vertex from queue and print it
		vertex = queue.front();
		cout << vertex << " ";
		queue.pop_front();

		// If a adjacent vertex has not been visited, then mark it visited and enqueue it
		for (i = adjacencyList[vertex].begin(); i != adjacencyList[vertex].end(); ++i)
		{
			if (!visited[*i])
			{
				visited[*i] = true;
				queue.push_back(*i);
			}
		}
	}
}

int main()
{
    Graph graph(7);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 1);
    graph.addEdge(2, 5);
    graph.addEdge(3, 6);

    cout << "Breadth First Traversal from 1 is : \n";
    graph.bfsTraversal(1);

    return 0;
}

Output:

Breadth First Traversal from 1 is : 
1 0 3 4 2 6 5

DFS Graph Traversal

Depth First Search (DFS) is a graph traversal algorithm, where we start from a selected(source) node and go into the depth of this node by recursively calling the DFS function until no children are encountered. When the dead-end is reached, this algorithm backtracks and starts visiting the other children of the current node.

Algorithm

Let’s see how we can approach the depth first search algorithm.

We can start our DFS process from any arbitrary vertex of the graph. Suppose we start our depth first search process from vertex A, since need to go as deep as possible in the graph, therefore we will go to one of the adjacent vertices of A.

The only thing we must take care of during the DFS process is that “we must not visit already visited vertices again.”

• We have two choices i.e. either to go to vertex B or vertex D. Let’s say we went to vertex B now again we will go to one of its adjacent vertices.
• We are having three choices i.e. either to go to vertex C or vertex E or back to vertex A (because A is also adjacent to vertex B ) but we will consider going A again because we had already visited it. Let’s say we went to vertex E, again from E we need to go to one of its adjacent vertices.
• Now at E we have three choices i.e. either to go to vertex F or vertex G or vertex B back but we will not consider it because it is already visited. Let’s say we went to vertex F.
• From vertex F we have only one unvisited node left i.e. vertex G, so we will visit it.
• We don’t have any unvisited vertex adjacent to G so we will go back to F.
• Now from F also we don’t have any choice so we will go back to E and from E the case is the same again so we will go back to B.
• From B we have C as an unvisited adjacent vertex so we will go to vertex C and then from C we will go to vertex D as it is unvisited till now.
• You can see now all the vertices have been traversed in the following order —A→B→E→F→G→C→D.

Pseudocode of DFS Algorithm

DFS(visited, u):
    visited[u]=True
    Print u
    for each v in adj[u]:
        if(visited[v]=False)
            DFS(visited,v)

Code Implementation

#include <bits/stdc++.h>
using namespace std;
class Graph
{

    // V denotes the number of vertices,
    // adj is the adjacency list of
    // the graph.
    int V;
    map<int, list<int>> adj;

public:
    // Constructor
    Graph(int v)
    {
        // Initializing V
        V = v;
    }

    // Function to insert an edge
    // in the graph.
    void insertEdge(int u, int v)
    {

        // Adding edge from u to v.
        adj[u].push_back(v);
        // Adding edge from v to u.
        adj[v].push_back(u);
    }

    // A helper function for DFS.
    void DFS_helper(int u, bool visited[])
    {
        // Marking u as visited
        visited[u] = true;

        // Printing it's value
        cout << u << " ";

        // Checking for all the
        // nodes adjacent to u.
        for (int v : adj[u])
        {
            // If any node is not visited
            // till now.
            if (!visited[v])
            {
                // Then, call DFS_helper with index
                // as v.
                DFS_helper(v, visited);
            }
        }
    }
    // DFS function
    void DFS(int u)
    {
        // Declaring a boolean
        // visited array of size V.
        bool visited[V];
        // Calling DFS_helper function
        // with index as u.
        DFS_helper(u, visited);
    }
};

// Driver Function
int main()
{
    // Declare a object
    // of graph type.
    Graph g(7);
    // Add all the edges through
    // insertEdge function.
    g.insertEdge(0, 1);
    g.insertEdge(0, 3);
    g.insertEdge(1, 4);
    g.insertEdge(1, 2);
    g.insertEdge(2, 3);
    g.insertEdge(4, 5);
    g.insertEdge(4, 6);
    g.insertEdge(5, 6);
    cout << "The DFS traversal of the given graph starting from node 0 is - ";
    // Call for DFS with
    // index as 0.
    g.DFS(0);
    return 0;
}

Output:

The DFS traversal of the given graph starting from node 0 is:
0 1 4 5 6 2 3

Conclusion

• A graph is a non-linear data structure, which is represented by vertices(nodes) and edges. Every pair of vertices is connected with one edge between them.
• Graph traversal techniques are methods used to visit all the nodes of a graph systematically.
• There are two sorts of traversal algorithms in the graph. These are referred to as the Breadth First Search and the Depth First Search.
• BFS (Breadth-First Search) traverses graph level by level, while DFS (Depth-First Search) explores as far as possible along each branch before backtracking.