Breadth First Traversal for a Graph

Breadth First Traversal for a Graph

Here given code implementation process.

//C Program, Breadth First Traversal in Directed graph
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode{
    int vId;//Vertices id
    struct AjlistNode*next;
};

struct Graph{
    int data; //node key value
    struct AjlistNode*next;
};

struct Queue{
    int element;
    struct Queue*next;
};

int size; //number of nodes

//set node key value
void setData(struct Graph*node){
    if(node!=NULL && size>0){
        int index=0;
        for(index;index<size;index++){
            //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }else{
    printf("Vertic Node is Empty");
  }
}
//Add Queue Element
void enqueue(int data,struct Queue**queue){
    struct Queue *newNode=(struct Queue*)malloc(sizeof(struct Queue));

    if(newNode!=NULL){
        newNode->element=data;
        newNode->next=NULL;
        if(*queue!=NULL){
            struct Queue*temp=*queue;
            while(temp->next!=NULL){
                temp=temp->next;
            }
            temp->next=newNode;
        }else{
            *queue=newNode;
        }
    }else{
         printf("\n Memory overflow");
    }
}
//remove single element into queue
void dequeue(struct Queue**queue){
    struct Queue*temp=(*queue);
    (*queue)=temp->next;
    free(temp);
    temp=NULL;
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E){
    //add edge form V to E
    //V and E is Node location
    if(V<size && E <size){
        //first create Adjacency node
        struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
            sizeof(struct AjlistNode)
        );
        if(newEdge!=NULL){
                        
            newEdge->next=NULL;
            newEdge->vId=E;

            struct AjlistNode *temp=node[V].next;

            if(temp==NULL){
                node[V].next=newEdge;
            }else{
                //Add node at last
                while(temp->next!=NULL){
                    temp=temp->next;
                }      
                temp->next=newEdge;          
            }
        }else{
            printf("\n Memory overflow");
        }
    }else{
        //not valid Vertices
        printf("Invalid Node Vertices %d  %d", V,E);
    }
}
//Display Adjacency list of vertex
void printGraph(struct Graph*node){
    if(node!=NULL){
        struct AjlistNode *temp=NULL;
        for(int index=0;index<size;index++){
            printf("\n Adjacency list of vertex %d  :",index);
            temp=node[index].next;
            while(temp!=NULL){
                //temp->vId is graph node vertices
                //in this case temp->vId is same as 
                //node[temp->vId].data
                
                printf("  %d",node[temp->vId].data);
                temp=temp->next;
            }
        }
    }else{
        printf("Empty Graph");
    }
}
//Breadth First Traversal for a directed graph node
void bfs(int point,struct Graph*node){

    if(point>size||node==NULL) return;

    struct Queue*queue=NULL;
    struct AjlistNode *temp=NULL;

    int *visit=(int*)calloc(size,sizeof(int));

    //Add first element into queue
    enqueue(point,&queue);

    printf("\n BFS :");
    while(queue!=NULL){
       
        temp=node[queue->element].next;
        while(temp!=NULL){

            if(visit[temp->vId]==0){
                visit[temp->vId]=1;
                enqueue(temp->vId,&queue);
            }
            temp=temp->next;
        }
        visit[queue->element]=1;

        printf("  %d",queue->element);

        dequeue(&queue);

    }

}
int main(){
    //Set number of graph node
    size=6;

    struct Graph*node=NULL;
    node=(struct Graph*)malloc(sizeof(struct Graph)*size);
    
    if(node==NULL){
        printf("\n Memory overflow");
    }else{
        //First set node keys
        setData(node); 
        //Connected two node with Edges
        addEdge(node,0,1);
        addEdge(node,0,5);
        addEdge(node,1,1);
        addEdge(node,2,1);
        addEdge(node,3,0);
        addEdge(node,3,3);
        addEdge(node,4,2);
        addEdge(node,4,3);
        addEdge(node,5,1);
        printGraph(node);
  
        bfs(4,node);
    }  
    return 0;
}

Output

 Adjacency list of vertex 0  :  1  5
 Adjacency list of vertex 1  :  1
 Adjacency list of vertex 2  :  1
 Adjacency list of vertex 3  :  0  3
 Adjacency list of vertex 4  :  2  3
 Adjacency list of vertex 5  :  1
 BFS :  4  2  3  1  0  5 

//C++ Program, Breadth First Traversal in Directed graph
#include<iostream>
using namespace std;
struct AjlistNode{
    int vId;//Vertices id
    struct AjlistNode*next;
};
struct Vertices{
    int data; //node key value
    struct AjlistNode*next;
};

