Write a program to implement an undirected weighted graph andprint out the verti

Question

Write a program to implement an undirected weighted graph andprint out the vertices identification by using the depth firstsearch and breadth first search.   Also your programshould check for connectivity and completeness.

Input order: Number of vertices, followed by a list ofedges. Each edge is represented by 3 numbers – the 2vertices that the edge connects, and the weight of theedge. The identification for a vertex is a number 0 throughN-1, where N is the number of vertices.

Sample input:

5

0 1 30

0 3 45

1 2 10

1 4 20

2 3 45

2 4 5

Let your program be menu driven using the following menu:

1.     Print using depth first search (start withvertex 0)

2.     Print using breadth first search (startwith vertex 0)

3.     Check for connectivity

4.     Check for completeness

For option 3, tell whether or not the graph is a connectedgraph. For option 5, tell whether or not the graph is acomplete graph. You may use an adjacency matrix for yourimplementation.

Explanation / Answer

Dear, //Program on graph traversals using Breadth first Search andDepth First Search

#include <iostream.h>
#include <conio.h>

class Node
{
public:
int data;
Node *link;
Node()
{
data=0;
link=NULL;
}
};

class Stack:private Node
{
Node *top;
public:
Stack()
{
top=NULL;
}
void push(int n,int *y)
{
Node *temp;
if(y[n-1]==0)
{
temp=new Node;
temp->data=n;
temp->link=NULL;
y[n-1]=1;
if(top!=NULL)
temp->link=top;
top=temp;
}
}
int pop()
{
Node *temp;
int m;
if(top==NULL)
return 0;
m=top->data;
temp=top;
top=top->link;
temp->link=NULL;
delete temp;
return m;
}
};

class Queue:private Node
{
Node *rear,*front;
public:
Queue()
{
front=rear=NULL;
}
void insert(int n,int *y)
{
Node *temp;
if(y[n-1]==0)
{
temp=new Node;
temp->data=n;
temp->link=NULL;
y[n-1]=1;
if(front==NULL)
front=rear=temp;
else
{
rear->link=temp;
rear=temp;
}
}
}
int del()
{
Node *temp;
int m;
if(front==NULL)
return 0;
m=front->data;
temp=front;
front=front->link;
temp->link=NULL;
delete temp;
return m;
}
};

void main()
{
Queue q;
Stack s;
clrscr();
int n,m,t,x[10][10],y[10];
int ch;
do
{
clrscr();
cout<<"GRAPH TRAVERSALS"<<endl;
cout<<"================"<<endl;
cout<<"1.Breadth First Search"<<endl;
cout<<"2.Depth first Search"<<endl;
cout<<"3.Exit"<<endl;
cout<<"Enter ur choice"<<endl;
cin>>ch;
switch(ch)
{
case 1:cout<<"Enter the number of nodes"<<endl;
       cin>>n;
       t=n;
       cout<<"Enter theadjacency matrix"<<endl;
       for(int i=0;i<n;i++)
       {
y[i]=0;
for(int j=0;j<n;j++)
cin>>x[i][j];
       }
       char ch1='y';
       do
       {
cout<<"Enter the starting node"<<endl;
cin>>n;
q.insert(n,y);
while((m=q.del())!=0)
{
int j=0;
while(j<t)
{
if(m-1!=j)
{
if(x[m-1][j]==1)
q.insert(j+1,y);
}
j++;
}
cout<<m<<" ";
}
for(i=0;i<t;i++)
y[i]=0;
cout<<" Do u want to continue(Y/N):"<<endl;
cin>>ch1;
       }while(ch1=='y');
       break;
case 2:cout<<"Enter the number of nodes"<<endl;
       cin>>n;
       t=n;
       cout<<"Enter theadjacency matrix"<<endl;
       for(i=0;i<n;i++)
       {
y[i]=0;
for(int j=0;j<n;j++)
cin>>x[i][j];
       }
       char ch2='y';
       do
       {
cout<<"Enter the starting nodes"<<endl;
cin>>n;
s.push(n,y);
while((m=s.pop())!=0)
{
int j=0;
while(j<t)
{
if((m-1)!=j && x[m-1][j]==1)
s.push(j+1,y);
j++;
}
cout<<m<<" ";
}
for(i=0;i<t;i++)
y[i]=0;
cout<<" Do u want to continue(Y/N):"<<endl;
cin>>ch2;
       }while(ch2=='y');
       break;
case 3:break;
}
getch();
}while(ch!=3);
}
I hope this will helpfulfor you................... //Program on graph traversals using Breadth first Search andDepth First Search

