1

Possible Duplicate:
Best algorithm for detecting cycles in a directed graph

This is a homework that design an algorithm to check if directed graph is dag or not.
The better algorithm that i can think of is :

Step 1: Find a node which has only outgoing edges. If there is no such node, then these is a cycle

Step 2: Start DFS at that node. Traversing each edge and checking whether the edge points back to a node already on the stack. If not finding such edge, there are no cycles in that connected component.

But what confuses me is the time complexity when the graph is represented as a adjacency matrix and adjacency linked.

it should be O(V^2) for adjacency matrix and O(V+E) for linked list?

And one more question is how to write the pesdoo-code, which should output the topological ordering if the graph is dag, or circle if not.

Community
  • 1
  • 1
Chenping
  • 11
  • 2
  • 2
    Discussed at http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph – Aamir Oct 16 '12 at 00:54
  • @aam1r yes, but there is no word about the algorithm analysis.i am not sure my analysis is correct or not.. – Chenping Oct 16 '12 at 01:09
  • is anyone else can help me with that? – Chenping Oct 16 '12 at 01:24
  • 1
    Your time bounds are correct. But you might have a forest, so you need to start at _all_ nodes with only outgoing edges. And you need to be a bit careful about how to detect whether an edge is pointing back into the stack: the operation must be constant time. – Gene Oct 16 '12 at 01:27

0 Answers0