struct Queue{
    int element;
    struct Queue*next;
};

class Graph{
  Vertices *node;
  int *visit;
  int size;//number of 
public:
    Graph(int);
    void setData();
    void addEdge(int,int);
    void printGraph();
    void dequeue(Queue**);
    void bfs(int);
    void enqueue(int,Queue**);
};
Graph::Graph(int size){
    this->size=size;
    //set number of nodes
    node=new Vertices[size];
    
    visit=new int[size];

    for(int index=0;index<size;index++){
        visit[index]=0;
    }
}
//set node key value
void Graph:: setData(){
    if(node!=NULL){
        int index=0;
        for(index;index<size;index++){
          //set vertic node data
          node[index].data=index;//set node key
          //Initial no AjlistNode
          //set NULL Value
          node[index].next=NULL;
        }
  }else{
    cout<<"Vertic Node is Empty"<<endl;
  }
}
//Add Queue Element
void Graph :: enqueue(int data,Queue**queue){
    Queue *newNode=new Queue;
    if(newNode!=NULL){
        newNode->element=data;
        newNode->next=NULL;
        if(*queue!=NULL){
            Queue*temp=*queue;
            while(temp->next!=NULL){
                temp=temp->next;
            }
            temp->next=newNode;
        }else{
            *queue=newNode;
        }
    }else{
         cout<<("\n Memory overflow");
    }
}

//remove single element into queue
void Graph :: dequeue(Queue**queue){
    Queue*temp=(*queue);
    (*queue)=temp->next;
    delete temp;
    temp=NULL;
}

//Add Edge from Two given Nodes
void Graph ::addEdge(int V ,int E){
    //add edge form V to E
    //V and E is Node location
    if(V<size && E <size){
      //first create Adjacency node
        AjlistNode *newEdge=new AjlistNode;
        if(newEdge!=NULL){
            
            newEdge->next=NULL;
            newEdge->vId=E;

            AjlistNode *temp=node[V].next;

            if(temp==NULL){
                node[V].next=newEdge;
            }else{
                //Add node at last
                while(temp->next!=NULL){
                    temp=temp->next;
                }      
                temp->next=newEdge;          
            }
        }
    }else{
        //not valid Vertices
        cout<<"Invalid Node Vertices "<< V<<" "<<E;
    }
}
//Display Adjacency list of vertex
void Graph::printGraph(){
    if(node!=NULL){
        AjlistNode *temp=NULL;
        for(int index=0;index<size;index++){
            cout<<"\n Adjacency list of vertex "<<index<<" :";
            temp=node[index].next;
            while(temp!=NULL){
                //temp->vId is graph node vertices
                //in this case temp->vId is same as 
                //node[temp->vId].data
                
                cout<<" "<<node[temp->vId].data;
                temp=temp->next;
            }
        }
    }else{
        cout<<"Empty Graph"<<endl;
    }
}
//Breadth First Traversal for a directed graph node
void Graph:: bfs(int point){

    if(point>size||node==NULL) return;

    Queue*queue=NULL;
    AjlistNode *temp=NULL;

    int visit[size]={0};//set zero to each element

    //Add first element into queue
    enqueue(point,&queue);

    cout<<"\n BFS :";
    while(queue!=NULL){
       
        temp=node[queue->element].next;
        while(temp!=NULL){

            if(visit[temp->vId]==0){
                visit[temp->vId]=1;
                enqueue(temp->vId,&queue);
            }
            temp=temp->next;
        }
        visit[queue->element]=1;

       cout<<"  "<<queue->element;

        dequeue(&queue);

    }

}
int main(){
    //Create Object
    Graph g(6);
    //First set node keys
    g.setData(); 

    //Connected two node with Edges
    g.addEdge(0,1);
    g.addEdge(0,5);
    g.addEdge(1,1);
    g.addEdge(2,1);
    g.addEdge(3,0);
    g.addEdge(3,3);
    g.addEdge(4,2);
    g.addEdge(4,3);
    g.addEdge(5,1);
    g.printGraph();
    g.bfs(4); //start node 4
    return 0;
}

Output

 Adjacency list of vertex 0 : 1 5
 Adjacency list of vertex 1 : 1
 Adjacency list of vertex 2 : 1
 Adjacency list of vertex 3 : 0 3
 Adjacency list of vertex 4 : 2 3
 Adjacency list of vertex 5 : 1
 BFS :  4  2  3  1  0  5
//Java Breadth First Traversal in Directed graph
public class MyGraph
{

