CareerCup

topological sorting

find indgree = 0 nodes and put them in a queue Q

get a node N each time out of the Q, and process N; decrease the indegree of the nodes point to by 1; if a node N points to now has indegree of 0, then put it in Q

so on and so forth until there is nothing left in Q; if all nodes are processed, then G has no cycle

a directed graph has a cycle if and only if its Depth First Search reveals a back edge.

You can do it via modified DFS - but instead of visited nodes set use current path set - whenever recursing into a next node add it to the path and remove it on the way back. If you find next node in current path - it's a cycle.

bool cycleExists(const Graph::Node &start,
                const Graph::Node &currentNode,
                std::set<Graph::Node> &pathNodes) {
    pathNodes.insert(currentNode);

    for(auto it = currentNode.adjucents.begin(); it != currentNode.adjucents.end(); ++it) {
        if(pathNodes.find(*it) == pathNodes.end()) {
            if(cycleExists(start, *it, pathNodes)) return true;
            pathNodes.erase(*it);
        } else {
            return true;
        }
    }
    return false;
}

bool cycleExists(const Graph::Node &start) {
    std::set<Graph::Node> pathNodes;
    return cycleExists(start, start, pathNodes);
}

this is what i got from wiki, which is said above...

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
output error message (graph has at least one cycle)
else
output message (proposed topologically sorted order: L)

The cycle detection algorithm for trees can easily be modified to work for graphs. The key is that in a
DFS of an acyclic graph, a node whose descendants have all been visited can be seen again without implying
a cycle. However, if a node is seen a second time before all of its descendants have been visited, then there
must be a cycle. Can you see why this is? Suppose there is a cycle containing node A. Then this means
that A must be reachable from one of its descendants. So when the DFS is visiting that descendant, it will
see A again, before it has finished visiting all of A’s descendants. So there is a cycle.
In order to detect cycles, we use a modified depth first search called a colored DFS. All nodes are initially
marked white. When a node is encountered, it is marked grey, and when its descendants are completely
visited, it is marked black. If a grey node is ever encountered, then there is a cycle.

can anyone explain the source code of dfs???

By doing a BFS or DFS and keeping track of the visited nodes we can detect a cycle. A cycle is detected when we visit an already visited node during the traversal.

What is the problem with normal recursive DFS?? I think it is sufficient.