Depth-First Search: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
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. | 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. | ||
== Resources == | |||
{| class="wikitable" | |||
! | |||
|- | |||
|https://en.wikipedia.org/wiki/Depth-first_search | |||
|} | |||
Revision as of 22:04, 3 June 2018
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.
Resources
| https://en.wikipedia.org/wiki/Depth-first_search |