    static class AjlistNode
    {
        int id;//Vertices node key
        AjlistNode next;
    }
    static class Vertices
    {
        int data;
        AjlistNode next;
    }
    static class Queue{
        int element;
        Queue next;
    }

    //number of Vertices
    static int size;
    public Vertices node[];
    public Queue queue;
    MyGraph(int size)
    {
        //set value
        this.size=size;
        queue=null;
        node=new Vertices[size];
        
    }

    //set initial node value
    public void setData(){
        if(node==null)
        {
            System.out.println("\nEmpty Graph");
        }else
        {
            for(int index=0;index<size;index++)
            {
                // avoid java.lang.nullPointerException
                node[index]=new Vertices(); 
                node[index].data=index;//set your data
                node[index].next=null;
            }
        }
    }

    public void addEdge(int S,int E){
        if(S<size && E<size && node!=null)
        {
            AjlistNode newEdge=new AjlistNode();
            newEdge.id=E;//end node
            newEdge.next=null;
            if(node[S].next==null)
            {
                node[S].next=newEdge;
            }else
            {
                AjlistNode temp=node[S].next;
                while(temp.next!=null)
                {
                    temp=temp.next;
                }
                temp.next=newEdge;
            }

        }else{
            System.out.println("\nEmpty Graph");
        }
    }
    public void enqueue(int data)
    {
        Queue newNode=new Queue();
        if(newNode!=null)
        {
            newNode.element=data;
            newNode.next=null;
            if( queue!=null)
            {
                Queue temp=queue;
                while(temp.next!=null)
                {
                    temp=temp.next;
                }
                temp.next=newNode;
            }else
            {
                queue=newNode;
            }
        }
        else
        {
            System.out.println("\n Memory overflow");
        }
    }
    public void dequeue()
    {   
        if(queue!=null)
        {
            Queue temp=(queue);
            queue=temp.next;
            temp=null;
        }
    }
    //Breadth First Traversal for a directed graph node
    public void  bfs(int point){

        if(point>size||node==null) return;

        queue=null;
        AjlistNode  temp=null;

        //set zero to each element
        int []visit=new int[size];

        //Add first element into queue
        enqueue(point);

        System.out.print("\n BFS :");
        while(queue!=null){

            temp=node[queue.element].next;
            while(temp!=null){

                if(visit[temp.id]==0){
                    visit[temp.id]=1;
                    enqueue(temp.id);
                }
                temp=temp.next;
            }
            visit[queue.element]=1;

            System.out.print("  "+queue.element);

            dequeue();

        }

    }

    public void printGraph()
    {
        if(size>0&&node!=null)
        {
            for(int index=0;index<size;index++)
            {
                System.out.print("\nAdjacency list of vertex "+index+" :");
                AjlistNode temp=node[index].next;
                while(temp!=null)
                {
                    System.out.print(" "+node[temp.id].data);
                    temp=temp.next;
                }
            }
        }
    }

    public static void main(String[] args) {
        int totalNode=6;

        MyGraph g=new MyGraph(totalNode);
        g.setData();
        //Connected two node with Edges
        g.addEdge(0,1);
        g.addEdge(0,5);
        g.addEdge(1,1);
        g.addEdge(2,1);
        g.addEdge(3,0);
        g.addEdge(3,3);
        g.addEdge(4,2);
        g.addEdge(4,3);
        g.addEdge(5,1);

        g.printGraph();
       
        g.bfs(4);

    }
}

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 1
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 3
Adjacency list of vertex 4 : 2 3
Adjacency list of vertex 5 : 1
 BFS :  4  2  3  1  0  5
