GENERAL QUESTIONS: Graph: Path: Cycle: Adjacency vertices: Adjacency List/Adjace

Question

GENERAL QUESTIONS: Graph: Path: Cycle: Adjacency vertices: Adjacency List/Adjacency Matrix: Spanning Tree: Minimal Spanning Tree: Topological Sorting: EXAMPLES OF FUNCTIONS/ALGORITHMS a. Write an algorithm for Prim's m.s.t. *In (English and C++) b. Write an algorithm for Kruskall's m.s.t. *In (English and C++) c. Write a function that returns true if there is cycle in a graph, false otherwise. d. A vertex which has incoming edges from all vertices and has no outgoing edges is called a Universal sink. Write a function that returns true if there is a Universal sink in a graph, false otherwise. e. Write a function that return true if a graph is connected, false otherwise. f. Write a function that return true if a graph is complete, false Cycle: Adjacent vertices: otherwise. g. Write a function that deletes a vertex from a graph (clearly, you must delete all incoming/outgoing edges as well !) h. Write a function that returns true if there is at least one vertex that is not reachable.

Explanation / Answer

Prim's Algorithm:

#include "stdafx.h"
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u;

int main()
{
int m,c;
cout <<"enter no of vertices ";
cin >> n;
cout <<"enter no of edges ";
cin >> m;
cout <<" EDGES Cost ";
for(k=1;k<=m;k++)
{
        cout<<"Enter the vertices and cost of Edge ";
  cin >>i>>j>>c;
  cost[i][j]=c;
        cost[j][i]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
  if(cost[i][j]==0)
  cost[i][j]=9999;

cout <<"ORDER OF VISITED VERTICES";
k=1;
while(k<n)
{
  m=9999;
  if(k==1)
  {
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    if(cost[i][j]<m)
    {
     m=cost[i][j];
     u=i;
    }
  }
  else
  {
   for(j=n;j>=1;j--)
   if(cost[v][j]<m && visited[j]!=1 && visit[j]!=1)
   {
    visit[j]=1;
    stk[top]=j;
    top++;
    m=cost[v][j];
    u=j;
   }
  }
  cost[v][u]=9999;
  v=u;
  cout<<v << " ";
  k++;
  visit[v]=0; visited[v]=1;
}
    system("pause");
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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