jeudi 19 décembre 2019

What is a need of defining indegree vector in private for finding All Topological Sorts of DAG?

What is the importance of defining indegree vector in the private of a class? It could have been defined in alltopologicalSort() function.

class Graph 
{ 
int V;    // No. of vertices 

// Pointer to an array containing adjacency list 
list<int> *adj; 

// Vector to store indegree of vertices 
vector<int> indegree; 

// A function used by alltopologicalSort 
void alltopologicalSortUtil(vector<int>& res, 
                            bool visited[]); 

public: 
Graph(int V);   // Constructor 

// function to add an edge to graph 
void addEdge(int v, int w); 

// Prints all Topological Sorts 
void alltopologicalSort(); 
}; 

And how it is functioning in below addedge function

void Graph::addEdge(int v, int w) 
{ 
adj[v].push_back(w); // Add w to v's list. 

// increasing inner degree of w by 1 
indegree[w]++; 
} 

This is the link to complete code of finding All Topological Sorts of Directed Acyclic Graph https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/

Aucun commentaire:

Enregistrer un commentaire