given a graph below
1 2 3 4 5 6 7 8 9 |
|
To traverse this simple graph, usually people go on and on talking about DFS and BFS, and there are many versions of algorithm book 101 talk about the way of implementing it. Today I got asked again by a colleague, and after search around online surprisingly I found there is a no good example anywhere that set a standard for beginners to start. Therefore I coded one for him. And it was pretty tricky since there are some caveat need be take into consideration. I decided to post that here so that it can benefit other people who might need it.
Start with this DFS. I call it classic-DFS This gives the good DFS: It Ends when All NODE ARE VISITED
1 2 3 4 5 6 7 8 9 |
|
This one is difference than the one above, it gives all possible path DFS: it ends when ALL PATH ARE SEARCHED. It also very good for circle detecting. I call it standard DFS or S-DFS
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Now this one is a BFS one. it is very straight forward.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|