Graph traversal is a technique to visit the each nodes of a graph G. It is also use to calculate the order of vertices in traverse process. We visit all the nodes starting from one node which is connected to each other without going into loop.
Basically in graph it may happen some time visiters can visit one node more than once. So, this may cause the going the visiters into infinite loop. So, to protect from this infinite loop condition we keep record of each vertices. Like if visiters visited vertex then the value will be zero if not, then one.
There are two graph traversal techniques
- Breadth-first search
- Depth-first search
Breadth-first search
Breadth-first search graph traversal techniques use a queue data structure as an auxiliary data structure to store nodes for further processing. The size of the queue will be the maximum total number of vertices in the graph.
Read More in detail : Breadth first search graph traversal method
Depth-first search
DFS stands for Depth First Search, is one of the graph traversal algorithms that use Stack data structure. In DFS Traversal go as deep as possible of the graph and then backtrack once reached a vertex that has all its adjacent vertices already visited.
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack data structure to remember to get the next vertex to start a search when a dead end occurs in any iteration.
DFS traversal for tree and graph is similar but the only difference is that a graph can have a cycle but the tree does not have any cycle. So in the graph we have additional array which keeps the record of visited array to protect from infinite loop and not visited again the visited node.
Read More In Detail : Depth First Search graph traversal method
[wpusb]