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