Skip to main content

Print all Spanning Tree in Graph

Here given code implementation process.

//C Program 
//Print all Spanning Tree in Graph

#include <stdio.h>
#include <stdlib.h>

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

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

struct Stack
{
  int src,des;
  struct Stack*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");
  }
}

void connect_edge(struct Graph*node, int V ,int E)
{

    // create Adjacency node
  struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
    sizeof(struct AjlistNode)
    );
  if(newEdge!=NULL)
  {

    newEdge->next=NULL;
    newEdge->id=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");

  }
}

//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)
  {

    connect_edge(node,V,E);
    if(V==E)
    {
      return;
    }
    connect_edge(node,E,V);

  }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->id is graph node vertices
          //in this case temp->id is same as 
          //node[temp->id].data
          
          printf("  %d",node[temp->id].data);
          temp=temp->next;
        }
      }
  }else
  {
      printf("Empty Graph");
  }
}
void push(struct Stack**root, int src,int des)
{
  struct Stack *element=(struct Stack*)malloc(
  sizeof(struct Stack)
  );

  if(element!=NULL)
  {
    element->src=src;
    element->des=des;
    element->next=*root;
    *root=element;
  }
}
void pop(struct Stack**root)
{
  if(*root==NULL) 
  {
   return; //already empty
  }
  struct Stack *temp=*root;
  *root=temp->next;
  temp->next=NULL;
  free(temp);
  temp=NULL;
}

//Display Path from source to destination
void print_path(struct Stack*temp)
{
  if(temp==NULL)
  {
    return;
  }
  print_path(temp->next);
  if(temp->src!=-1)
  {
    printf(" (%d  %d) ",temp->src ,temp->des );
  }
  
}



void get_path(int start, 
  int source ,
  int quantity,
  int *visit,
  struct Graph*node,
  struct Stack**output,
  int *final)
 {

   if(start >size 
    || quantity >size 
    || start<0 
    || quantity<0 
    || node==NULL)
  {
    //invalid input
    return ;
  }

  if(visit[start]==1)
  {
    //base case
    return;

  }else
  {
    //add element into stack
    push(output,source,start);
  }
  if(size==quantity && final[start]==0)
  {
    printf("\n");
    print_path(*output);
    
  }

  visit[start]=1;

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

  
  while(temp!=NULL)
  {
    get_path(temp->id,start,quantity+1,visit,node,output,final); 
    
    temp=temp->next;
  }
  //remove top element
  pop(output);
  //reset the  value of visited node
  visit[start]=0;

}

void connectivity(int start,
  int source ,
  int quantity,
  int *visit,
  struct AjlistNode *edge,
  struct Stack**output
  )
{
 if(start > size 
    || quantity > size 
    || edge == NULL 
    || visit[start]==1
    )
 {
  return;
 }
 
  visit[start]=1;
  //add element into stack
  push(output,source,edge->id);

  if(size==quantity+1)
  {

    print_path(*output);
    printf("\n");
    
  }
  
  edge = (edge)->next;
  if(edge != NULL)
  {
    connectivity(edge->id,source,quantity+1,visit,edge,output);
  }

  pop(output);
  //reset the  value of visited node
  visit[start]=0;
}
void spanning_tree(struct Graph*node)
{
  if(node!=NULL)
  {

    struct Stack*root=NULL;

    //Some auxiliary space, 
    //which are hold the information about visited node and result
    int *visit=(int*)calloc(size,sizeof(int));
    int *final=(int*)calloc(size,sizeof(int));
    printf("\n Spanning Tree\n Connect edges with node pairs");
    for (int i = 0; i < size; ++i)
    {
      get_path(i,-1,1,visit,node,&root,final);
     
      final[i]=1;
    }
    printf("\n");
    for (int i = 0; i < size; ++i)
    {
       connectivity(i,i,1,visit,node[i].next,&root);
    }
  }
  else
  {
    printf("Empty Graph");
  }
}

int main()
{
    
  size = 5;

  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, 0, 1);
    add_edge(node, 0, 2);
    add_edge(node, 0, 4);
    add_edge(node, 1, 2);
    add_edge(node, 1, 3);
    add_edge(node, 1, 4);
    add_edge(node, 2, 3);
    add_edge(node, 3, 4);
    print_graph(node);


    spanning_tree(node);
  }
  return 0;
}

Output

 Adjacency list of vertex 0  :  1  2  4
 Adjacency list of vertex 1  :  0  2  3  4
 Adjacency list of vertex 2  :  0  1  3
 Adjacency list of vertex 3  :  1  2  4
 Adjacency list of vertex 4  :  0  1  3
 Spanning Tree
 Connect edges with node pairs
 (0  1)  (1  2)  (2  3)  (3  4)
 (0  1)  (1  4)  (4  3)  (3  2)
 (0  2)  (2  1)  (1  3)  (3  4)
 (0  2)  (2  1)  (1  4)  (4  3)
 (0  2)  (2  3)  (3  1)  (1  4)
 (0  2)  (2  3)  (3  4)  (4  1)
 (0  4)  (4  1)  (1  2)  (2  3)
 (0  4)  (4  1)  (1  3)  (3  2)
 (0  4)  (4  3)  (3  1)  (1  2)
 (0  4)  (4  3)  (3  2)  (2  1)
 (1  0)  (0  2)  (2  3)  (3  4)
 (1  0)  (0  4)  (4  3)  (3  2)
 (1  2)  (2  0)  (0  4)  (4  3)
 (1  3)  (3  2)  (2  0)  (0  4)
 (1  3)  (3  4)  (4  0)  (0  2)
 (1  4)  (4  0)  (0  2)  (2  3)
 (2  0)  (0  1)  (1  3)  (3  4)
 (2  0)  (0  1)  (1  4)  (4  3)
 (2  0)  (0  4)  (4  1)  (1  3)
 (2  1)  (1  0)  (0  4)  (4  3)
 (2  3)  (3  1)  (1  0)  (0  4)
 (3  1)  (1  2)  (2  0)  (0  4)
 (3  2)  (2  0)  (0  1)  (1  4)
 (3  2)  (2  1)  (1  0)  (0  4)
 (1  0)  (1  2)  (1  3)  (1  4)
// C++ Program
// Print all Spanning Tree in 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 MyStack {
	public:
	int source;
	int destination;
	MyStack *next;
	MyStack(int source, int destination, MyStack *top) {
		this->source = source;
		this->destination = destination;
		this->next = top;
	}
};
class MyGraph {
	public:

	//Number of Vertices
	int size;
	Vertices *node;
	MyStack *top;
	MyGraph(int size) {
		//set value
		this->size = size;
		this->top = NULL;
		this->node = new Vertices[size];
		this->set_data();
	}
	//Set initial node value
	void set_data() {
		if (this->node == NULL) {
			cout << "\nEmpty Graph";
		} else {
			for (int index = 0; index < this->size; index++) {
				this->node[index] = index;
			}
		}
	}
	//Connect two nodes
	void connect(int start, int last) {
		AjlistNode *new_edge = new AjlistNode(last);
		if (this->node[start].next == NULL) {
			this->node[start].next = new_edge;
		} else {
			AjlistNode *temp = this->node[start].next;
			while (temp->next != NULL) {
				temp = temp->next;
			}
			temp->next = new_edge;
		}
	}
	//Add edge of two nodes
	void add_edge(int start, int last) {
		if (start >= 0 &&
			start < this->size &&
			last >= 0 &&
			last < this->size &&
			this->node != NULL) {
			this->connect(start, last);
			if (start != last) {
				this->connect(last, start);
			}
		} else {
			cout << "\nHere Something Wrong";
		}
	}
	void print_graph() {
		if (this->size > 0 &&
			this->node != NULL) {
			for (int index = 0; index < this->size; index++) {
				cout << "\nAdjacency list of vertex " << index << " :";
				AjlistNode *temp = this->node[index].next;
				while (temp != NULL) {
					cout << " " << this->node[temp->id].data;
					temp = temp->next;
				}
			}
		}
	}
	void push(int source, int destination) {
		MyStack *new_node = new MyStack(source, destination, this->top);
		this->top = new_node;
	}
	void pop() {
		if (this->top != NULL) {
			this->top = this->top->next;
		}
	}
	//Display Path from source to destination
	void print_path(MyStack *temp) {
		if (temp == NULL) {
			return;
		}
		this->print_path(temp->next);
		if (temp->source != -1) {
			cout << " (" << temp->source << " " << temp->destination << ") ";
		}
	}
	void get_path(int start, int source, int quantity, bool visit[], bool status[]) {
		if (start > this->size ||
			quantity > this->size ||
			start < 0 ||
			quantity < 0 ||
			this->node == NULL) {
			//invalid input

			return;
		}
		if (visit[start] == true) {
			//base case

			return;
		} else {
			//add element into stack
			this->push(source, start);
		}
		if (this->size == quantity &&
			status[start] == true) {
			cout << "\n";
			this->print_path(this->top);
		}
		visit[start] = true;
		AjlistNode *temp = this->node[start].next;
		while (temp != NULL) {
			this->get_path(temp->id, start, quantity + 1, visit, status);
			temp = temp->next;
		}
		//remove top element
		this->pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	void connectivity(int start, int source, int quantity, bool visit[], AjlistNode *edge) {
		if (start > this->size ||
			quantity > this->size ||
			edge == NULL ||
			visit[start] == true) {
			return;
		}
		visit[start] = true;
		//add element into stack
		this->push(source, edge->id);
		if (this->size == quantity + 1) {
			this->print_path(this->top);
			cout << "\n";
		}
		edge = edge->next;
		if (edge != NULL) {
			this->connectivity(edge->id, source, quantity + 1, visit, edge);
		}
		this->pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	void spanning_tree() {
		if (this->node != NULL) {
			bool *visit = new bool[size];
			bool *status = new bool[size];
			int i = 0;
			cout << "\n Spanning Tree\n Connect edges with node pairs";
			for (i = 0; i < this->size; i++) {
				status[i] = false;
				visit[i] = false;
			}
			for (i = 0; i < this->size; ++i) {
				this->get_path(i, -1, 1, visit, status);
				status[i] = true;
			}
			cout << "\n";
			for (i = 0; i < this->size; ++i) {
				this->connectivity(i, i, 1, visit, this->node[i].next);
			}
		} else {
			cout << "Empty Graph";
		}
	}
};
int main() {
	//5 implies the number of nodes in graph
	MyGraph g =  MyGraph(5);
	//Connected two node with Edges
	//Two parameter indicates edge between start and last nodes
	g.add_edge(0, 1);
	g.add_edge(0, 2);
	g.add_edge(0, 4);
	g.add_edge(1, 2);
	g.add_edge(1, 3);
	g.add_edge(1, 4);
	g.add_edge(2, 3);
	g.add_edge(3, 4);
	g.print_graph();
	g.spanning_tree();
	return 0;
}

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 0 2 3 4
Adjacency list of vertex 2 : 0 1 3
Adjacency list of vertex 3 : 1 2 4
Adjacency list of vertex 4 : 0 1 3
 Spanning Tree
 Connect edges with node pairs
 (1 2)  (2 3)  (3 4)  (4 0)
 (1 4)  (4 3)  (3 2)  (2 0)
 (2 0)  (0 4)  (4 3)  (3 1)
 (2 1)  (1 3)  (3 4)  (4 0)
 (2 3)  (3 1)  (1 4)  (4 0)
 (2 3)  (3 4)  (4 0)  (0 1)
 (2 3)  (3 4)  (4 1)  (1 0)
 (3 1)  (1 4)  (4 0)  (0 2)
 (3 2)  (2 0)  (0 4)  (4 1)
 (3 2)  (2 1)  (1 4)  (4 0)
 (3 4)  (4 0)  (0 1)  (1 2)
 (3 4)  (4 0)  (0 2)  (2 1)
 (3 4)  (4 1)  (1 0)  (0 2)
 (3 4)  (4 1)  (1 2)  (2 0)
 (4 0)  (0 1)  (1 2)  (2 3)
 (4 0)  (0 1)  (1 3)  (3 2)
 (4 0)  (0 2)  (2 1)  (1 3)
 (4 0)  (0 2)  (2 3)  (3 1)
 (4 1)  (1 0)  (0 2)  (2 3)
 (4 1)  (1 3)  (3 2)  (2 0)
 (4 3)  (3 1)  (1 0)  (0 2)
 (4 3)  (3 1)  (1 2)  (2 0)
 (4 3)  (3 2)  (2 0)  (0 1)
 (4 3)  (3 2)  (2 1)  (1 0)
 (1 0)  (1 2)  (1 3)  (1 4)
// Java Program
// Print all Spanning Tree in 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;
  }
}
class MyStack 
{
  public int source;
  public int destination;
  public MyStack next;
  public MyStack(int source,int destination,MyStack top) 
  {
    this.source = source;
    this.destination = destination;
    this.next = top;
  }
}
public class MyGraph
{

  //Number of Vertices
  public int size;
    
  public Vertices []node;
  
  public MyStack top;

  public MyGraph(int size)
  {
    //set value
    this.size = size;
    this.top = null;
    this.node = new Vertices[size];
    this.set_data();
    
  }

  //Set initial node value
  public void set_data()
  {
    if(node == null)
    {
      System.out.println("\nEmpty Graph");
    }else
    {
      for(int index=0;index<size;index++)
      {

        node[index]=new Vertices(index); 
      }
    }
  }