#include <iostream.h>
#include <conio.h>

class Node
{
public:
int data;
Node *link;
Node()
{
data=0;
link=NULL;
}
};

class Stack:private Node
{
Node *top;
public:
Stack()
{
top=NULL;
}
void push(int n,int *y)
{
Node *temp;
if(y[n-1]==0)
{
temp=new Node;
temp->data=n;
temp->link=NULL;
y[n-1]=1;
if(top!=NULL)
temp->link=top;
top=temp;
}
}
int pop()
{
Node *temp;
int m;
if(top==NULL)
return 0;
m=top->data;
temp=top;
top=top->link;
temp->link=NULL;
delete temp;
return m;
}
};

class Queue:private Node
{
Node *rear,*front;
public:
Queue()
{
front=rear=NULL;
}
void insert(int n,int *y)
{
Node *temp;
if(y[n-1]==0)
{
temp=new Node;
temp->data=n;
temp->link=NULL;
y[n-1]=1;
if(front==NULL)
front=rear=temp;
else
{
rear->link=temp;
rear=temp;
}
}
}
int del()
{
Node *temp;
int m;
if(front==NULL)
return 0;
m=front->data;
temp=front;
front=front->link;
temp->link=NULL;
delete temp;
return m;
}
};

void main()
{
Queue q;
Stack s;
clrscr();
int n,m,t,x[10][10],y[10];
int ch;
do
{
clrscr();
cout<<"GRAPH TRAVERSALS"<<endl;
cout<<"================"<<endl;
cout<<"1.Breadth First Search"<<endl;
cout<<"2.Depth first Search"<<endl;
cout<<"3.Exit"<<endl;
cout<<"Enter ur choice"<<endl;
cin>>ch;
switch(ch)
{
case 1:cout<<"Enter the number of nodes"<<endl;
       cin>>n;
       t=n;
       cout<<"Enter theadjacency matrix"<<endl;
       for(int i=0;i<n;i++)
       {
y[i]=0;
for(int j=0;j<n;j++)
cin>>x[i][j];
       }
       char ch1='y';
       do
       {
cout<<"Enter the starting node"<<endl;
cin>>n;
q.insert(n,y);
while((m=q.del())!=0)
{
int j=0;
while(j<t)
{
if(m-1!=j)
{
if(x[m-1][j]==1)
q.insert(j+1,y);
}
j++;
}
cout<<m<<" ";
}
for(i=0;i<t;i++)
y[i]=0;
cout<<" Do u want to continue(Y/N):"<<endl;
cin>>ch1;
       }while(ch1=='y');
       break;
case 2:cout<<"Enter the number of nodes"<<endl;
       cin>>n;
       t=n;
       cout<<"Enter theadjacency matrix"<<endl;
       for(i=0;i<n;i++)
       {
y[i]=0;
for(int j=0;j<n;j++)
cin>>x[i][j];
       }
       char ch2='y';
       do
       {
cout<<"Enter the starting nodes"<<endl;
cin>>n;
s.push(n,y);
while((m=s.pop())!=0)
{
int j=0;
while(j<t)
{
if((m-1)!=j && x[m-1][j]==1)
s.push(j+1,y);
j++;
}
cout<<m<<" ";
}
for(i=0;i<t;i++)
y[i]=0;
cout<<" Do u want to continue(Y/N):"<<endl;
cin>>ch2;
       }while(ch2=='y');
       break;
case 3:break;
}
getch();
}while(ch!=3);
}
I hope this will helpfulfor you...................

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.