Overview
- Traversing Graph
- BFS
- Logic for BFS
- Example
- DFS
- Logic for DFS
- Example
Traversing
There are two standard way of
traversing a graph
- BFS Breadth first search
- DFS Depth First Search
BFS
- Traversing graph has only issue that graph may have cycle. You may revisit a node .
- To avoid processing a node more than once , we divide the vertices into two categories :
- visited
- Not visited
- A boolean visited array is used to mark the visited vertices
- BFs ( Breadth First Search) uses a queue
data structure for traversal . - Traversing begin from a node called source node
Logic for BFS
BFS (G,S)
let Q be the queue
Q.insert(s);
v[s]=true;
while(!Q.is empty())
{
n=Q.getfront();
Q.del();
for all the neighbour u of n
if v[u]==false
Q.insert(u);
v[u]=true;
}
Example:
DFS
DFS is Depth first search.The main defferenee between BFS and DFS is that the DFS uses stuck in place of Queue
Logic for DFS
BFS (G,S)
let stack be the queue
stack.push(s);
v[s]=true;
while(!stack.is empty())
{
n=stack.getfront();
stack.pop();
for all the neighbour u of n
if v[u]==false
stack.insert(u);
v[u]=true;
}
Example
