1> Returns the vertices in such order that if there is an edge between u and v then u appears before v

Algorithm

$O(V+E)$

• Calculate the indegree for all vertices.
• Create a new queue and add all the vertices with indegree equal to 0.
• While the queue is not empty:
  • Get, pop and save the first element of the queue.
  • Decrease the indegree of all its neighbors.
  • If the new indegree of a neighbor is 0 add it to the queue

C++ code

vector<T> topsort(const Graph<T> *g) {
	vector<T> res;
	// Set the indegree to 0 and then calculate the real value
	for (Vertex<T> *ele: g->getVertexSet()) {
		ele->setIndegree(0);
	}
	for (Vertex<T> *ele: g->getVertexSet()) {
		for (Edge<T> edge: ele->getAdj()) {
			edge.getDest()->setIndegree(edge.getDest()->getIndegree() + 1);
		}
	}
	// Add all the vertices with indegree 0 to the queue
	queue<Vertex<T> *> tempQueue;
	for (Vertex<T> *ele: g->getVertexSet()) {
		if (ele->getIndegree() == 0) {
			tempQueue.push(ele);
		}
	}
	while (!tempQueue.empty()) {
		Vertex<T>* head = tempQueue.front();
		res.push_back(head->getInfo());
		tempQueue.pop();
		// Decrease the indegree of all its neighbors
		for (Edge<T> ele: head->getAdj()) {
			ele.getDest()->setIndegree(ele.getDest()->getIndegree() - 1);
			// If the indegree is 0, add it to the queue
			if (ele.getDest()->getIndegree() <= 0) {
				tempQueue.push(ele.getDest());
			}
		}
	}
return res;
}