Question

Write a program to test the breadth-first topological ordering algorithm.

Data Structures, Visual Studios 2017 C++

Answer 1

main.cpp

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

const int vert = 6;

int src;

vector <bool> visitsOfVertex(vert, false);

vector <int> inDeg(vert, 0);

vector <int> X;

void creatingEdges(vector <int> arr[], int u, int v1){

arr[u].push_back(v1);

}

void TopSort(vector <int> arr[]){

queue <int> qu;

int v1;

for (int x = 0; x < vert; x++)

for (vector <int>::iterator iter = arr[x].begin(); iter != arr[x].end(); iter++)

inDeg.at(*iter)++;

for (int x = 0; x < vert; x++)

if (inDeg.at(x) == 0){

src = x;

qu.push(src);

visitsOfVertex.at(src) = true;

break;

}

while (!qu.empty()){

v1 = qu.front();

qu.pop();

X.push_back(v1);

for (vector<int>::iterator iter = arr[v1].begin(); iter != arr[v1].end(); iter++)

if (!visitsOfVertex.at(*iter)){

inDeg.at(*iter)--;

if (inDeg.at(*iter) == 0){

qu.push(*iter);

visitsOfVertex.at(*iter) = true;

}

}

}

}

int main (void){

vector<int> arr[vert];

creatingEdges(arr, 0, 1);

creatingEdges(arr, 0, 3);

creatingEdges(arr, 1, 2);

creatingEdges(arr, 1, 3);

creatingEdges(arr, 2, 3);

creatingEdges(arr, 2, 4);

creatingEdges(arr, 2, 5);

creatingEdges(arr, 3, 4);

creatingEdges(arr, 3, 5);

creatingEdges(arr, 4, 5);

TopSort(arr);

cout << "Topological Ordering is: ";

for (int x = 0; x < X.size(); x++)

cout << X.at(x) << " ";

cout << endl;

}

Output:

Topological Ordering is: 0 1 2 3 4 5