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 » Sat Jun 29, 2002 8:48 pm

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 » Sat Jun 29, 2002 9:25 pm

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 » Sun Jun 30, 2002 5:41 am

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 » Sun Jun 30, 2002 7:39 am

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 » Sun Jun 30, 2002 3:42 pm

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

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Mon Jan 19, 2004 6:42 am

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”