//start adsense code //end adsense code

Graph Traversal

by | Sep 15, 2017

INTRODUCTION

Following up on Graph Theory series, this article will explain the algorithms of traveling through graphs: Depth First Traversal and Breadth First Traversal. Both the methods maintain a boolean array visited[] that is used to avoid repeating nodes in case of cycles or loops.

Prerequisite: Adjacency List 

DEPTH FIRST TRAVERSAL 

In Depth First Traversal, we travel through all successive nodes of the first child of current node before visiting second child of the current node. The following example will illustrate the concept:

Graph Traversal

 

Here, we have two components, one including node 1, and the other that has node 7. To cover all the components, we will iterate through all unvisited nodes in our main(). 

For each component, we visit a root node (say 1 in this case) and travel through its connections successively until we reach an end:

1 –> 4

   –> 3 –> 6 –> 5 –> 2

7 –> 9  –> 8

In order to avoid traveling in a loop and hence doing infinite iterations, we maintain a boolean array visited[] that tells us if node i has been previously visited or not.  Java Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
class DFT
{
    static LinkedList<Integer> adj[];
    static boolean v[];
    static void addEdge(int i, int j) {
        adj[i].addFirst(j);
        adj[j].addFirst(i);
    }
    static void dfs(int cur) {
        System.out.println((cur));
        v[cur]=true;
        int i;
       
        //To iterate through list of connected nodes to node cur
        Iterator it=adj[cur].listIterator();
       
        while(it.hasNext()) {
            i=(int)it.next();            
            if(!v[i])
                dfs(i); //Travel to maximum possible depth first
             
        }
    }
    public static void main(String args[]) {
        int V = 9; //Total Nodes
        adj = new LinkedList[V+1];
        for(int i=1;i<=V;i++)
            adj[i] = new LinkedList<>();
        v = new boolean[V+1];

        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(1, 4);
        addEdge(2, 3);
        addEdge(2, 5);
        addEdge(3, 6);
        addEdge(5, 6);
        addEdge(7, 8);
        addEdge(7, 9);

        //Loop to cover all componenets in case of disconnected graph
        for(int i=1;i<=V;i++) {
            if(!v[i])
                dfs(i);
        }
    }
   
}

BREADTH FIRST TRAVERSAL

 

In Breadth First Traversal, we visit all the nodes directly connected to the current node first and then travel to following nodes. We will travel through the same graph as above, using breadth first traversal:

Graph Traversal

 

In the above graph, we will have a loop iterating through all vertices as we did in Depth First Traversal since we have two components, one including node 1, and the other that has node 7. 

Starting at root (say node 1): 

1 –> 2 –> 3 –> 4  : nodes {2,3,4} have depth = 1   

   –> 5 –> 6           : nodes {5, 6} have depth = 2 

7 –> 8 –> 9           : nodes {8, 9} have depth = 1 

In other words, we travel through all unvisited nodes with depth greater than current node ( +1 ) first before moving on to deeper nodes. Here is a Java Implementation:

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*;
class BFT
{
    static LinkedList<Integer> adj[];
    static boolean[] v;
    static void addEdge(int i, int j) {
        adj[i].addFirst(j);
        adj[j].addFirst(i);
    }
    static void bfs(int cur) {
        Queue<Integer> queue=new PriorityQueue<Integer>();
        queue.add(cur);
        v[cur] = true; //Mark current node as visited

        int node;

        while(queue.size()>0) {
            node = queue.poll();
            System.out.println(node);
           
            //To iterate through list of connected nodes to node cur
            Iterator it = adj[node].listIterator();

            while(it.hasNext()) {
                node = (int)it.next();
                if(!v[node]) {
                    //Add the nodes of height greater than the current node (+1)
                    queue.add(node);
                    v[node] = true;
                }
            }
        }
    }
    public static void main(String args[])
    {
        int V = 9; //Total Nodes
        adj = new LinkedList[V+1];
        for(int i=1;i<=V;i++)
            adj[i] = new LinkedList<>();
        v = new boolean[V+1];

        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(1, 4);
        addEdge(2, 3);
        addEdge(2, 5);
        addEdge(3, 6);
        addEdge(5, 6);
        addEdge(7, 8);
        addEdge(7, 9);

        //Loop to cover all componenets in case of disconnected graph
        for(int i=1;i<=V;i++) {
            if(!v[i])
                bfs(i);
        }
    }
}

What next? Both of these algorithms can be modified to make a search query : Depth First Search (DFS) and Breath First Search (BFS) . All we need to do this return true or false if the value of current node is equal to the query value.

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

More from this Category