Depth-First Search: Difference between revisions
Jump to navigation
Jump to search
Created page with "The Depth-First Search is a recursive algorithm that finds if there is a path from one node to another. This algorithm searches for the node's children first before going to..." |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
This algorithm searches for the node's children first before going to the neighbours. | This algorithm searches for the node's children first before going to the neighbours. | ||
To avoid the algorithm to run in circle infinitely, a flag should indicate if the node has been visited once. The algorithm concludes there is a path between two nodes A and B if one of the node's A children has a path to node B. And, obviously each node has a path to itself. | |||
DFS is preferred if we want to visit all nodes in a graph. | |||
== Resources == | |||
{| class="wikitable" | |||
! | |||
|- | |||
|https://en.wikipedia.org/wiki/Depth-first_search | |||
|} | |||
Latest revision as of 13:57, 30 September 2020
The Depth-First Search is a recursive algorithm that finds if there is a path from one node to another.
This algorithm searches for the node's children first before going to the neighbours.
To avoid the algorithm to run in circle infinitely, a flag should indicate if the node has been visited once. The algorithm concludes there is a path between two nodes A and B if one of the node's A children has a path to node B. And, obviously each node has a path to itself.
DFS is preferred if we want to visit all nodes in a graph.
Resources
| https://en.wikipedia.org/wiki/Depth-first_search |