Breadth First Search [BFS]

-
BFS algorithm works similar to level-order traversal of the tree.

  •   BFS also uses queues. 
  •  Initially, BFS starts at a given vertex, which is at level 0. 
  •  In the first stage, it visits all vertices at level 1. 
  •  In the second stage, it visits all vertices at level 2.

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.
    }
    
    // prints BFS traversal from a given source s
    void BFS(int s)
    {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[V];
        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();
        // Mark the current node as visited and enqueue it
        visited[s]=true;
        queue.add(s);
        while (queue.size() != 0)
        {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s+" ");
            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it
            // visited and enqueue it
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext())
            {
                int n = i.next();
                if (!visited[n])
                {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
    
    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 Breadth First Traversal "+
                           "(starting from vertex 2)");
        g.BFS(2);
    }
}

Output:

Following is Breadth-First Traversal (starting from vertex 2)
2 0 3 1

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

AVL Tree Rotations

-
Image
Rotations When the tree structure changes, we need to modify the tree to restore the AVL tree property. This can be done using single or double rotations. Types of Violations Let us assume the node that must be rebalanced in X. Violations might occur in four cases: Insertion into the left subtree of the left child of X. Insertion into the right subtree of the right child of X.  Insertion into the right subtree of the left child of X. Insertion into the left subtree of the right child of X. Single Rotation Left Left Rotation (LL Rotation) [Case 1]: Rotation does not have to be done at the root of a tree. In general, we start at the node inserted and travel up the tree, updating the balance information at every node on the path. public AVLTree rotateLeft (AVLTree x) {        AVLTree  y = x.right;        // Perform rotation            y.left = x;    ...
Read more

Disjoint Set (Union-Find)

-
A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of non-overlapping subsets. Union-Find Algorithm is an algorithm which performs two operations: Find: Determine which subset a particular element is in. Union: Join two subsets into a single subset.   Source code in java import java.util.*; import java.lang.*; import java.io.*; class Graph { int V, E; // V-> no. of vertices & E->no.of edges Edge edge[]; // /collection of all edges class Edge { int src, dest; }; // Creates a graph with V vertices and E edges Graph(int v,int e) { V = v; E = e; edge = new Edge[E]; for (int i=0; i<e; ++i) edge[i] = new Edge(); } // A utility function to find the subset of an element i int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // A uti...
Read more