Graph problems

[10153EN]

I am solving problems, but I am poor at graph problems.

Could anymore share his or her experience on how to have an efficient algorithm to detect or check for presences of cycles on a graph?

I just know DFS, but I think it's a poor algo.

Thx.

[Stefan Pochmann]

You couldn't be more wrong. DFS rules, it's one of the fastest and most versatile algorithms out there and because of that one of my favourite algorithms. In particular for the detection of cycles, please name another algorithm that solves it faster or is easier to code. I think I can't name one.

[10153EN]

What I thought before is that DFS is a brute force method to find solutions, so it's a slow algo. For some problems like MST, shortest path, DFS most often gets time limit exceeds.

That's why I am afraid to try on cycle detection problems~

Thx for your advice, I will try by DFS.

[Stefan Pochmann]

Hmm, I might be wrong, but I think what you mean with the brute force method might be more appropriately be called backtracking.

When I think DFS, then I see the O(V+E) algorithm that traverses every part of the graph exactly once, without taking back choices made (i.e. the DFS tree is only extended).

For a nice application, try to solve problem 610 (Street Directions) with DFS.

[tenshi]

Some graph problems can be easily solved by DFS.
Backtracking is a kind of method to tranverse a search tree.
Diffient problems diffient methods.
If you want to know more, just visit the following site,
you will get reply very soon.( A lot of excellent programmers from China there)

Welcome to visit :
http://www.ioiforum.org/en/
Here to register:
http://www.ioiforum.org/userreg.asp

[horape]

For a nice application, try to solve problem 610 (Street Directions) with DFS.

Or, if you want a more challenging one, try 10510 (Cactus)

Saludos,
HoraPe