Depth-First Search: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| 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. | ||
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 |