Problem in C++ In a depth-first topological ordering, we start with finding a ve

Question

Problem in C++

In a depth-first topological ordering, we start with finding a vertex that has
no successors (such a vertex exists because the graph has no cycles), and place
it last in the topological order. After we have placed all the successors of a
vertex in topological order, we place the vertex in the topological order
before any of its successors. Clearly, in the depth-first topological ordering,
first we find the vertex to be placed in topologicalOrder[n-1], then
topologicalOrder[n-2], and so on.

Write the definitions of the C++ functions to implement the depth-first topological
ordering. Add these functions to the class topologicalOrderType,
which is derived from the class graphType. Also, write a program to test your
depth-first topological ordering.

Explanation / Answer

#include <cstdio>
#include <vector>
#include <list>
#include <cstring>
using namespace std;
// Class to represent a Digraph, with vertices labeled
// from 0 to V-1, where V is the number of vertices
class topologicalOderType:public GraphType {
public:
    int V;
    vector <int>* adjacentList;
    bool* explor;
    list <int> topologicalOrder;
    void dfsUtil(int u) {
        explor[u] = true;
        for (vector <int>::iterator v = adjacentList[u].begin(); v != adjList[u].end(); v++)
            if (!explor[*v])
                dfsUtil(*v);
        topologicalOrder.push_front(u);
    }
    void dfs() {
        for (int u = 0; u < V; u++)
            if (!explor[u])
                dfsUtil(u);
    }
public:
    // create an empty Digraph having V vertices
  
    // add a directed edge u -> v to the digraph
    // returns false if either u or v is less than 0 or greater than equal to V
    // returns true if the edge was added to the digraph
    bool addEdge(int u, int v) {
        if (u < 0 || u >= V) return false;
        if (v < 0 || v >= V) return false;
        adjList[u].push_back(v);
        return true;
    }
    list <int> getTopologicalOrder() {
        if (topologicalOrder.empty())
            dfs();
        return topologicalOrder;
    }
    void printTopologicalOrder() {
        if (topologicalOrder.empty())
            dfs();
        printf("Topological Order :");
        for (list<int>::iterator it = topologicalOrder.begin(); it != topologicalOrder.end(); it++)
            printf(" %d", *it);
        printf(" ");
    }
};

class graphType

{
Graphtype(int V) {
        this->V = V;
        adjacentList = new vector <int>[V];
        explor= new bool[V];
        memset(explor, false, V * sizeof(bool));
    }
    ~Graphtype() {
        delete [] adjList;
        delete [] explored;
    }

    }

int main() {
    Graph G(8);
    G.addEdge(2, 0);
    G.addEdge(1, 2);
    G.addEdge(2, 3);
    G.addEdge(2, 5);
    G.addEdge(6, 2);
    G.addEdge(7, 5);
    G.addEdge(4, 7);
    G.addEdge(6, 7);
    G.addEdge(4, 3);
    G.printTopologicalOrder();
    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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