  //Connect two nodes
  public void connect(int start,int last )
  {
    AjlistNode new_edge=new AjlistNode(last);

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

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=new_edge;
    }
  }
  //Add edge of two nodes
  public void add_edge(int start,int last)
  {
    if(start>=0 && start < size && last >= 0 &&  last < size && node != null)
    {
      connect(start,last);
      if(start!=last)
      {
        connect(last,start);
      }
   
    }else
    {
      System.out.println("\nHere Something Wrong");
    }
  }

  public void print_graph()
  {

    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 void push(int source,int destination)
  {
    MyStack new_node = new MyStack(source,destination,top);

    top = new_node;

  }
  public void pop()
  {
    if(top != null)
    {
      top = top.next;
    }
  }
  //Display Path from source to destination
  public void print_path(MyStack temp) 
  {

    if (temp == null) 
    {
      return;
    }
    print_path(temp.next);
    if (temp.source != -1) 
    {
      System.out.print(" ("+temp.source+"  "+ temp.destination+") ");
    }
  }


  public void get_path(int start, 
    int source ,
    int quantity,
    boolean[]  visit,
    boolean[] status)
   {

     if(start >size 
      || quantity >size 
      || start<0 
      || quantity<0 
      || this.node==null)
    {
      //invalid input
      return ;
    }

    if(visit[start]==true)
    {
      //base case
      return;

    }else
    {
      //add element into stack
      push(source,start);
    }
    if(size==quantity && status[start]==true)
    {
      System.out.print("\n");
      print_path(this.top);
      
    }

    visit[start]=true;

    AjlistNode  temp=node[start].next;

    
    while(temp!=null)
    {
      get_path(temp.id,start,quantity+1,visit,status); 
      
      temp=temp.next;
    }
    //remove top element
    this.pop();
    //reset the  value of visited node
    visit[start]=false;

  }

  public void connectivity(int start,
    int source ,
    int quantity,
    boolean[] visit,
    AjlistNode  edge
    )
  {
   if(start > size 
      || quantity > size 
      || edge == null 
      || visit[start]==true
      )
   {
    return;
   }
   
    visit[start]=true;
    //add element into stack
    this.push(source,edge.id);

    if(size==quantity+1)
    {

      print_path(this.top);
      System.out.print("\n");
      
    }
    
    edge = edge.next;

    if(edge != null)
    {
      connectivity(edge.id,source,quantity+1,visit,edge);
    }

    this.pop();
    //reset the  value of visited node
    visit[start]=false;
  }
  public void spanning_tree()
  {
    if(node!=null)
    {


      //Some auxiliary space, 
      //which are hold the information about visited node and result
      boolean[] visit= new boolean[size];

      boolean[] status= new boolean[size];
      
      int i = 0;
      System.out.print("\n Spanning Tree\n Connect edges with node pairs");
      for ( i=0 ; i<size ; i++) {
          status[i]=false;
          visit[i]=false;
      } 
      
      for ( i = 0; i < size; ++i)
      {
        get_path(i,-1,1,visit,status);
       
        status[i]=true;
      }
      System.out.print("\n");

      for ( i = 0; i < size; ++i)
      {
         connectivity(i,i,1,visit,node[i].next);
      }
    }
    else
    {
      System.out.print("Empty Graph");
    }
  }

  public static void main(String[] args) 
  {

    //5 implies the number of nodes in graph
    MyGraph g=new MyGraph(5);

    //Connected two node with Edges
    //Two parameter indicates edge between start and last nodes
  
    g.add_edge( 0, 1);
    g.add_edge( 0, 2);
    g.add_edge( 0, 4);
    g.add_edge( 1, 2);
    g.add_edge( 1, 3);
    g.add_edge( 1, 4);
    g.add_edge( 2, 3);
    g.add_edge( 3, 4);
    g.print_graph();
    g.spanning_tree();
  }
}

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 0 2 3 4
Adjacency list of vertex 2 : 0 1 3
Adjacency list of vertex 3 : 1 2 4
Adjacency list of vertex 4 : 0 1 3
 Spanning Tree
 Connect edges with node pairs
 (1 2)  (2 3)  (3 4)  (4 0)
 (1 4)  (4 3)  (3 2)  (2 0)
 (2 0)  (0 4)  (4 3)  (3 1)
 (2 1)  (1 3)  (3 4)  (4 0)
 (2 3)  (3 1)  (1 4)  (4 0)
 (2 3)  (3 4)  (4 0)  (0 1)
 (2 3)  (3 4)  (4 1)  (1 0)
 (3 1)  (1 4)  (4 0)  (0 2)
 (3 2)  (2 0)  (0 4)  (4 1)
 (3 2)  (2 1)  (1 4)  (4 0)
 (3 4)  (4 0)  (0 1)  (1 2)
 (3 4)  (4 0)  (0 2)  (2 1)
 (3 4)  (4 1)  (1 0)  (0 2)
 (3 4)  (4 1)  (1 2)  (2 0)
 (4 0)  (0 1)  (1 2)  (2 3)
 (4 0)  (0 1)  (1 3)  (3 2)
 (4 0)  (0 2)  (2 1)  (1 3)
 (4 0)  (0 2)  (2 3)  (3 1)
 (4 1)  (1 0)  (0 2)  (2 3)
 (4 1)  (1 3)  (3 2)  (2 0)
 (4 3)  (3 1)  (1 0)  (0 2)
 (4 3)  (3 1)  (1 2)  (2 0)
 (4 3)  (3 2)  (2 0)  (0 1)
 (4 3)  (3 2)  (2 1)  (1 0)
 (1 0)  (1 2)  (1 3)  (1 4)
// C# Program
// Print all Spanning Tree in Graph
using System;
public 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;
	}
}
public class Vertices {
	public int data;
	public AjlistNode next;
	public Vertices(int data) {
		this.data = data;
		this.next = null;
	}
}
public class MyStack {
	public int source;
	public int destination;
	public MyStack next;
	public MyStack(int source, int destination, MyStack top) {
		this.source = source;
		this.destination = destination;
		this.next = top;
	}
}
public class MyGraph {
	//Number of Vertices
	public int size;
	public Vertices[] node;
	public MyStack top;
	public MyGraph(int size) {
		//set value
		this.size = size;
		this.top = null;
		this.node = new Vertices[size];
		this.set_data();
	}
	//Set initial node value
	public void set_data() {
		if (node == null) {
			Console.WriteLine("\nEmpty Graph");
		} else {
			for (int index = 0; index < size; index++) {
				node[index] = new Vertices(index);
			}
		}
	}
	//Connect two nodes
	public void connect(int start, int last) {
		AjlistNode new_edge = new AjlistNode(last);
		if (node[start].next == null) {
			node[start].next = new_edge;
		} else {
			AjlistNode temp = node[start].next;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = new_edge;
		}
	}
	//Add edge of two nodes
	public void add_edge(int start, int last) {
		if (start >= 0 &&
			start < size &&
			last >= 0 &&
			last < size &&
			node != null) {
			connect(start, last);
			if (start != last) {
				connect(last, start);
			}
		} else {
			Console.WriteLine("\nHere Something Wrong");
		}
	}
	public void print_graph() {
		if (size > 0 &&
			node != null) {
			for (int index = 0; index < size; index++) {
				Console.Write("\nAdjacency list of vertex " + index + " :");
				AjlistNode temp = node[index].next;
				while (temp != null) {
					Console.Write(" " + node[temp.id].data);
					temp = temp.next;
				}
			}
		}
	}
	public void push(int source, int destination) {
		MyStack new_node = new MyStack(source, destination, top);
		top = new_node;
	}
	public void pop() {
		if (top != null) {
			top = top.next;
		}
	}
	//Display Path from source to destination
	public void print_path(MyStack temp) {
		if (temp == null) {
			return;
		}
		print_path(temp.next);
		if (temp.source != -1) {
			Console.Write(" (" + temp.source + " " + temp.destination + ") ");
		}
	}
	public void get_path(int start, int source, int quantity, Boolean[] visit, Boolean[] status) {
		if (start > size ||
			quantity > size ||
			start < 0 ||
			quantity < 0 ||
			this.node == null) {
			return;
		}
		if (visit[start] == true) {
			return;
		} else {
			push(source, start);
		}
		if (size == quantity &&
			status[start] == true) {
			Console.Write("\n");
			print_path(this.top);
		}
		visit[start] = true;
		AjlistNode temp = node[start].next;
		while (temp != null) {
			get_path(temp.id, start, quantity + 1, visit, status);
			temp = temp.next;
		}
		this.pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	public void connectivity(int start, int source, int quantity, Boolean[] visit, AjlistNode edge) {
		if (start > size ||
			quantity > size ||
			edge == null ||
			visit[start] == true) {
			return;
		}
		visit[start] = true;
		this.push(source, edge.id);
		if (size == quantity + 1) {
			print_path(this.top);
			Console.Write("\n");
		}
		edge = edge.next;
		if (edge != null) {
			connectivity(edge.id, source, quantity + 1, visit, edge);
		}
		this.pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	public void spanning_tree() {
		if (node != null) {
			Boolean[]
			//Some auxiliary space, 
			//which are hold the information about visited node and result
			visit = new Boolean[size];
			Boolean[] status = new Boolean[size];
			int i = 0;
			Console.Write("\n Spanning Tree\n Connect edges with node pairs");
			for (i = 0; i < size; i++) {
				status[i] = false;
				visit[i] = false;
			}
			for (i = 0; i < size; ++i) {
				get_path(i, -1, 1, visit, status);
				status[i] = true;
			}
			Console.Write("\n");
			for (i = 0; i < size; ++i) {
				connectivity(i, i, 1, visit, node[i].next);
			}
		} else {
			Console.Write("Empty Graph");
		}
	}
	public static void Main(String[] args) {
		//5 implies the number of nodes in graph
		MyGraph g = new MyGraph(5);
		g.add_edge(0, 1);
		g.add_edge(0, 2);
		g.add_edge(0, 4);
		g.add_edge(1, 2);
		g.add_edge(1, 3);
		g.add_edge(1, 4);
		g.add_edge(2, 3);
		g.add_edge(3, 4);
		g.print_graph();
		g.spanning_tree();
	}
}

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 0 2 3 4
Adjacency list of vertex 2 : 0 1 3
Adjacency list of vertex 3 : 1 2 4
Adjacency list of vertex 4 : 0 1 3
 Spanning Tree
 Connect edges with node pairs
 (1 2)  (2 3)  (3 4)  (4 0)
 (1 4)  (4 3)  (3 2)  (2 0)
 (2 0)  (0 4)  (4 3)  (3 1)
 (2 1)  (1 3)  (3 4)  (4 0)
 (2 3)  (3 1)  (1 4)  (4 0)
 (2 3)  (3 4)  (4 0)  (0 1)
 (2 3)  (3 4)  (4 1)  (1 0)
 (3 1)  (1 4)  (4 0)  (0 2)
 (3 2)  (2 0)  (0 4)  (4 1)
 (3 2)  (2 1)  (1 4)  (4 0)
 (3 4)  (4 0)  (0 1)  (1 2)
 (3 4)  (4 0)  (0 2)  (2 1)
 (3 4)  (4 1)  (1 0)  (0 2)
 (3 4)  (4 1)  (1 2)  (2 0)
 (4 0)  (0 1)  (1 2)  (2 3)
 (4 0)  (0 1)  (1 3)  (3 2)
 (4 0)  (0 2)  (2 1)  (1 3)
 (4 0)  (0 2)  (2 3)  (3 1)
 (4 1)  (1 0)  (0 2)  (2 3)
 (4 1)  (1 3)  (3 2)  (2 0)
 (4 3)  (3 1)  (1 0)  (0 2)
 (4 3)  (3 1)  (1 2)  (2 0)
 (4 3)  (3 2)  (2 0)  (0 1)
 (4 3)  (3 2)  (2 1)  (1 0)
 (1 0)  (1 2)  (1 3)  (1 4)
<?php
// Php Program
// Print all Spanning Tree in 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 MyStack {
	public $source;
	public $destination;
	public $next;

	function __construct($source, $destination, $top) {
		$this->source = $source;
		$this->destination = $destination;
		$this->next = $top;
	}
}
class MyGraph {
	//Number of Vertices

