Graph problems

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Graph problems

Post by 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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by 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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by 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
New poster
Posts: 14
Joined: Tue Jun 25, 2002 8:50 am

Post by 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
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape »

Stefan Pochmann wrote: 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

Post Reply

Return to “Other words”