Answer To: Please follow the link:https://www.dropbox.com/sh/75gwop7fcdapuid/AADeJNby2bctf-3VthhEYz-4a?dl=0...
Snehil answered on Nov 16 2020
graph.cpp
graph.cpp
#include
#include
#include"graphmatrix.h"
#include"graphlist.h"
#include"Stack.h"
using namespace std;
void topologicalSort(GraphMatrix graphMatrix, int numVertices);
bool topologicalSortUtil(GraphMatrix graphMatrix, int numVertices, int v, int visited[], Stack &stack);
int main()
{
string fileName;
cout<<"Enter file name : ";
cin>>fileName;
cout< ifstream fin(fileName);
int numVertices;
fin>>numVertices;
GraphMatrix graphMatrix(numVertices);
GraphList graphList(numVertices);
int u,v;
fin>>u>>v;
while(fin)
{
graphMatrix.addEdge(u,v);
graphList.addEdge(u,v);
fin>>u>>v;
}
graphMatrix.printGraph();
cout< graphList.printGraph();
cout< topologicalSort(graphMatrix, numVertices);
return 0;
}
bool topologicalSortUtil(GraphMatrix graphMatrix,int numVertices, int v, int visited[], Stack &stack)
{
bool isCyclic=false;
visited[v] = 1;
for(int i=0;i {
if(graphMatrix.isThereAnEdge(v,i))
{
if(visited[i]==0)
{
isCyclic = topologicalSortUtil(graphMatrix, numVertices, i, visited, stack);
}
else if(visited[i]==1)
{
isCyclic = true;
break;
}
}
}
stack.push(v);
visited[v]=2;
return isCyclic;
}
void topologicalSort(GraphMatrix graphMatrix, int numVertices)
{
int *visited = new int[numVertices];
Stack stack;
int i;
for(i=0;i {
if(visited[i]==0)
{
if(topologicalSortUtil(graphMatrix,numVertices,i,visited,stack)==true)
{
break;
}
}
else if(visited[i]==1)
{
break;
}
}
if(i==numVertices)
{
cout<<"Topologically sorted graph vertices: ";
while(stack.isEmpty()==false)
{
int val;
stack.pop(val);
cout< }
}
else
{
cout<<"Cannot sort topologically as the graph is Cyclic.";
}
delete [] visited;
}
graphlist.h
#ifndef GRAPHLIST_H
#define GRAPHLIST_H
using namespace std;
class GraphList
{
private:
struct ListNode
{
int val;
ListNode *next;
};
ListNode ** headArray;
int numVertices;
int numEdges;
public:
GraphList(int num)
{
numVertices = num;
headArray = new ListNode*[numVertices];
for(int i=0;i {
headArray[i] = new ListNode;
headArray[i]->val=i;
headArray[i]->next=NULL;
}
}
~GraphList()
{
for(int i=0;i {
ListNode* cur = headArray[i];
ListNode* next;
while(cur!=NULL)
{
next = cur->next;
delete cur;
cur=next;
}
}
delete [] headArray;
}
void addEdge(int u, int v)
{
ListNode* cur = headArray[u];
while(cur->next!=NULL)
{
cur = cur->next;
}
cur->next = new ListNode;
cur=cur->next;
cur->val=v;
cur->next=NULL;
numEdges++;
}
void printGraph()
{
...