Computer Science Question: Forests/Graphs

[Ameesh]

i need to know the optimum algorithim for finding cycles in a forest that may contain disjoint graphs. I start off with a pointer to an array of nodes in the forest and the count of nodes.

what is the big O and little O and theta of this algorithm?


Thanks,
Ameesh

 

[Ameesh]

hello?

 

sounds like someone doesn't want to do their Comp Sci project. I don't actually have an answer for you though.

 

[CTho9305]

Ask me last semester Look at Kruskal's/Dijkstra's algorithms (whatever is used for shortest-path, I don't remember), and maybe keep a list of nodes in each tree or something. It would probably be O(m*O(algorithm)) where m is the number of trees and the algorithm is the shortest-path algorithm (google it), but I haven't given it any thought.

edit: Is the graph directed? If it is, I have no idea, unless you start off knowing each root.

 

[Shalmanese]

A flooding algorithm would do it. But waitasec... if its disjoint, wouldnt that mean that given a single node its impossible to reach the entire tree?

 

[CTho9305]

Originally posted by: Shalmanese
A flooding algorithm would do it. But waitasec... if its disjoint, wouldnt that mean that given a single node its impossible to reach the entire tree?

That's why he has to pick a start point, explore the complete tree (only possible if it is non-directed, unless he knows the roots), then pick another node that hasn't been visited and explore that tree... repeat until you've hit every node.

 

[lukatmyshu]

In order for your nodes to comprise a forest, the set MUST be disjoint. Your question isn't so clear, so I had to make some assumptions. 1) Your graph is undirected. 2) The problem is really to take the nodes, and classify them into graphs that are NOT disjoint (so I give you a bunch of nodes and edges and your algorithm spits them back in some grouping which corresponds to their actual structure). If this is correct, then simple DFS will work .... and if you do it properly then it'll just take O( |E| +|V|) time. Actually this is an upper AND lower bound .... DFS is theta(E + V).