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:
[tabs]
[tab title=”C++”]
#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;
}[/tab]
[tab title=”C#”]
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);
}
}
}
[/tab]
[/tabs]
Consider the following 6-node directed graph, as created using calls to the AddEdge function shown in the above code:
Running the breadth-first search to traverse the graph gives the following output, showing the graph nodes discovered by the graph traversal:
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:
[tabs]
[tab title=”C++”]
#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;
}
[/tab]
[tab title=”C#”]
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);
}
}
}
[/tab]
[/tabs]
Output of the depth-first search traversal as shown:
