Process the following precedence relations using the Topological Sort Algorithm
ID: 672454 • Letter: P
Question
Process the following precedence relations using the Topological Sort Algorithm taught in class. You must do both parts “A” and “B” to receive credit.
First process all relations in the order specified below to build the initial data structure. Note the subscripts and QLinks are the names of the persons responsible for the task. Label your answer as “Part A.”
QLink
1
Sam
Sara
Tim
Tom
Jill
Bob
8
9
0
0
0
0
0
0
0
0
0
1 < Tom, 8 < Tim, Tim < Tom, 9 < Jill, Sam < Jill, 8 < Tim, Bob < Jill, Sara < Tim, 1 < Sam, Tim < Bob
Partial answer:
QLink
1
Sam
Sara
Tim
Tom
Jill
Bob
8
9
0
1
0
3
2
3
1
0
0
|
|
|
|
|
|
|
| | | | | | |
Sam Jill Tim Bob Jill Tim Jill
| | |
Tom Tom Tim
pro
QLink
1
Sam
Sara
Tim
Tom
Jill
Bob
8
9
0
0
0
0
0
0
0
0
0
Explanation / Answer
PLS PROVIDE UR OWN INPUTS TO GET THE REQUIRED ANSWER. THIS MAY HELP YOU
A C++ program to print topological sorting
#include<iostream>
#include <list>
#include <stack>
using namespace std;
// Class to represent a graph
class Graph
{
int V; // No. of vertices'
// Pointer to an array containing adjacency listsList
list<int> *adj;
// A function used by topologicalSort
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int v, int w);
// prints a Topological Sort of the complete graph
void topologicalSort();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
{
// Mark the current node as visited.
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
// Push current vertex to stack which stores result
Stack.push(v);
}
// The function to do Topological Sort. It uses recursive topologicalSortUtil()
void Graph::topologicalSort()
{
stack<int> Stack;
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to store Topological Sort
// starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Print contents of stack
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
}
// Driver program to test above functions
int main()
{
// Create a graph given in the above diagram
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << "Following is a Topological Sort of the given graph ";
g.topologicalSort();
return 0;
}
OUR PUT IS: 5 4 2 3 1 0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.