DFS for disconnected graph

Here given code implementation process.

//C Program
//DFS for disconnected 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;
};



int size; //number of nodes

//set node key value
void set_data(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 Edge from Two given Nodes
void add_edge(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 print_graph(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");
  }
}


//Perform dfs traversal by given node
void dfs(int start, int *visit, struct Graph *node) {

  if (start > size || start < 0 || node == NULL) {
    //invalid input
    return;
  }
  if (visit[start] == 1) {
    return;
  }
  visit[start] = 1;
  printf("%3d", start);
  struct AjlistNode *temp = node[start].next;
  while (temp != NULL) {
    dfs(temp->vId, visit, node);
    temp = temp->next;
  }
}


void view_dfs(struct Graph *node) {
  if (node != NULL) {
    //Auxiliary space which is used to store visited path information

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


    for (int i = 0; i < size; ++i) {
      if (visit[i] == 0) {
        dfs(i, visit, node);
      }
    }

  }
}

int main() {

  size = 7;

  struct Graph *node = NULL;

  node = (struct Graph *) malloc(sizeof(struct Graph) *size);

  if (node == NULL) {
    printf("\n Memory overflow");
  } else {
    //First set node keys
    set_data(node);



    //Connected two node with Edges
    add_edge(node, 1, 0);
    add_edge(node, 1, 4);
    add_edge(node, 1, 6);
    add_edge(node, 2, 0);
    add_edge(node, 2, 5);
    add_edge(node, 3, 5);
    add_edge(node, 6, 1);

    print_graph(node);
    printf("\n DFS : ");
    view_dfs(node);
  }
  return 0;
}

Output

 Adjacency list of vertex 0  :
 Adjacency list of vertex 1  :  0  4  6
 Adjacency list of vertex 2  :  0  5
 Adjacency list of vertex 3  :  5
 Adjacency list of vertex 4  :
 Adjacency list of vertex 5  :
 Adjacency list of vertex 6  :  1
 DFS :   0  1  4  6  2  5  3
// C++ program
// DFS for disconnected graph
#include<iostream>

using namespace std;
class AjlistNode {
  public:

  //Vertices node key
  int id;
  AjlistNode *next;
  AjlistNode(int id) {
    //Set value of node key
    this->id = id;
    this->next = NULL;
  }
};
class Vertices {
  public:
  int data;
  AjlistNode *next;
    Vertices()
    {
      this->data = 0;
      this->next = NULL;
    }
  Vertices(int data) {
    this->data = data;
    this->next = NULL;
  }
};
class MyGraph {
  public:

  //number of Vertices
  int size;
  Vertices *node;
  MyGraph(int size) {
    this->size = size;
    this->node = new Vertices[size];
    //set initial values of graph node
    this->set_data();
  }
  //Set initial node value
  void set_data() {
    if (this->node == NULL) {
      cout << "\nEmpty Graph";
    } else {
      int index = 0;
      while (index < this->size) {
        this->node[index] = index;
        index++;
      }
    }
  }
  //Connect two node
  void add_edge(int start, int last) {
    AjlistNode *newEdge = new AjlistNode(last);
    if (this->node[start].next == NULL) {
      //Include first adjacency list node of location start 
      this->node[start].next = newEdge;
    } else {
      AjlistNode *temp = this->node[start].next;
      //Add new node at the last of edge
      while (temp->next != NULL) {
        temp = temp->next;
      }
      //Add node 
      temp->next = newEdge;
    }
  }
  //Display graph elements
  void print_graph() {
    if (this->size > 0 &&
      this->node != NULL) {
      int index = 0;
      while (index < this->size) {
        cout << "\nAdjacency list of vertex " << index << " : ";
        AjlistNode *temp = this->node[index].next;
        while (temp != NULL) {
          cout << this->node[temp->id].data << " ";
          temp = temp->next;
        }
        index++;
      }
    }
  }
  //Perform dfs traversal by given index
  void dfs(int start, bool visit[]) {
    if (start >= this->size ||
      start < 0 ||
      this->node == NULL) {
      //invalid input

      return;
    }
    if (visit[start] == false) {
      visit[start] = true;
      cout << " " << start;
      AjlistNode *temp = this->node[start].next;
      while (temp != NULL) {
        this->dfs(temp->id, visit);
        temp = temp->next;
      }
    }
  }
  void view_dfs() {
    if (this->node != NULL) {
      bool visit[size];
      for (int index = 0; index < this->size; index++) {
        visit[index] = false;
      }
      for (int i = 0; i < this->size; ++i) {
        if (visit[i] == false) {
          this->dfs(i, visit);
        }
      }
    }
  }
};
int main() {
  MyGraph g =  MyGraph(7);
  //Connected two node with Edges
  g.add_edge(1, 0);
  g.add_edge(1, 4);
  g.add_edge(1, 6);
  g.add_edge(2, 0);
  g.add_edge(2, 5);
  g.add_edge(3, 5);
  g.add_edge(6, 1);
  g.print_graph();
  cout << "\n DFS : ";
  g.view_dfs();
  return 0;
}

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 6
Adjacency list of vertex 2 : 0 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 1
 DFS :  0 1 4 6 2 5 3
// Java program
// DFS for disconnected graph

class AjlistNode {
  //Vertices node key
  public int id; 
  public AjlistNode next;

  public AjlistNode(int id) {
    //Set value of node key
    this.id = id;
    this.next = null;
  }
}
class Vertices {

  public int data;
  public AjlistNode next;

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

public class MyGraph {


  //number of Vertices
  private int size;

  private Vertices[] node;

  public MyGraph(int size) {

    this.size = size;
    this.node = new Vertices[size];
    //set initial values of graph node
    this.set_data();


  }

  //Set initial node value
  public void set_data() {
    if (node == null) {
      System.out.println("\nEmpty Graph");
    } else {

      int index = 0;

      while (index < size) {
  
        node[index] = new Vertices(index);

        index++;
      }
    }
  }


  //Connect two node
  public void add_edge(int start, int last) {
    AjlistNode newEdge = new AjlistNode(last);

    if (node[start].next == null) 
    {
      //Include first adjacency list node of location start 
      node[start].next = newEdge;
    }
    else 
    {
      AjlistNode temp = node[start].next;
      //Add new node at the last of edge
      while (temp.next != null) 
      {
        temp = temp.next;
      }
      //Add node 
      temp.next = newEdge;
    }
  }
  //Display graph elements
  public void print_graph() {

    if (size > 0 && node != null) {
      int index = 0;
      while (index < size) {
        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;
        }
        index++;
      }
    }
  }
  //Perform dfs traversal by given index
  public void dfs(int start,boolean []visit)
  {

    if(start >= size ||start<0 || node==null)
    {
      //invalid input
      return ;
    }
    if(visit[start]==false)
    {
 
      visit[start]=true;
      System.out.print(" "+start);
      AjlistNode temp=node[start].next;
      while(temp!=null)
      {
        dfs(temp.id,visit); 
        temp=temp.next;
      }
    }
  }


  public void view_dfs()
  {
    if(node!=null)
    {
      //Auxiliary space which is used to store visited path information
      boolean []visit= new boolean[size];

      for (int index=0; index<size ;index++ ) {
          
          visit[index] = false;
      }

      

      for (int i = 0; i < size; ++i)
      {
        if(visit[i]==false)
        {
          dfs(i,visit);
        }
      }

    }
  }


  public static void main(String[] args) {


    MyGraph g = new MyGraph(7);
    //Connected two node with Edges
    g.add_edge(1, 0); 
    g.add_edge(1, 4); 
    g.add_edge(1, 6); 
    g.add_edge(2, 0); 
    g.add_edge(2, 5); 
    g.add_edge(3, 5); 
    g.add_edge(6, 1);
    
    g.print_graph();
    System.out.print("\n DFS : ");
    g.view_dfs();
  }
}

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 6
Adjacency list of vertex 2 : 0 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 1
 DFS :  0 1 4 6 2 5 3
// C# program
// DFS for disconnected graph
using System;
class AjlistNode {
  //Vertices node key
  public int id;
  public AjlistNode next;
  public AjlistNode(int id) {
    //Set value of node key
    this.id = id;
    this.next = null;
  }
}
class Vertices {
  public int data;
  public AjlistNode next;
  public Vertices(int data) {
    this.data = data;
    this.next = null;
  }
}
public class MyGraph {
  //number of Vertices
  private int size;
  private Vertices[] node;
  public MyGraph(int size) {
    this.size = size;
    this.node = new Vertices[size];
    this.set_data();
  }
  //Set initial node value
  public void set_data() {
    if (node == null) {
      Console.WriteLine("\nEmpty Graph");
    } else {
      int index = 0;
      while (index < size) {
        node[index] = new Vertices(index);
        index++;
      }
    }
  }
  //Connect two node
  public void add_edge(int start, int last) {
    AjlistNode newEdge = new AjlistNode(last);
    if (node[start].next == null) {
      //Include first adjacency list node of location start 
      node[start].next = newEdge;
    } else {
      AjlistNode temp = node[start].next;
      //Add new node at the last of edge
      while (temp.next != null) {
        temp = temp.next;
      }
      //Add node 
      temp.next = newEdge;
    }
  }
  //Display graph elements
  public void print_graph() {
    if (size > 0 &&
      node != null) {
      int index = 0;
      while (index < size) {
        Console.Write("\nAdjacency list of vertex " + index + " : ");
        AjlistNode temp = node[index].next;
        while (temp != null) {
          Console.Write(node[temp.id].data + " ");
          temp = temp.next;
        }
        index++;
      }
    }
  }
  //Perform dfs traversal by given index
  public void dfs(int start, Boolean[] visit) {
    if (start >= size ||
      start < 0 ||
      node == null) {
      return;
    }
    if (visit[start] == false) {
      visit[start] = true;
      Console.Write(" " + start);
      AjlistNode temp = node[start].next;
      while (temp != null) {
        dfs(temp.id, visit);
        temp = temp.next;
      }
    }
  }
  public void view_dfs() {
    if (node != null) {
      Boolean[]
      //Auxiliary space which is used to store visited path information
      visit = new Boolean[size];
      for (int index = 0; index < size; index++) {
        visit[index] = false;
      }
      for (int i = 0; i < size; ++i) {
        if (visit[i] == false) {
          dfs(i, visit);
        }
      }
    }
  }
  public static void Main(String[] args) {
    MyGraph g = new MyGraph(7);
    g.add_edge(1, 0);
    g.add_edge(1, 4);
    g.add_edge(1, 6);
    g.add_edge(2, 0);
    g.add_edge(2, 5);
    g.add_edge(3, 5);
    g.add_edge(6, 1);
    g.print_graph();
    Console.Write("\n DFS : ");
    g.view_dfs();
  }
}

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 6
Adjacency list of vertex 2 : 0 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 1
 DFS :  0 1 4 6 2 5 3
<?php
// Php program
// DFS for disconnected graph
class AjlistNode {
  //Vertices node key

  public $id;
  public $next;

  function __construct($id) {
    //Set value of node key
    $this->id = $id;
    $this->next = null;
  }
}
class Vertices {
  public $data;
  public $next;

  function __construct($data) {
    $this->data = $data;
    $this->next = null;
  }
}
class MyGraph {
  //number of Vertices

  private $size;
  private $node;

  function __construct($size) {
    $this->size = $size;
    $this->node = array_fill(0, $size, null);
    //set initial values of graph node
    $this->set_data();
  }
  //Set initial node value

  public  function set_data() {
    if ($this->node == null) {
      echo("\nEmpty Graph");
    } else {
      $index = 0;
      while ($index < $this->size) {
        $this->node[$index] = new Vertices($index);
        $index++;
      }
    }
  }
  //Connect two node

  public  function add_edge($start, $last) {
    $newEdge = new AjlistNode($last);
    if ($this->node[$start]->next == null) {
      //Include first adjacency list node of location start 
      $this->node[$start]->next = $newEdge;
    } else {
      $temp = $this->node[$start]->next;
      //Add new node at the last of edge
      while ($temp->next != null) {
        $temp = $temp->next;
      }
      //Add node 
      $temp->next = $newEdge;
    }
  }
  //Display graph elements

  public  function print_graph() {
    if ($this->size > 0 &&
      $this->node != null) {
      $index = 0;
      while ($index < $this->size) {
        echo("\nAdjacency list of vertex ". $index ." : ");
        $temp = $this->node[$index]->next;
        while ($temp != null) {
          echo($this->node[$temp->id]->data ." ");
          $temp = $temp->next;
        }
        $index++;
      }
    }
  }
  //Perform dfs traversal by given index

  public  function dfs($start, & $visit) {
    if ($start >= $this->size ||
      $start < 0 ||
      $this->node == null) {
      return;
    }
    if ($visit[$start] == false) {
      $visit[$start] = true;
      echo(" ". $start);
      $temp = $this->node[$start]->next;
      while ($temp != null) {
        $this->dfs($temp->id, $visit);
        $temp = $temp->next;
      }
    }
  }
  public  function view_dfs() {
    if ($this->node != null) {
      //Auxiliary space which is used to store visited path information
      $visit = array_fill(0, $this->size, false);
      for ($index = 0; $index < $this->size; $index++) {
        $visit[$index] = false;
      }
      for ($i = 0; $i < $this->size; ++$i) {
        if ($visit[$i] == false) {
          $this->dfs($i, $visit);
        }
      }
    }
  }
}

function main() {
  $g = new MyGraph(7);
  //Connected two node with Edges
  $g->add_edge(1, 0);
  $g->add_edge(1, 4);
  $g->add_edge(1, 6);
  $g->add_edge(2, 0);
  $g->add_edge(2, 5);
  $g->add_edge(3, 5);
  $g->add_edge(6, 1);
  $g->print_graph();
  echo("\n DFS : ");
  $g->view_dfs();

}
main();

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 6
Adjacency list of vertex 2 : 0 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 1
 DFS :  0 1 4 6 2 5 3
// Node Js program
// DFS for disconnected graph
class AjlistNode {
  //Vertices node key

  constructor(id) {
    //Set value of node key
    this.id = id;
    this.next = null;
  }
}
class Vertices {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class MyGraph {
  //number of Vertices

  constructor(size) {
    this.size = size;
    this.node = Array(size).fill(null);
    //set initial values of graph node
    this.set_data();
  }

  //Set initial node value
  set_data() {
    if (this.node == null) {
      process.stdout.write("\nEmpty Graph");
    } else {
      var index = 0;
      while (index < this.size) {
        this.node[index] = new Vertices(index);
        index++;
      }
    }
  }

  //Connect two node
  add_edge(start, last) {
    var newEdge = new AjlistNode(last);
    if (this.node[start].next == null) {
      //Include first adjacency list node of location start 
      this.node[start].next = newEdge;
    } else {
      var temp = this.node[start].next;
      //Add new node at the last of edge
      while (temp.next != null) {
        temp = temp.next;
      }

      //Add node 
      temp.next = newEdge;
    }
  }

  //Display graph elements
  print_graph() {
    if (this.size > 0 &&
      this.node != null) {
      var index = 0;
      while (index < this.size) {
        process.stdout.write("\nAdjacency list of vertex " + index + " : ");
        var temp = this.node[index].next;
        while (temp != null) {
          process.stdout.write(this.node[temp.id].data + " ");
          temp = temp.next;
        }
        index++;
      }
    }
  }

  //Perform dfs traversal by given index
  dfs(start, visit) {
    if (start >= this.size ||
      start < 0 ||
      this.node == null) {
      return;
    }

    if (visit[start] == false) {
      visit[start] = true;
      process.stdout.write(" " + start);
      var temp = this.node[start].next;
      while (temp != null) {
        this.dfs(temp.id, visit);
        temp = temp.next;
      }
    }
  }
  view_dfs() {
    if (this.node != null) {
      //Auxiliary space which is used to store visited path information
      var visit = Array(this.size).fill(false);
      for (var index = 0; index < this.size; index++) {
        visit[index] = false;
      }

      for (var i = 0; i < this.size; ++i) {
        if (visit[i] == false) {
          this.dfs(i, visit);
        }
      }
    }
  }
}

function main(args) {
  var g = new MyGraph(7);
  //Connected two node with Edges
  g.add_edge(1, 0);
  g.add_edge(1, 4);
  g.add_edge(1, 6);
  g.add_edge(2, 0);
  g.add_edge(2, 5);
  g.add_edge(3, 5);
  g.add_edge(6, 1);
  g.print_graph();
  process.stdout.write("\n DFS : ");
  g.view_dfs();
}

main();

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 6
Adjacency list of vertex 2 : 0 5
Adjacency list of vertex 3 : 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 1
 DFS :  0 1 4 6 2 5 3
#  Python 3 program
#  DFS for disconnected graph
class AjlistNode :

  def __init__(self, id) :
    # Set value of node key
    self.id = id
    self.next = None
  

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

class MyGraph :
  
  def __init__(self, size) :
    self.size = size
    self.node = [None] * size
    # set initial values of graph node
    self.set_data()
  
  # Set initial node value
  def set_data(self) :
    if (self.node == None) :
      print("\nEmpty Graph", end = "")
    else :
      index = 0
      while (index < self.size) :
        self.node[index] = Vertices(index)
        index += 1
      
    
  
  # Connect two node
  def add_edge(self, start, last) :
    newEdge = AjlistNode(last)
    if (self.node[start].next == None) :
      # Include first adjacency list node of location start 
      self.node[start].next = newEdge
    else :
      temp = self.node[start].next
      # Add new node at the last of edge
      while (temp.next != None) :
        temp = temp.next
      
      # Add node 
      temp.next = newEdge
    
  
  # Display graph elements
  def print_graph(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(self.node[temp.id].data ," ", end = "")
          temp = temp.next
        
        index += 1
      
    
  
  # Perform dfs traversal by given index
  def dfs(self, start, visit) :
    if (start >= self.size or start < 0 or self.node == None) :
      return
    
    if (visit[start] == False) :
      visit[start] = True
      print(" ", start, end = "")
      temp = self.node[start].next
      while (temp != None) :
        self.dfs(temp.id, visit)
        temp = temp.next
      
    
  
  def view_dfs(self) :
    if (self.node != None) :
      # Auxiliary space which is used to store visited path information
      visit = [False] * self.size
      index = 0
      while (index < self.size) :
        visit[index] = False
        index += 1
      
      index = 0
      while (index < self.size) :
        if (visit[index] == False) :
          self.dfs(index, visit)
        
        index += 1
      
    
  

def main() :
  g = MyGraph(7)
  # Connected two node with Edges
  g.add_edge(1, 0)
  g.add_edge(1, 4)
  g.add_edge(1, 6)
  g.add_edge(2, 0)
  g.add_edge(2, 5)
  g.add_edge(3, 5)
  g.add_edge(6, 1)
  g.print_graph()
  print("\n DFS : ", end = "")
  g.view_dfs()


if __name__ == "__main__":
  main()

Output

Adjacency list of vertex  0  :
Adjacency list of vertex  1  : 0  4  6
Adjacency list of vertex  2  : 0  5
Adjacency list of vertex  3  : 5
Adjacency list of vertex  4  :
Adjacency list of vertex  5  :
Adjacency list of vertex  6  : 1
 DFS :   0  1  4  6  2  5  3
#  Ruby program
#  DFS for disconnected graph
class AjlistNode
    # Define the accessor and reader of class AjlistNode
    attr_reader :id, :next
    attr_accessor :id, :next 

  
  def initialize(id) 
     # Set value of node key
    self.id = id
    self.next = nil
  end
end
class Vertices
    # Define the accessor and reader of class Vertices
    attr_reader :data, :next
    attr_accessor :data, :next 
  
  def initialize(data) 
    self.data = data
    self.next = nil
  end
end
class MyGraph
    # Define the accessor and reader of class MyGraph
    attr_reader :size, :node
    attr_accessor :size, :node 
  
  
  def initialize(size) 
    self.size = size
    self.node = Array.new(size) {nil}
     # set initial values of graph node
    self.set_data()
  end
   # Set initial node value
  def set_data() 
    if (@node == nil) 
      print("\nEmpty Graph")
    else 
      index = 0
      while (index < @size) 
        @node[index] = Vertices.new(index)
        index += 1
      end
    end
  end
   # Connect two node
  def add_edge(start, last) 
    newEdge = AjlistNode.new(last)
    if (@node[start].next == nil) 
       # Include first adjacency list node of location start 
      @node[start].next = newEdge
    else 
      temp = @node[start].next
       # Add new node at the last of edge
      while (temp.next != nil) 
        temp = temp.next
      end
       # Add node 
      temp.next = newEdge
    end
  end
   # Display graph elements
  def print_graph() 
    if (@size > 0 &&
      @node != nil) 
      index = 0
      while (index < @size) 
        print("\nAdjacency list of vertex ", index ,"  : ")
        temp = @node[index].next
        while (temp != nil) 
          print(@node[temp.id].data ," ")
          temp = temp.next
        end
        index += 1
      end
    end
  end
   # Perform dfs traversal by given index
  def dfs(start, visit) 
    if (start >= @size ||
      start < 0 ||
      @node == nil) 
      return
    end
    if (visit[start] == false) 
      visit[start] = true
      print(" ", start)
      temp = @node[start].next
      while (temp != nil) 
        self.dfs(temp.id, visit)
        temp = temp.next
      end
    end
  end
  def view_dfs() 
    if (@node != nil) 
       # Auxiliary space which is used to store visited path information
      visit = Array.new(@size) {false}
      index = 0
      while (index < @size) 
        visit[index] = false
        index += 1
      end
      index = 0
      while (index < @size) 
        if (visit[index] == false) 
          self.dfs(index, visit)
        end
        index += 1
      end
    end
  end
end
def main() 
  g = MyGraph.new(7)
   # Connected two node with Edges
  g.add_edge(1, 0)
  g.add_edge(1, 4)
  g.add_edge(1, 6)
  g.add_edge(2, 0)
  g.add_edge(2, 5)
  g.add_edge(3, 5)
  g.add_edge(6, 1)
  g.print_graph()
  print("\n DFS  :")
  g.view_dfs()
end
main()

Output

Adjacency list of vertex 0  : 
Adjacency list of vertex 1  : 0 4 6 
Adjacency list of vertex 2  : 0 5 
Adjacency list of vertex 3  : 5 
Adjacency list of vertex 4  : 
Adjacency list of vertex 5  : 
Adjacency list of vertex 6  : 1 
 DFS  : 0 1 4 6 2 5 3
// Scala program
// DFS for disconnected graph
class AjlistNode(var id: Int,
  var next: AjlistNode) {

  def this(id: Int) {
    //Set value of node value
    this(id,null);
  }
}
class Vertices(var data: Int,
  var next: AjlistNode) {

  def this(data: Int) {
    this(data,null);
  }
}
class MyGraph(var size: Int,
  var node: Array[Vertices]) {

  def this(size: Int) {
    this(size,Array.fill[Vertices](size)(null));

    //set initial values of graph node
    this.set_data();
  }
  //Set initial node value
  def set_data(): Unit = {
    if (this.node == null) {
      print("\nEmpty Graph");
    } else {
      var index: Int = 0;
      while (index < this.size) {
        this.node(index) = new Vertices(index);
        index += 1;
      }
    }
  }
  //Connect two node
  def add_edge(start: Int, last: Int): Unit = {
    var newEdge: AjlistNode = new AjlistNode(last);

    if (this.node(start).next == null) {
      //Include first adjacency list node of location start 
      this.node(start).next = newEdge;
    } else {
      var temp: AjlistNode = this.node(start).next;

      //Add new node at the last of edge
      while (temp.next != null) {
        temp = temp.next;
      }
      //Add node 
      temp.next = newEdge;
    }
  }
  //Display graph elements
  def print_graph(): Unit = {
    if (this.size > 0 &&
      this.node != null) {
      var index: Int = 0;
      while (index < this.size) {
        print("\nAdjacency list of vertex " + index + " : ");
        var temp: AjlistNode = this.node(index).next;
        while (temp != null) {
          print(" "+this.node(temp.id).data );
          temp = temp.next;
        }
        index += 1;
      }
    }
  }
  //Perform dfs traversal by given index
  def dfs(start: Int, visit: Array[Boolean]): Unit = {
    if (start >= this.size ||
      start < 0 ||
      this.node == null) {
      return;
    }
    if (visit(start) == false) {
      visit(start) = true;
      print(" " + start);
      var temp: AjlistNode = this.node(start).next;
      while (temp != null) {
        dfs(temp.id, visit);
        temp = temp.next;
      }
    }
  }
  def view_dfs(): Unit = {
    if (this.node != null) {
      //Auxiliary space which is used to store visited path information
      var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
      var index: Int = 0;
      while (index < this.size) {
        visit(index) = false;
        index += 1;
      }
      index = 0;
      while (index < this.size) {
        if (visit(index) == false) {
          dfs(index, visit);
        }
        index += 1;
      }
    }
  }
}
object Main {
  def main(args: Array[String]): Unit = {
    var g: MyGraph = new MyGraph(7);

    //Connected two node with Edges
    g.add_edge(1, 0);
    g.add_edge(1, 4);
    g.add_edge(1, 6);
    g.add_edge(2, 0);
    g.add_edge(2, 5);
    g.add_edge(3, 5);
    g.add_edge(6, 1);
    g.print_graph();
    print("\n DFS : ");
    g.view_dfs();
  }
}

Output

Adjacency list of vertex 0 :
Adjacency list of vertex 1 :  0 4 6
Adjacency list of vertex 2 :  0 5
Adjacency list of vertex 3 :  5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 :
Adjacency list of vertex 6 :  1
 DFS :  0 1 4 6 2 5 3
// Swift program
// DFS for disconnected graph
class AjlistNode {
  //Vertices node key
  var id: Int;
  var next: AjlistNode? ;
  init(_ id: Int) {
    //Set value of node key
    self.id = id;
    self.next = nil;
  }
}
class Vertices {
  var data: Int;
  var next: AjlistNode? ;
  init(_ data: Int) {
    self.data = data;
    self.next = nil;
  }
}
class MyGraph {
  //number of Vertices
  var size: Int;
  var node: [Vertices]?=[Vertices]();
  init(_ size: Int) {
    self.size = size;
    var i = 0;
    while (i<size) {
          self.node!.append(Vertices(i));
          i+=1;
        }
  }

  //Connect two node
  func add_edge(_ start: Int, _ last: Int) {
    let newEdge: AjlistNode? = AjlistNode(last);
    if (self.node![start].next == nil) {
      //Include first adjacency list node of location start 
      self.node![start].next = newEdge;
    } else {
      var temp: AjlistNode? = self.node![start].next;
      //Add new node at the last of edge
      while (temp!.next != nil) {
        temp = temp!.next;
      }
      //Add node 
      temp!.next = newEdge;
    }
  }
  //Display graph elements
  func print_graph() {
    if (self.size > 0 &&
      self.node != nil) {
      var index: Int = 0;
      while (index < self.size) {
        print("\nAdjacency list of vertex ", index ," : ", terminator: "");
        var temp: AjlistNode? = self.node![index].next;
        while (temp != nil) {
          print(self.node![temp!.id].data ," ", terminator: "");
          temp = temp!.next;
        }
        index += 1;
      }
    }
  }
  //Perform dfs traversal by given index
  func dfs(_ start: Int, _ visit: inout[Bool]) {
    if (start >= self.size ||
      start < 0 ||
      self.node == nil) {
      return;
    }
    if (visit[start] == false) {
      visit[start] = true;
      print(" ", start, terminator: "");
      var temp: AjlistNode? = self.node![start].next;
      while (temp != nil) {
        self.dfs(temp!.id, &visit);
        temp = temp!.next;
      }
    }
  }
  func view_dfs() {
    if (self.node != nil) {
      //Auxiliary space which is used to store visited path information
      var visit: [Bool] = Array(repeating: false, count: self.size);
      var index: Int = 0;
      while (index < self.size) {
        visit[index] = false;
        index += 1;
      }
      index = 0;
      while (index < self.size) {
        if (visit[index] == false) {
          self.dfs(index, &visit);
        }
        index += 1;
      }
    }
  }
}
func main() {
  let g: MyGraph? = MyGraph(7);
  //Connected two node with Edges
  g!.add_edge(1, 0);
  g!.add_edge(1, 4);
  g!.add_edge(1, 6);
  g!.add_edge(2, 0);
  g!.add_edge(2, 5);
  g!.add_edge(3, 5);
  g!.add_edge(6, 1);
  g!.print_graph();
  print("\n DFS : ", terminator: "");
  g!.view_dfs();
}
main();

Output

Adjacency list of vertex  0  :
Adjacency list of vertex  1  : 0  4  6
Adjacency list of vertex  2  : 0  5
Adjacency list of vertex  3  : 5
Adjacency list of vertex  4  :
Adjacency list of vertex  5  :
Adjacency list of vertex  6  : 1
 DFS :   0  1  4  6  2  5  3


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