	public $size;
	public $node;
	public $top;

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

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

	public 	function connect($start, $last) {
		$new_edge = new AjlistNode($last);
		if ($this->node[$start]->next == null) {
			$this->node[$start]->next = $new_edge;
		} else {
			$temp = $this->node[$start]->next;
			while ($temp->next != null) {
				$temp = $temp->next;
			}
			$temp->next = $new_edge;
		}
	}
	//Add edge of two nodes

	public 	function add_edge($start, $last) {
		if ($start >= 0 &&
			$start < $this->size &&
			$last >= 0 &&
			$last < $this->size &&
			$this->node != null) {
			$this->connect($start, $last);
			if ($start != $last) {
				$this->connect($last, $start);
			}
		} else {
			echo("\nHere Something Wrong");
		}
	}
	public 	function print_graph() {
		if ($this->size > 0 &&
			$this->node != null) {
			for ($index = 0; $index < $this->size; $index++) {
				echo("\nAdjacency list of vertex ". $index ." :");
				$temp = $this->node[$index]->next;
				while ($temp != null) {
					echo(" ". $this->node[$temp->id]->data);
					$temp = $temp->next;
				}
			}
		}
	}
	public 	function push($source, $destination) {
		$new_node = new MyStack($source, $destination, $this->top);
		$this->top = $new_node;
	}
	public 	function pop() {
		if ($this->top != null) {
			$this->top = $this->top->next;
		}
	}
	//Display Path from source to destination

	public 	function print_path($temp) {
		if ($temp == null) {
			return;
		}
		$this->print_path($temp->next);
		if ($temp->source != -1) {
			echo(" (". $temp->source ." ". $temp->destination .") ");
		}
	}
	public 	function get_path($start, $source, $quantity, & $visit, & $status) {
		if ($start > $this->size ||
			$quantity > $this->size ||
			$start < 0 ||
			$quantity < 0 ||
			$this->node == null) {
			return;
		}
		if ($visit[$start] == true) {
			return;
		} else {
			//add element into stack
			$this->push($source, $start);
		}
		if ($this->size == $quantity &&
			$status[$start] == true) {
			echo("\n");
			$this->print_path($this->top);
		}
		$visit[$start] = true;
		$temp = $this->node[$start]->next;
		while ($temp != null) {
			$this->get_path($temp->id, $start, $quantity + 1, $visit, $status);
			$temp = $temp->next;
		}
		//remove top element
		$this->pop();
		//reset the  value of visited node
		$visit[$start] = false;
	}
	public 	function connectivity($start, $source, $quantity, & $visit, $edge) {
		if ($start > $this->size ||
			$quantity > $this->size ||
			$edge == null ||
			$visit[$start] == true) {
			return;
		}
		$visit[$start] = true;
		//add element into stack
		$this->push($source, $edge->id);
		if ($this->size == $quantity + 1) {
			$this->print_path($this->top);
			echo("\n");
		}
		$edge = $edge->next;
		if ($edge != null) {
			$this->connectivity($edge->id, $source, $quantity + 1, $visit, $edge);
		}
		$this->pop();
		//reset the  value of visited node
		$visit[$start] = false;
	}
	public 	function spanning_tree() {
		if ($this->node != null) {
			//Some auxiliary space, 
			//which are hold the information about visited node and result
			$visit = array_fill(0, $this->size, false);
			$status = array_fill(0, $this->size, false);
			$i = 0;
			echo("\n Spanning Tree\n Connect edges with node pairs");
			for ($i = 0; $i < $this->size; ++$i) {
				$this->get_path($i, -1, 1, $visit, $status);
				$status[$i] = true;
			}
			echo("\n");
			for ($i = 0; $i < $this->size; ++$i) {
				$this->connectivity($i, $i, 1, $visit, $this->node[$i]->next);
			}
		} else {
			echo("Empty Graph");
		}
	}
}

function main() {
	//5 implies the number of nodes in graph
	$g = new MyGraph(5);
	//Connected two node with Edges
	//Two parameter indicates edge between start and last nodes
	$g->add_edge(0, 1);
	$g->add_edge(0, 2);
	$g->add_edge(0, 4);
	$g->add_edge(1, 2);
	$g->add_edge(1, 3);
	$g->add_edge(1, 4);
	$g->add_edge(2, 3);
	$g->add_edge(3, 4);
	$g->print_graph();
	$g->spanning_tree();

}
main();

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 0 2 3 4
Adjacency list of vertex 2 : 0 1 3
Adjacency list of vertex 3 : 1 2 4
Adjacency list of vertex 4 : 0 1 3
 Spanning Tree
 Connect edges with node pairs
 (1 2)  (2 3)  (3 4)  (4 0)
 (1 4)  (4 3)  (3 2)  (2 0)
 (2 0)  (0 4)  (4 3)  (3 1)
 (2 1)  (1 3)  (3 4)  (4 0)
 (2 3)  (3 1)  (1 4)  (4 0)
 (2 3)  (3 4)  (4 0)  (0 1)
 (2 3)  (3 4)  (4 1)  (1 0)
 (3 1)  (1 4)  (4 0)  (0 2)
 (3 2)  (2 0)  (0 4)  (4 1)
 (3 2)  (2 1)  (1 4)  (4 0)
 (3 4)  (4 0)  (0 1)  (1 2)
 (3 4)  (4 0)  (0 2)  (2 1)
 (3 4)  (4 1)  (1 0)  (0 2)
 (3 4)  (4 1)  (1 2)  (2 0)
 (4 0)  (0 1)  (1 2)  (2 3)
 (4 0)  (0 1)  (1 3)  (3 2)
 (4 0)  (0 2)  (2 1)  (1 3)
 (4 0)  (0 2)  (2 3)  (3 1)
 (4 1)  (1 0)  (0 2)  (2 3)
 (4 1)  (1 3)  (3 2)  (2 0)
 (4 3)  (3 1)  (1 0)  (0 2)
 (4 3)  (3 1)  (1 2)  (2 0)
 (4 3)  (3 2)  (2 0)  (0 1)
 (4 3)  (3 2)  (2 1)  (1 0)
 (1 0)  (1 2)  (1 3)  (1 4)
// Node Js Program
// Print all Spanning Tree in 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 MyStack {
	constructor(source, destination, top) {
		this.source = source;
		this.destination = destination;
		this.next = top;
	}
}
class MyGraph {
	//Number of Vertices