#Python Breadth First Traversal in Directed graph
class AjLinkeNode:
  def __init__(self,data):
    self.id=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Queue:
  def __init__(self,data):
    self.element=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[]


  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1

  def addEdge(self,S,E):
    #S and E is two nodes
    if(self.size>S and self.size>E):
      new_edge=AjLinkeNode(E)
      if(self.node[S].next==None):
        self.node[S].next=new_edge
      else:
        temp=self.node[S].next
        while(temp.next!=None):
          temp=temp.next
        temp.next=new_edge
    else:
      print("Invalid nodes")

  def printGraph(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        print("\nAdjacency list of vertex ",index,end=" : ")
        temp=self.node[index].next
        while temp!=None:
          print(temp.id,end=" ")
          temp=temp.next
        index+=1

  def enqueue(self,data):
      newNode = Queue(data)
      if(newNode!=None):
          if(self.queue!=None):
              temp=self.queue
              while(temp.next!=None):
                  temp=temp.next
              
              temp.next=newNode
          else:
              self.queue=newNode
          
      
      else:
          println("\n Memory overflow")
        
  
  def dequeue(self):   
      if(self.queue!=None):
          temp=(self.queue)
          self.queue=temp.next
          temp=None
        
    
  #Breadth First Traversal for a directed graph node
  def  bfs(self,point):

      if(point>self.size or self.node==None):
        return
      self.queue=None
      temp=None

      #set zero to each element
      visit=[0]*self.size

      #Add first element into queue
      self.enqueue(point)

      print("\n BFS :",end=" ")
      while(self.queue!=None):

          temp=self.node[self.queue.element].next
          while(temp!=None):

              if(visit[temp.id]==0):
                  visit[temp.id]=1
                  self.enqueue(temp.id)
              
              temp=temp.next
          
          visit[self.queue.element]=1

          print(self.queue.element,end=" ")

          self.dequeue()

def main():
  g=Graph(6)
  g.setData() 
  #Connected two node with Edges
  g.addEdge(0,1)
  g.addEdge(0,5)
  g.addEdge(1,1)
  g.addEdge(2,1)
  g.addEdge(3,0)
  g.addEdge(3,3)
  g.addEdge(4,2)
  g.addEdge(4,3)
  g.addEdge(5,1)
  g.printGraph()
 
  g.bfs(4)

if __name__=="__main__":
    main()

Output

Adjacency list of vertex  0 : 1 5 
Adjacency list of vertex  1 : 1 
Adjacency list of vertex  2 : 1 
Adjacency list of vertex  3 : 0 3 
Adjacency list of vertex  4 : 2 3 
Adjacency list of vertex  5 : 1 
 BFS : 4 2 3 1 0 5
//C# Breadth First Traversal in Directed graph
using System;
class AjlistNode{
    public int key;
    public AjlistNode next;
    public AjlistNode(int key){
        this.key=key;
        this.next=null;
    }
}
class Node{
    public int data;
    public AjlistNode next;

    public Node(int data){
        this.data=data;
        this.next=null;


    }
}
class Queue{
    public int element;
    public Queue next;
}
class MyGraph{
    //empty array
    public Node[]node= new Node[] {};
    public int size;
    public Queue queue;
    public MyGraph(int size){
        this.size=size;
        node=new Node[size];
        this.queue = null;

    }
    public void setData(){
        if(size>0 && this.node!=null){
            for(int index=0;index<size;index++){
                node[index]=new Node(index);
            }

        }
    }
    public void addEdge(int start,int end){
        if(this.size>start && this.size>end){
            AjlistNode newEdge=new AjlistNode(end);

            if(node[start].next==null){
                node[start].next=newEdge;
            }else{
                AjlistNode temp=node[start].next;
                while(temp.next!=null){
                    temp=temp.next;
                }
                temp.next=newEdge;
            }

        }
    }
    public void printGraph(){
        if(size>0 && node.Length>0 && node!=null){
            for(int index=0;index<size;index++){
                Console.Write("\nAdjacency list of vertex {0} :",index);
                AjlistNode temp=node[index].next;
                while(temp!=null){
                    Console.Write(" {0}",node[temp.key].data);
                    temp=temp.next;
                }
            }
        }
    }
    public void enqueue(int data)
    {
        Queue newNode=new Queue();
        if(newNode!=null)
        {
            newNode.element=data;
            newNode.next=null;
            if(this.queue!=null)
            {
                Queue temp=queue;
                while(temp.next!=null)
                {
                    temp=temp.next;
                }
                temp.next=newNode;
            }else
            {
                queue=newNode;
            }
        }
        else
        {
            Console.WriteLine("\n Memory overflow");
        }
    }
    public void dequeue()
    {   
        if(queue!=null)
        {
            Queue temp=(queue);
            queue=temp.next;
            temp=null;
        }
    }
    //Breadth First Traversal for a directed graph node
    public void  bfs(int point){

        if(point>size||node==null) return;

        queue=null;
        AjlistNode  temp=null;

        //set zero to each element
        int []visit=new int[this.size];

        //Add first element into queue
        enqueue(point);

        Console.Write("\n BFS :");
        while(queue!=null){

            temp=node[queue.element].next;
            while(temp!=null){

                if(visit[temp.key]==0){
                    visit[temp.key]=1;
                    enqueue(temp.key);
                }
                temp=temp.next;
            }
            visit[queue.element]=1;

            Console.Write("  {0}",queue.element);

            dequeue();

        }

    }


}
class Program{

    static void Main(string[] args){
        //create object
        MyGraph g=new MyGraph(6);
        g.setData();
        //Connected two node with Edges
        g.addEdge(0,1);
        g.addEdge(0,5);
        g.addEdge(1,1);
        g.addEdge(2,1);
        g.addEdge(3,0);
        g.addEdge(3,3);
        g.addEdge(4,2);
        g.addEdge(4,3);
        g.addEdge(5,1);

        g.printGraph();
        g.bfs(4);
    }
}

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 1
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 3
Adjacency list of vertex 4 : 2 3
Adjacency list of vertex 5 : 1
 BFS :  4  2  3  1  0  5

<?php 
/*
* PHP Breadth First Traversal in Directed graph
*/

class AjlistNode{
  public $key;
  public $next;
  function __construct($key)
  {
    $this->key=$key;
    $this->next=NULL;
  }
}
class Node{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data=$data;
    $this->next=NULL;
  }
}
class Queue{
  public $element;
  public $next;
  function __construct($data)
  {
    $this->element=$data;
    $this->next=NULL;
  }
}
class MyGraph{
 
