Friday 14 November 2014

Graph : Depth First Traversal and Breadth First Traversal for connected Graphs in Java

Assumption : Given Graph is connected.

PS : For Traversal in Disconnected Graph, refer the post of Detecting Cycle in Graph



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class TGraph {

    int v;
    ArrayList<Integer>[] alist;
    boolean[] visited;


    TGraph(int v) {
        this.v = v;
        this.alist = new ArrayList[v];
        this.visited = new boolean[v];
    }

    public void initList(){
        for(int i=0;i<alist.length;i++)
            alist[i] = new ArrayList<Integer>();
    }

    public void addEdge(int u,int v) {
        alist[u].add(v);
    }

    public void BFS(int u) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(u);
        while(!q.isEmpty()) {
            int v = q.poll();
            visited[v] = true;
            for(int i=0;i<alist[v].size();i++) {
              int n = alist[v].get(i);
                if(!visited[n]) q.add(n);
            }
            System.out.print(v + " ");
        }
    }


    public void DFS(int u) {
        visited[u] = true;
        System.out.print(u + " ");
        for(int i=0;i<alist[u].size();i++) {
            int v = alist[u].get(i);
            if(!visited[v]) DFS(v);
        }
    }

    public static void main(String[] args) {
        TGraph g= new TGraph(4);
        g.initList();
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        System.out.println("Breadth First Traversal (starting from vertex 2)");
        g.BFS(2);
        System.out.println();


        System.out.println("Depth First Traversal (starting from vertex 2)");
        TGraph g1 = new TGraph(4);
        g1.initList();
        g1.addEdge(0, 1);
        g1.addEdge(0, 2);
        g1.addEdge(1, 2);
        g1.addEdge(2, 0);
        g1.addEdge(2, 3);
        g1.addEdge(3, 3);
        g1.DFS(2);
    }


}

No comments:

Post a Comment