	constructor(size) {
		//set value
		this.size = size;
		this.top = null;
		this.node = Array(size).fill(null);
		this.set_data();
	}

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

	//Connect two nodes
	connect(start, last) {
		var new_edge = new AjlistNode(last);
		if (this.node[start].next == null) {
			this.node[start].next = new_edge;
		} else {
			var temp = this.node[start].next;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = new_edge;
		}
	}

	//Add edge of two nodes
	add_edge(start, last) {
		if (start >= 0 &&
			start < this.size &&
			last >= 0 &&
			last < this.size &&
			this.node != null) {
			this.connect(start, last);
			if (start != last) {
				this.connect(last, start);
			}
		} else {
			process.stdout.write("\nHere Something Wrong");
		}
	}
	print_graph() {
		if (this.size > 0 &&
			this.node != null) {
			for (var index = 0; index < this.size; index++) {
				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;
				}
			}
		}
	}
	push(source, destination) {
		var new_node = new MyStack(source, destination, this.top);
		this.top = new_node;
	}
	pop() {
		if (this.top != null) {
			this.top = this.top.next;
		}
	}

	//Display Path from source to destination
	print_path(temp) {
		if (temp == null) {
			return;
		}
		this.print_path(temp.next);
		if (temp.source != -1) {
			process.stdout.write(" (" + temp.source + " " + temp.destination + ") ");
		}
	}
	get_path(start, source, quantity, visit, status) {
		if (start > this.size ||
			quantity > this.size ||
			start < 0 ||
			quantity < 0 ||
			this.node == null) {
			return;
		}

		if (visit[start] == true) {
			return;
		} else {
			//add element into stack
			this.push(source, start);
		}

		if (this.size == quantity &&
			status[start] == true) {
			process.stdout.write("\n");
			this.print_path(this.top);
		}
		visit[start] = true;
		var temp = this.node[start].next;
		while (temp != null) {
			this.get_path(temp.id, start, quantity + 1, visit, status);
			temp = temp.next;
		}

		//remove top element
		this.pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	connectivity(start, source, quantity, visit, edge) {
		if (start > this.size ||
			quantity > this.size ||
			edge == null ||
			visit[start] == true) {
			return;
		}
		visit[start] = true;
		//add element into stack
		this.push(source, edge.id);
		if (this.size == quantity + 1) {
			this.print_path(this.top);
			process.stdout.write("\n");
		}
		edge = edge.next;
		if (edge != null) {
			this.connectivity(edge.id, source, quantity + 1, visit, edge);
		}
		this.pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	spanning_tree() {
		if (this.node != null) {
			//Some auxiliary space, 
			//which are hold the information about visited node and result
			var visit = Array(this.size).fill(false);
			var status = Array(this.size).fill(false);
			var i = 0;
			process.stdout.write("\n Spanning Tree\n Connect edges with node pairs");
			for (i = 0; i < this.size; i++) {
				status[i] = false;
				visit[i] = false;
			}

			for (i = 0; i < this.size; ++i) {
				this.get_path(i, -1, 1, visit, status);
				status[i] = true;
			}

			process.stdout.write("\n");
			for (i = 0; i < this.size; ++i) {
				this.connectivity(i, i, 1, visit, this.node[i].next);
			}
		} else {
			process.stdout.write("Empty Graph");
		}
	}
}

function main(args) {
	//5 implies the number of nodes in graph
	var g = new MyGraph(5);
	//Connected two node with Edges
	//Two parameter indicates edge between start and last nodes
	g.add_edge(0, 1);
	g.add_edge(0, 2);
	g.add_edge(0, 4);
	g.add_edge(1, 2);
	g.add_edge(1, 3);
	g.add_edge(1, 4);
	g.add_edge(2, 3);
	g.add_edge(3, 4);
	g.print_graph();
	g.spanning_tree();
}

main();

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 0 2 3 4
Adjacency list of vertex 2 : 0 1 3
Adjacency list of vertex 3 : 1 2 4
Adjacency list of vertex 4 : 0 1 3
 Spanning Tree
 Connect edges with node pairs
 (1 2)  (2 3)  (3 4)  (4 0)
 (1 4)  (4 3)  (3 2)  (2 0)
 (2 0)  (0 4)  (4 3)  (3 1)
 (2 1)  (1 3)  (3 4)  (4 0)
 (2 3)  (3 1)  (1 4)  (4 0)
 (2 3)  (3 4)  (4 0)  (0 1)
 (2 3)  (3 4)  (4 1)  (1 0)
 (3 1)  (1 4)  (4 0)  (0 2)
 (3 2)  (2 0)  (0 4)  (4 1)
 (3 2)  (2 1)  (1 4)  (4 0)
 (3 4)  (4 0)  (0 1)  (1 2)
 (3 4)  (4 0)  (0 2)  (2 1)
 (3 4)  (4 1)  (1 0)  (0 2)
 (3 4)  (4 1)  (1 2)  (2 0)
 (4 0)  (0 1)  (1 2)  (2 3)
 (4 0)  (0 1)  (1 3)  (3 2)
 (4 0)  (0 2)  (2 1)  (1 3)
 (4 0)  (0 2)  (2 3)  (3 1)
 (4 1)  (1 0)  (0 2)  (2 3)
 (4 1)  (1 3)  (3 2)  (2 0)
 (4 3)  (3 1)  (1 0)  (0 2)
 (4 3)  (3 1)  (1 2)  (2 0)
 (4 3)  (3 2)  (2 0)  (0 1)
 (4 3)  (3 2)  (2 1)  (1 0)
 (1 0)  (1 2)  (1 3)  (1 4)
#  Python 3 Program
#  Print all Spanning Tree in Graph

class AjlistNode :
	# Vertices node key
	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 MyStack :
	
	def __init__(self, source, destination, top) :
		self.source = source
		self.destination = destination
		self.next = top
	

class MyGraph :
	# Number of Vertices
	
	def __init__(self, size) :
		# set value
		self.size = size
		self.top = None
		self.node = [None] * size
		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 nodes
	def connect(self, start, last) :
		new_edge = AjlistNode(last)
		if (self.node[start].next == None) :
			self.node[start].next = new_edge
		else :
			temp = self.node[start].next
			while (temp.next != None) :
				temp = temp.next
			
			temp.next = new_edge
		
	
	# Add edge of two nodes
	def add_edge(self, start, last) :
		if (start >= 0 and start < self.size and 
            last >= 0 and last < self.size and self.node != None) :
			self.connect(start, last)
			if (start != last) :
				self.connect(last, start)
			
		else :
			print("\nHere Something Wrong", end = "")
		
	
	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
			
		
	
	def push(self, source, destination) :
		new_node = MyStack(source, destination, self.top)
		self.top = new_node
	
	def pop(self) :
		if (self.top != None) :
			self.top = self.top.next
		
	
	# Display Path from source to destination
	def print_path(self, temp) :
		if (temp == None) :
			return
		
		self.print_path(temp.next)
		if (temp.source != -1) :
			print(" (", temp.source ," ", temp.destination ,") ", end = "")
		
	
	def get_path(self, start, source, quantity, visit, status) :
		if (start > self.size or quantity > self.size or start < 0 or quantity < 0 or self.node == None) :
			return
		
		if (visit[start] == True) :
			return
		else :
			self.push(source, start)
		
		if (self.size == quantity and status[start] == True) :
			print("\n", end = "")
			self.print_path(self.top)
		
		visit[start] = True
		temp = self.node[start].next
		while (temp != None) :
			self.get_path(temp.id, start, quantity + 1, visit, status)
			temp = temp.next
		
		self.pop()
		# reset the  value of visited node
		visit[start] = False
	
	def connectivity(self, start, source, quantity, visit, edge) :
		if (start > self.size or quantity > self.size or edge == None or visit[start] == True) :
			return
		
		visit[start] = True
		self.push(source, edge.id)
		if (self.size == quantity + 1) :
			self.print_path(self.top)
			print("\n", end = "")
		
		edge = edge.next
		if (edge != None) :
			self.connectivity(edge.id, source, quantity + 1, visit, edge)
		
		self.pop()
		# reset the  value of visited node
		visit[start] = False
	
	def spanning_tree(self) :
		if (self.node != None) :
			visit = [False] * self.size
			status = [False] * self.size
			i = 0
			print("\n Spanning Tree\n Connect edges with node pairs", end = "")
			i = 0
			while (i < self.size) :
				status[i] = False
				visit[i] = False
				i += 1
			
			i = 0
			while (i < self.size) :
				self.get_path(i, -1, 1, visit, status)
				status[i] = True
				i += 1
			
			print("\n", end = "")
			i = 0
			while (i < self.size) :
				self.connectivity(i, i, 1, visit, self.node[i].next)
				i += 1
			
		else :
			print("Empty Graph", end = "")
		
	

def main() :
	# 5 implies the number of nodes in graph
	g = MyGraph(5)
	# Connected two node with Edges
	# Two parameter indicates edge between start and last nodes
	g.add_edge(0, 1)
	g.add_edge(0, 2)
	g.add_edge(0, 4)
	g.add_edge(1, 2)
	g.add_edge(1, 3)
	g.add_edge(1, 4)
	g.add_edge(2, 3)
	g.add_edge(3, 4)
	g.print_graph()
	g.spanning_tree()


if __name__ == "__main__":
	main()

Output

Adjacency list of vertex  0  :  1  2  4
Adjacency list of vertex  1  :  0  2  3  4
Adjacency list of vertex  2  :  0  1  3
Adjacency list of vertex  3  :  1  2  4
Adjacency list of vertex  4  :  0  1  3
 Spanning Tree
 Connect edges with node pairs
 ( 1   2 )  ( 2   3 )  ( 3   4 )  ( 4   0 )
 ( 1   4 )  ( 4   3 )  ( 3   2 )  ( 2   0 )
 ( 2   0 )  ( 0   4 )  ( 4   3 )  ( 3   1 )
 ( 2   1 )  ( 1   3 )  ( 3   4 )  ( 4   0 )
 ( 2   3 )  ( 3   1 )  ( 1   4 )  ( 4   0 )
 ( 2   3 )  ( 3   4 )  ( 4   0 )  ( 0   1 )
 ( 2   3 )  ( 3   4 )  ( 4   1 )  ( 1   0 )
 ( 3   1 )  ( 1   4 )  ( 4   0 )  ( 0   2 )
 ( 3   2 )  ( 2   0 )  ( 0   4 )  ( 4   1 )
 ( 3   2 )  ( 2   1 )  ( 1   4 )  ( 4   0 )
 ( 3   4 )  ( 4   0 )  ( 0   1 )  ( 1   2 )
 ( 3   4 )  ( 4   0 )  ( 0   2 )  ( 2   1 )
 ( 3   4 )  ( 4   1 )  ( 1   0 )  ( 0   2 )
 ( 3   4 )  ( 4   1 )  ( 1   2 )  ( 2   0 )
 ( 4   0 )  ( 0   1 )  ( 1   2 )  ( 2   3 )
 ( 4   0 )  ( 0   1 )  ( 1   3 )  ( 3   2 )
 ( 4   0 )  ( 0   2 )  ( 2   1 )  ( 1   3 )
 ( 4   0 )  ( 0   2 )  ( 2   3 )  ( 3   1 )
 ( 4   1 )  ( 1   0 )  ( 0   2 )  ( 2   3 )
 ( 4   1 )  ( 1   3 )  ( 3   2 )  ( 2   0 )
 ( 4   3 )  ( 3   1 )  ( 1   0 )  ( 0   2 )
 ( 4   3 )  ( 3   1 )  ( 1   2 )  ( 2   0 )
 ( 4   3 )  ( 3   2 )  ( 2   0 )  ( 0   1 )
 ( 4   3 )  ( 3   2 )  ( 2   1 )  ( 1   0 )
 ( 1   0 )  ( 1   2 )  ( 1   3 )  ( 1   4 )
#  Ruby Program
#  Print all Spanning Tree in Graph
class AjlistNode
    # Define the accessor and reader of class AjlistNode
    attr_reader :id, :next
    attr_accessor :id, :next 
	# Vertices node key
	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 MyStack
    # Define the accessor and reader of class MyStack
    attr_reader :source, :destination, :next
    attr_accessor :source, :destination, :next 
	
	def initialize(source, destination, top) 
		self.source = source
		self.destination = destination
		self.next = top
	end
end
class MyGraph
    # Define the accessor and reader of class MyGraph
    attr_reader :size, :node, :top
    attr_accessor :size, :node, :top 
	# Number of Vertices
	def initialize(size) 
		# set value
		self.size = size
		self.top = nil
		self.node = Array.new(size) {nil}
		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 nodes
	def connect(start, last) 
		new_edge = AjlistNode.new(last)
		if (@node[start].next == nil) 
			@node[start].next = new_edge
		else 
			temp = @node[start].next
			while (temp.next != nil) 
				temp = temp.next
			end
			temp.next = new_edge
		end
	end
	# Add edge of two nodes
	def add_edge(start, last) 
		if (start >= 0 &&
			start < @size &&
			last >= 0 &&
			last < @size &&
			@node != nil) 
			self.connect(start, last)
			if (start != last) 
				self.connect(last, start)
			end
		else 
			print("\nHere Something Wrong")
		end
	end
	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
	def push(source, destination) 
		new_node = MyStack.new(source, destination, @top)
		@top = new_node
	end
	def pop() 
		if (@top != nil) 
			@top = @top.next
		end
	end
	# Display Path from source to destination
	def print_path(temp) 
		if (temp == nil) 
			return
		end
		self.print_path(temp.next)
		if (temp.source != -1) 
			print(" (", temp.source ," ", temp.destination ,") ")
		end
	end
	def get_path(start, source, quantity, visit, status) 
		if (start > @size ||
			quantity > @size ||
			start < 0 ||
			quantity < 0 ||
			self.node == nil) 
			return
		end
		if (visit[start] == true) 
			return
		else 
			self.push(source, start)
		end
		if (@size == quantity &&
			status[start] == true) 
			print("\n")
			self.print_path(self.top)
		end
		visit[start] = true
		temp = @node[start].next
		while (temp != nil) 
			self.get_path(temp.id, start, quantity + 1, visit, status)
			temp = temp.next
		end
		self.pop()
		# reset the  value of visited node
		visit[start] = false
	end
	def connectivity(start, source, quantity, visit, edge) 
		if (start > @size ||
			quantity > @size ||
			edge == nil ||
			visit[start] == true) 
			return
		end
		visit[start] = true
		self.push(source, edge.id)
		if (@size == quantity + 1) 
			self.print_path(self.top)
			print("\n")
		end
		edge = edge.next
		if (edge != nil) 
			self.connectivity(edge.id, source, quantity + 1, visit, edge)
		end
		self.pop()
		# reset the  value of visited node
		visit[start] = false
	end
	def spanning_tree() 
		if (@node != nil) 
			visit = Array.new(@size) {false}
			status = Array.new(@size) {false}
			i = 0
			print("\n Spanning Tree\n Connect edges with node pairs")
			i = 0
			while (i < @size) 
				status[i] = false
				visit[i] = false
				i += 1
			end
			i = 0
			while (i < @size) 
				self.get_path(i, -1, 1, visit, status)
				status[i] = true
				i += 1
			end
			print("\n")
			i = 0
			while (i < @size) 
				self.connectivity(i, i, 1, visit, @node[i].next)
				i += 1
			end
		else 
			print("Empty Graph")
		end
	end
end
def main() 
	# 5 implies the number of nodes in graph
	g = MyGraph.new(5)
	# Connected two node with Edges
	# Two parameter indicates edge between start and last nodes
	g.add_edge(0, 1)
	g.add_edge(0, 2)
	g.add_edge(0, 4)
	g.add_edge(1, 2)
	g.add_edge(1, 3)
	g.add_edge(1, 4)
	g.add_edge(2, 3)
	g.add_edge(3, 4)
	g.print_graph()
	g.spanning_tree()
end
main()

Output

Adjacency list of vertex 0  : 1 2 4
Adjacency list of vertex 1  : 0 2 3 4
Adjacency list of vertex 2  : 0 1 3
Adjacency list of vertex 3  : 1 2 4
Adjacency list of vertex 4  : 0 1 3
 Spanning Tree
 Connect edges with node pairs
 (1 2)  (2 3)  (3 4)  (4 0) 
 (1 4)  (4 3)  (3 2)  (2 0) 
 (2 0)  (0 4)  (4 3)  (3 1) 
 (2 1)  (1 3)  (3 4)  (4 0) 
 (2 3)  (3 1)  (1 4)  (4 0) 
 (2 3)  (3 4)  (4 0)  (0 1) 
 (2 3)  (3 4)  (4 1)  (1 0) 
 (3 1)  (1 4)  (4 0)  (0 2) 
 (3 2)  (2 0)  (0 4)  (4 1) 
 (3 2)  (2 1)  (1 4)  (4 0) 
 (3 4)  (4 0)  (0 1)  (1 2) 
 (3 4)  (4 0)  (0 2)  (2 1) 
 (3 4)  (4 1)  (1 0)  (0 2) 
 (3 4)  (4 1)  (1 2)  (2 0) 
 (4 0)  (0 1)  (1 2)  (2 3) 
 (4 0)  (0 1)  (1 3)  (3 2) 
 (4 0)  (0 2)  (2 1)  (1 3) 
 (4 0)  (0 2)  (2 3)  (3 1) 
 (4 1)  (1 0)  (0 2)  (2 3) 
 (4 1)  (1 3)  (3 2)  (2 0) 
 (4 3)  (3 1)  (1 0)  (0 2) 
 (4 3)  (3 1)  (1 2)  (2 0) 
 (4 3)  (3 2)  (2 0)  (0 1) 
 (4 3)  (3 2)  (2 1)  (1 0) 
 (1 0)  (1 2)  (1 3)  (1 4) 
// Scala Program
// Print all Spanning Tree in Graph
class AjlistNode(var id: Int,
	var next: AjlistNode) {
	//Vertices node key



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


	def this(data: Int) {
		this(data,null);
	}
}
class MyStack(var source: Int,
	var destination: Int,
		var next: MyStack) {

}
class MyGraph(var size: Int,
	var node: Array[Vertices],
		var top: MyStack) {

	def this(size: Int) {
		//set value
       this(size,Array.fill[Vertices](size)(null),null);
	   this.set_data();
	}
	//Set initial node value
	def set_data(): Unit = {
		if (node == null) {
			print("\nEmpty Graph");
		} else {
			var index: Int = 0;
			while (index < size) {
				node(index) = new Vertices(index);
				index += 1;
			}
		}
	}
	//Connect two nodes
	def connect(start: Int, last: Int): Unit = {
		var new_edge: AjlistNode = new AjlistNode(last);

		if (node(start).next == null) {
			node(start).next = new_edge;
		} else {
			var temp: AjlistNode = node(start).next;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = new_edge;
		}
	}
	//Add edge of two nodes
	def add_edge(start: Int, last: Int): Unit = {
		if (start >= 0 &&
			start < size &&
			last >= 0 &&
			last < size &&
			node != null) {
			connect(start, last);

			if (start != last) {
				connect(last, start);
			}
		} else {
			print("\nHere Something Wrong");
		}
	}
	def print_graph(): Unit = {
		if (size > 0 &&
			node != null) {
			var index: Int = 0;
			while (index < size) {
				print("\nAdjacency list of vertex " + index + " :");
				var temp: AjlistNode = node(index).next;
				while (temp != null) {
					print(" " + node(temp.id).data);
					temp = temp.next;
				}
				index += 1;
			}
		}
	}
	def push(source: Int, destination: Int): Unit = {
		var new_node: MyStack = new MyStack(source, destination, top);
		top = new_node;
	}
	def pop(): Unit = {
		if (top != null) {
			top = top.next;
		}
	}
	//Display Path from source to destination
	def print_path(temp: MyStack): Unit = {
		if (temp == null) {
			return;
		}
		print_path(temp.next);

		if (temp.source != -1) {
			print(" (" + temp.source + " " + temp.destination + ") ");
		}
	}
	def get_path(start: Int, source: Int, quantity: Int, visit:  Array[Boolean], status:  Array[Boolean]): Unit = {
		if (start > size ||
			quantity > size ||
			start < 0 ||
			quantity < 0 ||
			this.node == null) {
			return;
		}
		if (visit(start) == true) {
			return;
		} else {
			push(source, start);
		}
		if (size == quantity &&
			status(start) == true) {
			print("\n");
			print_path(this.top);
		}
		visit(start) = true;
		var temp: AjlistNode = node(start).next;
		while (temp != null) {
			get_path(temp.id, start, quantity + 1, visit, status);
			temp = temp.next;
		}
		this.pop();

		//reset the  value of visited node
		visit(start) = false;
	}
	def connectivity(start: Int, source: Int, quantity: Int, visit:  Array[Boolean], edge: AjlistNode): Unit = {
		if (start > size ||
			quantity > size ||
			edge == null ||
			visit(start) == true) {
			return;
		}
		visit(start) = true;
		this.push(source, edge.id);

		if (size == quantity + 1) {
			print_path(this.top);
			print("\n");
		}
		var new_edge : AjlistNode = edge.next;

		if (new_edge != null) {
			connectivity(new_edge.id, source, quantity + 1, visit, new_edge);
		}
		this.pop();

		//reset the  value of visited node
		visit(start) = false;
	}
	def spanning_tree(): Unit = {
		if (node != null) {
			var visit:  Array[Boolean] = Array.fill[Boolean](this.size)(false);
			var status:  Array[Boolean] = Array.fill[Boolean](this.size)(false);
			var i: Int = 0;
			print("\n Spanning Tree\n Connect edges with node pairs");
			i = 0;
			while (i < size) {
				status(i) = false;
				visit(i) = false;
				i += 1;
			}
			i = 0;
			while (i < size) {
				get_path(i, -1, 1, visit, status);
				status(i) = true;
				i += 1;
			}
			print("\n");
			i = 0;
			while (i < size) {
				connectivity(i, i, 1, visit, node(i).next);
				i += 1;
			}
		} else {
			print("Empty Graph");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		//5 implies the number of nodes in graph
		var g: MyGraph = new MyGraph(5);

		//Connected two node with Edges
		//Two parameter indicates edge between start and last nodes
		g.add_edge(0, 1);
		g.add_edge(0, 2);
		g.add_edge(0, 4);
		g.add_edge(1, 2);
		g.add_edge(1, 3);
		g.add_edge(1, 4);
		g.add_edge(2, 3);
		g.add_edge(3, 4);
		g.print_graph();
		g.spanning_tree();
	}
}

Output

Adjacency list of vertex 0 : 1 2 4
Adjacency list of vertex 1 : 0 2 3 4
Adjacency list of vertex 2 : 0 1 3
Adjacency list of vertex 3 : 1 2 4
Adjacency list of vertex 4 : 0 1 3
 Spanning Tree
 Connect edges with node pairs
 (1 2)  (2 3)  (3 4)  (4 0)
 (1 4)  (4 3)  (3 2)  (2 0)
 (2 0)  (0 4)  (4 3)  (3 1)
 (2 1)  (1 3)  (3 4)  (4 0)
 (2 3)  (3 1)  (1 4)  (4 0)
 (2 3)  (3 4)  (4 0)  (0 1)
 (2 3)  (3 4)  (4 1)  (1 0)
 (3 1)  (1 4)  (4 0)  (0 2)
 (3 2)  (2 0)  (0 4)  (4 1)
 (3 2)  (2 1)  (1 4)  (4 0)
 (3 4)  (4 0)  (0 1)  (1 2)
 (3 4)  (4 0)  (0 2)  (2 1)
 (3 4)  (4 1)  (1 0)  (0 2)
 (3 4)  (4 1)  (1 2)  (2 0)
 (4 0)  (0 1)  (1 2)  (2 3)
 (4 0)  (0 1)  (1 3)  (3 2)
 (4 0)  (0 2)  (2 1)  (1 3)
 (4 0)  (0 2)  (2 3)  (3 1)
 (4 1)  (1 0)  (0 2)  (2 3)
 (4 1)  (1 3)  (3 2)  (2 0)
 (4 3)  (3 1)  (1 0)  (0 2)
 (4 3)  (3 1)  (1 2)  (2 0)
 (4 3)  (3 2)  (2 0)  (0 1)
 (4 3)  (3 2)  (2 1)  (1 0)
 (1 0)  (1 2)  (1 3)  (1 4)
// Swift Program
// Print all Spanning Tree in 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 MyStack {
	var source: Int;
	var destination: Int;
	var next: MyStack? ;
	init(_ source: Int, _ destination: Int, _ top: MyStack? ) {
		self.source = source;
		self.destination = destination;
		self.next = top;
	}
}
class MyGraph {
	//Number of Vertices
	var size: Int;
	var node: [Vertices]? = [Vertices]();
	var top: MyStack? ;
	init(_ size: Int) {
		//set value
		self.size = size;
		self.top = nil;
		 var i = 0;
        while (i<size) {
          self.node!.append(Vertices(i));
          i+=1;
        }
	}

	//Connect two nodes
	func connect(_ start: Int, _ last: Int) {
		let new_edge: AjlistNode? = AjlistNode(last);
		if (self.node![start].next == nil) {
			self.node![start].next = new_edge;
		} else {
			var temp: AjlistNode? = self.node![start].next;
			while (temp!.next != nil) {
				temp = temp!.next;
			}
			temp!.next = new_edge;
		}
	}
	//Add edge of two nodes
	func add_edge(_ start: Int, _ last: Int) {
		if (start >= 0 &&
			start < self.size &&
			last >= 0 &&
			last < self.size &&
			self.node != nil) {
			self.connect(start, last);
			if (start != last) {
				self.connect(last, start);
			}
		} else {
			print("\nHere Something Wrong", terminator: "");
		}
	}
	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;
			}
		}
	}
	func push(_ source: Int, _ destination: Int) {
		let new_node: MyStack? = MyStack(source, destination, self.top);
		self.top = new_node;
	}
	func pop() {
		if (self.top != nil) {
			self.top = self.top!.next;
		}
	}
	//Display Path from source to destination
	func print_path(_ temp: MyStack? ) {
		if (temp == nil) {
			return;
		}
		self.print_path(temp!.next);
		if (temp!.source != -1) {
			print(" (", temp!.source ," ", temp!.destination ,") ", terminator: "");
		}
	}
	func get_path(_ start: Int, _ source: Int, _ quantity: Int, _ visit: inout[Bool], _ status: [Bool]) {
		if (start > self.size ||
			quantity > self.size ||
			start < 0 ||
			quantity < 0 ||
			self.node == nil) {
			return;
		}
		if (visit[start] == true) {
			return;
		} else {
			self.push(source, start);
		}
		if (self.size == quantity &&
			status[start] == true) {
			print("\n", terminator: "");
			self.print_path(self.top);
		}
		visit[start] = true;
		var temp: AjlistNode? = self.node![start].next;
		while (temp != nil) {
			self.get_path(temp!.id, start, quantity + 1, &visit, status);
			temp = temp!.next;
		}
		self.pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	func connectivity(_ start: Int, _ source: Int, _ quantity: Int, _ visit: inout[Bool], _ edge: AjlistNode? ) {
		if (start > self.size ||
			quantity > self.size ||
			edge == nil ||
			visit[start] == true) {
			return;
		}
		visit[start] = true;
		self.push(source, edge!.id);
		if (self.size == quantity + 1) {
			self.print_path(self.top);
			print("\n", terminator: "");
		}
		let new_edge : AjlistNode? = edge!.next;
		if (new_edge != nil) {
			self.connectivity(new_edge!.id, source, quantity + 1, &visit, new_edge);
		}
		self.pop();
		//reset the  value of visited node
		visit[start] = false;
	}
	func spanning_tree() {
		if (self.node != nil) {
			var visit: [Bool] = Array(repeating: false, count: self.size);
			var status: [Bool] = Array(repeating: false, count: self.size);
			var i: Int = 0;
			print("\n Spanning Tree\n Connect edges with node pairs", terminator: "");

			i = 0;
			while (i < self.size) {
				self.get_path(i, -1, 1, &visit, status);
				status[i] = true;
				i += 1;
			}
			print("\n", terminator: "");
			i = 0;
			while (i < self.size) {
				self.connectivity(i, i, 1, &visit, self.node![i].next);
				i += 1;
			}
		} else {
			print("Empty Graph", terminator: "");
		}
	}
}
func main() {
	//5 implies the number of nodes in graph
	let g: MyGraph? = MyGraph(5);
	//Connected two node with Edges
	//Two parameter indicates edge between start and last nodes
	g!.add_edge(0, 1);
	g!.add_edge(0, 2);
	g!.add_edge(0, 4);
	g!.add_edge(1, 2);
	g!.add_edge(1, 3);
	g!.add_edge(1, 4);
	g!.add_edge(2, 3);
	g!.add_edge(3, 4);
	g!.print_graph();
	g!.spanning_tree();
}
main();