  public $node;
  public $size;
  public $queue;
  function __construct($size){
    $this->size=$size;
    $this->node=[];  //empty array
    $this->queue=NULL;
   
  }
  public function setData(){
    if($this->size>0){
      for($index=0;$index<$this->size;$index++){
        $this->node[$index]=new Node($index);
      }
      
    }
  }
  public function addEdge($start,$end){
    if($this->size > $start && $this->size>$end){
      $newEdge=new AjlistNode($end);
      if($this->node[$start]->next==NULL){
        $this->node[$start]->next=$newEdge;
      }else{

        $temp=$this->node[$start]->next;
        while($temp->next!=NULL){
         $temp=$temp->next;
        }
        $temp->next= $newEdge;
      }
    }
  }
  public function printGraph(){
    if($this->size>0 && count($this->node)>0 && $this->node!=NULL){
      for($index=0;$index<$this->size;$index++){
       echo ("<br>Adjacency list of vertex ".$index." : ");
        $temp=$this->node[$index]->next;
        while($temp!=NULL){
         echo (" ".$this->node[$temp->key]->data);
          $temp=$temp->next;
        }
      }
    }
  }
 public function enqueue($data)
    {
        $newNode=new Queue($data);
        if($newNode!=NULL)
        {
            if( $this->queue!=NULL)
            {
                $temp=$this->queue;
                while($temp->next!=NULL)
                {
                    $temp=$temp->next;
                }
                $temp->next=$newNode;
            }else
            {
                $this->queue=$newNode;
            }
        }
        else
        {
            echo("\n Memory overflow");
        }
    }
    public function dequeue()
    {   
        if($this->queue!=NULL)
        {
            $temp=$this->queue;
            $this->queue=$temp->next;
            $temp=NULL;
        }
    }
    //Breadth First Traversal for a directed graph node
    public function  bfs($point)
    {

        if($point>$this->size||$this->node==NULL)
        {
          return;
        } 
        $this->queue=NULL;
        $temp=NULL;

        //set zero to each element
         $visit=array_fill(0, $this->size, 0);

        //Add first element into queue
        $this->enqueue($point);

        echo ("<br> BFS :");
        
       
        while($this->queue!=NULL)
        {
            $point=$this->queue->element;
           

            $temp=$this->node[$point]->next;

            while($temp!=NULL)
            {

                if($visit[$temp->key]==0)
                {
                    $visit[$temp->key]=1;
                    $this->enqueue($temp->key);
                }
                $temp=$temp->next;
            }
            $visit[$this->queue->element]=1;

            echo("  ".$this->queue->element);

            $this->dequeue();

        }

    }


}


function main(){
  //create object
  $g=new MyGraph(6);
  $g->setData();
  
  //Connected two node with Edges
  $g->addEdge(0,1);
  $g->addEdge(0,5);
  $g->addEdge(1,1);
  $g->addEdge(2,1);
  $g->addEdge(3,0);
  $g->addEdge(3,3);
  $g->addEdge(4,2);
  $g->addEdge(4,3);
  $g->addEdge(5,1);
  $g->printGraph();

  $g->bfs(4);
 
}
main();
?>

Output

Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 : 1
Adjacency list of vertex 2 : 1
Adjacency list of vertex 3 : 0 3
Adjacency list of vertex 4 : 2 3
Adjacency list of vertex 5 : 1
BFS : 4 2 3 1 0 5


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment




© 2021, kalkicode.com, All rights reserved