Depth First Search [DFS]

-
Graph traversal algorithms are also called graph search algorithm.
Two such algorithms for traversing the graphs :
  • Depth First Search [DFS]
  • Breadth First Search [BFS]
Depth First Search [DFS]:

DFS algorithm works in a manner similar to a preorder traversal of the trees.
We encountered the following types of edge:
  • Tree edge: encounter new vertex.
  • Back edge: from descendant to ancestor.
  • Forward edge: from ancestor to descendant.
  • Cross edge: between a tree or subtree.
To track the vertices two colours are enough:
  • false → Vertex is unvisited.
  • true  → Vertex is visited.

Source code in Java:

import java.util.LinkedList;
import java.util.Iterator;

/**
 *
 * @author Rohan
 */

public class Graph 
{
    private int V;   // No. of vertices
    // Array  of lists for Adjacency List Representation

    private LinkedList<Integer> adj[];
    // Constructor

    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }
    
    //Function to add an edge into the graph

    void addEdge(int v, int w)
    {
        adj[v].add(w);  // Add w to v's list.
    }
    
    void DFSUtil(int j,boolean visited[])
    {
        // Mark the current node as visited and print it

        visited[j] = true;
        System.out.print(j+" ");
        // Recur for all the vertices adjacent to this vertex

        Iterator<Integer> i = adj[j].listIterator();
        while (i.hasNext())
        {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
    // The function to do DFS traversal. It uses recursive DFSUtil()

    void DFS(int i)
    {
        // Mark all the vertices as not visited(set as
        // false by default in java)

        boolean visited[] = new boolean[V];
        // Call the recursive helper function to print DFS traversal
        DFSUtil(i, visited);
    }
    
    public static void main(String args[])
    {
        Graph g = new Graph(4);
        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("Following is Depth First Traversal "+
                           "(starting from vertex 2)");
        g.DFS(2);
    }
}

 Output:

 Following is Depth First Traversal (starting from vertex 2)

2 0 1 3

Explanation:











Comments

Post a Comment

Popular posts from this blog

How to Build REST API Using PHP

-
Image
Create REST API in PHP API stands for Application Programming Interface and the idea behind API is to connect different applications irrespective of their platforms to share information. Generally, API takes requests from different applications, processes it and gives back the response. What is REST API? REST stands for Representational State Transfer and it means that the request and the response should contain a representation of the information i.e., should be in a certain format. So basically, the requests must use proper HTTP methods and the response must be in a proper format like JSON or XML instead of plain text. REST API is nothing but a normal API with a set of principles. We need to follow a set of rules while creating and consuming REST API. The rules include the following : 1. Use appropriate HTTP methods while performing API calls. The following are the four primary HTTP methods which should be used to send and receive API requests.     ...
Read more

What is the difference between the add and offer methods in a Queue in Java?

-
If a collection refuses to add a particular element for any reason other than that it already contains the element, it  must throw  an exception (rather than returning false). This preserves the invariant that a collection always contains the specified element after this call returns. offer  method - tries to add an element to a queue, and returns  false  if the element can't be added (like in case when a queue is full), or  true  if the element was added, and doesn't throw any specific exception. add  method - tries to add an element to a queue, returns  true  if the element was added, or throws an IllegalStateException if no space is currently available. There is no difference for the implementation of  PriorityQueue.add : public boolean add ( E e ) { return offer ( e ); } For  AbstractQueue  there actually is a difference: public boolean add ( E e ) { if ( offer ( e )) ret...
Read more

Dynamic Programming

-
Image
What is dynamic programming? It is a way of making your algorithm more efficient by storing some of the intermediate results and it works really well when your algorithm has a lot of repetitive computations. So that you don't have to repeat those computations over and over again.  I'm gonna give you a concrete example of how it works with Fibonacci Sequence (1, 1, 2, 3, 5, 8, ....). Let see how we can solve the problem using dynamic programming. There are typically three steps you can take: 1. Recursion. 2. Store (Memoize). 3. Bottom-up. Recursion solution   public static  int fibSeq (int n)   {       // this function return the value of Fibonacci Sequence at n position              if(n ==1 || n==2)            return 1;       else            return (fibSeq(n-1) + fibSeq(n-2));        ...
Read more