Output

Adjacency list of vertex  0  :  1  2  4
Adjacency list of vertex  1  :  0  2  3  4
Adjacency list of vertex  2  :  0  1  3
Adjacency list of vertex  3  :  1  2  4
Adjacency list of vertex  4  :  0  1  3
 Spanning Tree
 Connect edges with node pairs
 ( 1   2 )  ( 2   3 )  ( 3   4 )  ( 4   0 )
 ( 1   4 )  ( 4   3 )  ( 3   2 )  ( 2   0 )
 ( 2   0 )  ( 0   4 )  ( 4   3 )  ( 3   1 )
 ( 2   1 )  ( 1   3 )  ( 3   4 )  ( 4   0 )
 ( 2   3 )  ( 3   1 )  ( 1   4 )  ( 4   0 )
 ( 2   3 )  ( 3   4 )  ( 4   0 )  ( 0   1 )
 ( 2   3 )  ( 3   4 )  ( 4   1 )  ( 1   0 )
 ( 3   1 )  ( 1   4 )  ( 4   0 )  ( 0   2 )
 ( 3   2 )  ( 2   0 )  ( 0   4 )  ( 4   1 )
 ( 3   2 )  ( 2   1 )  ( 1   4 )  ( 4   0 )
 ( 3   4 )  ( 4   0 )  ( 0   1 )  ( 1   2 )
 ( 3   4 )  ( 4   0 )  ( 0   2 )  ( 2   1 )
 ( 3   4 )  ( 4   1 )  ( 1   0 )  ( 0   2 )
 ( 3   4 )  ( 4   1 )  ( 1   2 )  ( 2   0 )
 ( 4   0 )  ( 0   1 )  ( 1   2 )  ( 2   3 )
 ( 4   0 )  ( 0   1 )  ( 1   3 )  ( 3   2 )
 ( 4   0 )  ( 0   2 )  ( 2   1 )  ( 1   3 )
 ( 4   0 )  ( 0   2 )  ( 2   3 )  ( 3   1 )
 ( 4   1 )  ( 1   0 )  ( 0   2 )  ( 2   3 )
 ( 4   1 )  ( 1   3 )  ( 3   2 )  ( 2   0 )
 ( 4   3 )  ( 3   1 )  ( 1   0 )  ( 0   2 )
 ( 4   3 )  ( 3   1 )  ( 1   2 )  ( 2   0 )
 ( 4   3 )  ( 3   2 )  ( 2   0 )  ( 0   1 )
 ( 4   3 )  ( 3   2 )  ( 2   1 )  ( 1   0 )
 ( 1   0 )  ( 1   2 )  ( 1   3 )  ( 1   4 )




Comment

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