Graph Traversals in C++ and C#

Breadth First Search

From WikiPedia:

“Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors”

I have borrowed heavily the C++ code listing used at the ‘Geeks for geeks’ website and made a few modifications of my own, such as using smart pointers. I have also produced C# equivalents of the code. For reference the website is here:

http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

Full C++/C# code listings:

#include <iostream>
#include <list>
#include <memory>
  
class Graph
{
    int _V;    
    bool _directed;
    std::unique_ptr< std::list<int> > adj;  
     
public:
    Graph(int V, bool directed);
    void AddEdge(int v, int w); 
    void BreadthFirstSearch(int s); 
};
  
Graph::Graph(int V, bool directed) : adj(new std::list<int>[V])
{
    _V = V;
    _directed = directed;       
}   
  
void Graph::AddEdge(int v, int w)
{
    std::list<int>* adjacency = adj.get();
    adjacency[v].push_back(w);
  
    if (!_directed)
    {
        adjacency[w].push_back(v);
    }
}
  
void Graph::BreadthFirstSearch(int s)
{
    bool *visited = new bool[_V];
    for(int i = 0; i < _V; i++)
        visited[i] = false;
  
    // Create a queue for BFS
    std::list<int> queue;
  
    visited[s] = true;
    queue.push_back(s);
  
    // 'i' will be used to get all adjacent vertices of a vertex
    std::list<int>::iterator i;
  
    while(!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
        std::cout << s << " ";
        queue.pop_front();
  
        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for(i = (adj.get())[s].begin(); i != (adj.get())[s].end(); ++i)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}
  
int main()
{
    Graph g(7, true);
    g.AddEdge(0, 1);
    g.AddEdge(0, 2);
    g.AddEdge(0, 3);
    g.AddEdge(1, 0);
    g.AddEdge(1, 5);
    g.AddEdge(2, 5);
	g.AddEdge(3, 0);
	g.AddEdge(3, 4);
	g.AddEdge(4, 6);
	g.AddEdge(5, 1);
	g.AddEdge(6, 5);
  
    std::cout << "Breadth First Traversal from vertex 2:\n";
    g.BreadthFirstSearch(2);
  
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DFS
{
    class Graph
    {
        private int _V;    
        private bool _directed;
        LinkedList<int>[] _adj;  
      
        public Graph(int V, bool directed)
        {
            _adj = new LinkedList<int>[V];

            for (int i = 0; i < _adj.Length; i++)
            {
                _adj[i] = new LinkedList<int>();
            }

            _V = V;
            _directed = directed;       
        }

        public void AddEdge(int v, int w)
        {            
            _adj[v].AddLast(w);

            if (!_directed)
            {
                _adj[w].AddLast(v);
            }
        }

        public void BreadthFirstSearch(int s)
        {
            bool[] visited = new bool[_V];
            for(int i = 0; i < _V; i++)
                visited[i] = false;
   
            // Create a queue for BFS
            LinkedList<int> queue = new LinkedList<int>();
   
            visited[s] = true;
            queue.AddLast(s);          
   
            while(queue.Any())
            {
                // Dequeue a vertex from queue and print it
                s = queue.First();
                Console.Write( s + " " );
                queue.RemoveFirst();

                LinkedList<int> list = _adj[s];

                foreach (var val in list)                
                {
                    if (!visited[val])
                    {
                        visited[val] = true;
                        queue.AddLast(val);
                    }
                }
            }
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph(7, true);
            g.AddEdge(0, 1);
            g.AddEdge(0, 2);
            g.AddEdge(0, 3);
            g.AddEdge(1, 0);
            g.AddEdge(1, 5);
            g.AddEdge(2, 5);
            g.AddEdge(3, 0);
            g.AddEdge(3, 4);
            g.AddEdge(4, 6);
            g.AddEdge(5, 1);
            g.AddEdge(6, 5);
   
            Console.Write("Breadth First Traversal from vertex 2:\n");
            g.BreadthFirstSearch(2);
        }
    }
}

Consider the following 6-node directed graph, as created using calls to the AddEdge function shown in the above code:

Graph_6_node

Running the breadth-first search to traverse the graph gives the following output, showing the graph nodes discovered by the graph traversal:

BFS1

Depth First Search

From Wikipedia:

“Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.”

Again I’ve modified the version of the Depth First Search algorithm from the ‘Geeks for Geeks’ site and done some modifications, including replacing normal pointers with smart pointers, and allowing the graphs to be directed or undirected:

#include <iostream>
#include <list>
#include <memory>
  
class Graph
{
private:
    int _V;    
    bool _directed;
    std::unique_ptr< std::list<int> > adj;  
	void DFSUtil(int v, bool visited[]);
     
public:
    Graph(int V, bool directed);
    void AddEdge(int v, int w); 
    void DepthFirstSearch(int s); 
};
  
Graph::Graph(int V, bool directed) : adj(new std::list<int>[V])
{
    _V = V;
    _directed = directed;       
}   
  
void Graph::AddEdge(int v, int w)
{
    std::list<int>* adjacency = adj.get();
    adjacency[v].push_back(w);
  
    if (!_directed)
    {
        adjacency[w].push_back(v);
    }
}
 
void Graph::DFSUtil(int v, bool visited[])
{
    // Mark the current node as visited and print it
    visited[v] = true;
    std::cout << v << " ";
 
    // Recur for all the vertices adjacent to this vertex
    std::list<int>::iterator i;
    for (i = (adj.get())[v].begin(); i != (adj.get())[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
 
// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
void Graph::DepthFirstSearch(int v)
{
    // Mark all the vertices as not visited
	std::unique_ptr<bool[]> visited(new bool[_V]);
	
    for (int i = 0; i < _V; i++)
        visited[i] = false;
 
    // Call the recursive helper function to print DFS traversal
	DFSUtil(v, visited.get());
}
 
int main()
{
    // Create a graph given in the above diagram
    Graph g(7, true);
    g.AddEdge(0, 1);
    g.AddEdge(0, 2);
    g.AddEdge(0, 3);
    g.AddEdge(1, 0);
    g.AddEdge(1, 5);
    g.AddEdge(2, 5);
    g.AddEdge(3, 0);
    g.AddEdge(3, 4);
    g.AddEdge(4, 6);
    g.AddEdge(5, 1);
    g.AddEdge(6, 5);
 
    std::cout << "Depth First Traversal starting from vertex 2:\n";
	g.DepthFirstSearch(2);
 
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DFS
{
    class Graph
    {
        private int _V;    
        private bool _directed;
        LinkedList<int>[] _adj;  
      
        public Graph(int V, bool directed)
        {
            _adj = new LinkedList<int>[V];

            for (int i = 0; i < _adj.Length; i++)
            {
                _adj[i] = new LinkedList<int>();
            }

            _V = V;
            _directed = directed;       
        }

        public void AddEdge(int v, int w)
        {            
            _adj[v].AddLast(w);

            if (!_directed)
            {
                _adj[w].AddLast(v);
            }
        }

        public void DepthFirstSearch(int v)
        {
            // Mark all the vertices as not visited
            bool[] visited = new bool[_V];
     
            for (int i = 0; i < _V; i++)
                visited[i] = false;
  
            // Call the recursive helper function to print DFS traversal
            DFSUtil(v, visited);          
        }

        private void DFSUtil(int v, bool []visited)
        {
            // Mark the current node as visited and print it
            visited[v] = true;
            Console.Write( v + " " );
  
            // Recur for all the vertices adjacent to this vertex
            LinkedList<int> list = _adj[v];

            foreach (var val in list)
            {
                if (!visited[val])
                    DFSUtil(val, visited);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph(7, true);
            g.AddEdge(0, 1);
            g.AddEdge(0, 2);
            g.AddEdge(0, 3);
            g.AddEdge(1, 0);
            g.AddEdge(1, 5);
            g.AddEdge(2, 5);
            g.AddEdge(3, 0);
            g.AddEdge(3, 4);
            g.AddEdge(4, 6);
            g.AddEdge(5, 1);
            g.AddEdge(6, 5);
   
            Console.Write("Depth First Traversal from vertex 2:\n");
            g.DepthFirstSearch(2);
        }
    }
}

Output of the depth-first search traversal as shown:

DFS1

Latest Comments

  1. Art 4 September 2016
    • Andy 5 September 2016
      • Mickey 25 November 2016

Leave a Reply