Now, Most probably
you’re wondering what is BFS and DFS, right?
Well, We’ll move there
in a bit, but first let’s get through some other basic terminologies of graphs
as well!
In the last section, We
considered the following graph right?
Now for purposes of
simplicity let’s define a graph in another way, This time We’ll use numbers
instead of names:
So, here the vertices
are numbered: from 1 through 30 and there are 27 edges.
Now Just imagine that all
of these vertices were actually places and the edges that are placed in between
two vertices indicate that there is a road/path between them i.e. You could
reach the other vertex from one of those vertices.
But if they are like
roads, then there must be two sorts/kinds of them, right? Because Every road is
either two-way whereby you could go in both directions or one way, whereby you
could move in just one direction.
In Graph Terminology a
one-way path/road/edge is called unidirectional and it is defined to be in one
of the directions only. A Two way path/road/edge is known as bi-directional and
it is in both the directions i.e. If you could go from A to B, then you could
also come back from B to A.
A Unidirectional Graph may also be called a Directed Graph while a Bi-Directional Graph may be called an Undirected Graph.
Now, Lets consider that
all the edges in the Graph above are Unidirectional, which gives us something
like this and you could only move from a vertex of lower number to a vertex of
higher number and not the other way round! Eg: You may move from 12 to 25, but
not from 25 to 12.
Now Let’s consider the
following problem: Can we reach a particular vertex, say ‘x’ from any other
vertex, say ‘y’. If we ask in particular with reference to the above graph if
we could reach vertex 30 from vertex 1, the answer would be yes, We would go
from: 1à6à13à30.
But if we ask if we
could reach vertex 26 from vertex 13, the answer would be no! Because the edges
are unidirectional and there’s no any route(series of paths, taken one after
another) possible which goes from vertex 26 to 13.
Could we generalize an
algorithm which could work on solving the problem stated above for any provided
graph?
As it turns out: Yes, We
Can!
This is what BFS(Breadth
First Search) and DFS(Depth First Search) are all about.
Depth First Search is
slightly more popular than Breadth First Search for being slightly more
efficient and easy to implement, thus we should look onto just Depth First
Search though you could look upon BFS on Google if you wish to!
For DFS, our task is to
find out which Vetices/nodes could be reached from any other given vertex/node.
We take the starting
vertex as ‘v’ and associate every vertex with a property named, ‘visited’ which
is a Boolean indicating whether that particular vertex could be reached/visited
from the given starting point and has been covered already or not, The Pseudocode
is like:
DFS(G,v) ( v is the vertex where the search starts )
Stack S := {}; ( start with an
empty stack )
for each vertex u, set visited[u] := false;
push S, v;
while (S is not empty) do
u := pop S;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbour w
of u
push S, w;
end if
end while
END DFS()
Here’s an animation
demonstrating the same:
In C++ Code we may have
DFS declared in an almost user-friendly manner in the following way:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
typedef struct edge{
int
from;
int
to;
}edge;
typedef struct vertex{
int
num;
vector<edge>
to; //The Edges
which end up at any particular vertex
vector<edge>
from; //The Edges which
start from any particular vertex
bool
visited;
}vertex;
typedef struct graph{
vector<vertex>
V;
vector<edge>
E;
}graph;
int main(){
graph
G;
int
n,m,i; // n = Number of
Vertexes and m = Number of Edges
cout<<"How
many Vertices would you like to have?"<<endl;
cin>>n;
G.V.resize(n+1); //
Telling the Computer to have spaces for n elements in the Vertex vector
for(i
= 1;i<=n;i++){
G.V[i].visited
= false;
G.V[i].num
= i;
}
cout<<"How
many edges would you like to have?"<<endl;
cin>>m;
G.E.resize(m); //Telling
the Computer to have space for m elements in the edges vector
for(i
= 0;i<m;i++){
cout<<"Enter
the vertex from which the "<<i<<"th edge starts: ";
cin>>G.E[i].from;
cout<<endl<<"Enter
the vertex to which the "<<i<<"th edge goes:";
cin>>G.E[i].to;
cout<<endl;
G.V[G.E[i].from].from.push_back(G.E[i]); //Storing to the from attribute of every vertex
G.V[G.E[i].to].to.push_back(G.E[i]); //Storing to the to
attribute of every vertex
}
cout<<"From
which vertex would you like to know the other vertices which could be reached
by it?"<<endl;
int
start;
cin>>start; //Getting the Start Vertex
for DFS
vector<int>
reachable;
//DFS
starts from here
vertex
u;
stack<vertex>
S;
S.push(G.V[start]);
while(!S.empty()){
u
= S.top();S.pop();
if(u.visited==false){
u.visited
= true;
reachable.push_back(u.num);
for(i
= 0;i<u.from.size();i++){
if(G.V[u.from[i].to].visited==false){
S.push(G.V[u.from[i].to]);
}
}
}
}
cout<<"The
Vertices that could be visited from Vertex "<<start<<"
are: ";
for(i
= 0;i<reachable.size();i++){
cout<<reachable[i]<<",
";
}
cout<<endl;
}
We start with a declaration of the types we are going
to need, including vertex, edges and graphs with all the required attributes,
then we take input and store it where it needs to be stored and then implement
exactly like the Pseudocode.
We could implement DFS using a Recursive Method as
well!
NOTE: The <stack> library consists of functions
in C++ using which we could declare and make use of stacks including the pop
and push features, as we discussed in previous sections. .resize() is a
function from the vector library which is used to set the size of a vector.
Exercise
Implement DFS using a Recursive Method!
Problems
Comments
Post a Comment