A traversal is a systematic walk which visits the nodes of the graph in a specific order.
Two Types:-
1.Breadth First Traversal
2.Depth First Traversal
Breadth First Traversal-
It traverses the successors of the start node,generation after generation in a horizontal or linear fashion.
Algorithm-
BFT(s)
{
//s is the start vertex of the traversal in an undirected graph G.
//Q is a queue which keeps track of the vertices whose adjacent nodes are to be visited.
//Vertices which have been visited have their ‘visited’ flags set to 1.
//Initially,visited(vertex) = 0 for all vertices of graph G.
//queue is a linear list in which all insertions are made at one end and all deletions are made at the other end.
Initialize queue Q;
visited(s)=1;
ENQUEUE (Q,s) //insert s into queue Q
while (Q is not empty) //process until Q is empty
{
DEQUEUE(Q,s) //delete s from Q
print (s); //output the vertex visited.
for all vertices v adjacent to s
{
if(visited[v]=0)
{
ENQUEUE(Q,v);
visited(v)=1;
}
}
}
}
Code-
[cpp]
vector<int>a[1005];
int visited[1000]={0};
//N is the number of nodes and M is the number of edges
//preparing adjacency list
for(i=0;i<M;i++)
{
scanf(“%d %d”,&x,&y);
a[x].push_back(y);
}
queue<int> q;
visited[s]=1;
q.push(s);
while(!q.empty())
{
s=q.front();
//retrieving the element which is to be deleted.
printf(“%d “,s);
q.pop();
//checking vertices adjacent to s
for(int i=0;i<a[s].size();i++)
{
if(visited[a[s][i]]==0)
{
visited[a[s][i]]=1;
q.push(a[s][i]);
}
}
}
[/cpp]
Depth First Traversal-
This traversal visits each node,that is,the first occurring among its adjacent nodes and successively repeats the operation,thus moving deeper and deeper into the graph.In contrast,BFT moves side ways or breadth ways in the graph.
Algorithm-
DFT(s)
{
// s is the start vertex
visited(s)=1;
print (s);
for each vertex v adjacent to s
{
if( visited(v)=0 ) {DFT(v);}
}
}
Code-
[cpp]
vector<int>a[1005];
int visited[1000]={0};
//N is the number of nodes and M is the number of edges
//preparing adjacency list
for(i=0;i<M;i++)
{
scanf(“%d %d”,&x,&y);
a[x].push_back(y);
}
for(int i=0;i<N;i++)
{
if(visited[i]==0)
{
dfs(i);
}
}
void dfs(int node)
{
visited[node]=1;
printf(“%d “,node);
for(int i=0;i<a[s].size();i++)
{
if(visited[a[s][i]]==0)
{
dfs(a[s][i]);
}
}
}
[/cpp]
NOTE-
If an adjacency matrix is used to represent the graph,the time complexity in both the traversals will be O(N^2). But,the use of adjacency list results in a time complexity of O(N).
