DFS: Difference between revisions
From charlesreid1
(Created page with "Depth first search: * see Preorder or Postorder or Inorder for recursive depth-first algorithms for tree traversal. * see Recursion for recursion.") |
(→Flags) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Depth first search: | ==Depth first search notes== | ||
* | |||
Depth first search utilizes backtracking and recursion to explore each node of a tree, or each vertex of a graph, exactly once. | |||
On a graph, depth-first search is a crucial building block of several algorithms related to connectivity, such as finding cycles, determining of two vertices are connected, and constructing spanning trees. | |||
For an example of depth-first search on a graph, see [[TSP|traveling salesperson problem]] page. | |||
==Related== | |||
Recursion: | |||
* See [[Recursion]] | |||
{{TraversalRelated}} | |||
==Flags== | |||
{{TreesFlag}} | |||
{{GraphsFlag}} | |||
[[Category:Trees]] | |||
[[Category:Binary Trees]] | |||
[[Category:Graphs]] | |||
[[Category:Traversal]] | |||
[[Category:Algorithms]] | |||
[[Category:Recursion]] | |||
[[Category:DFS]] | |||
Latest revision as of 15:52, 7 September 2017
Depth first search notes
Depth first search utilizes backtracking and recursion to explore each node of a tree, or each vertex of a graph, exactly once.
On a graph, depth-first search is a crucial building block of several algorithms related to connectivity, such as finding cycles, determining of two vertices are connected, and constructing spanning trees.
For an example of depth-first search on a graph, see traveling salesperson problem page.
Related
Recursion:
- See Recursion
Graphs:
- Graphs#Graph Traversals
- Graphs/Depth First Traversal
- Graphs/Breadth First Traversal
- Graphs/Euler Tour
- Graphs/Euler Circuit
Traversals on trees:
Breadth-first search and traversal on trees:
Depth-first search and traversal on trees:
OOP design patterns:
Flags
 |
Trees Part of Computer Science Notes
Series on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree · Trees/ArrayTree · SimpleTree
Tree Traversal Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP · Tree Traversal/Traversal Method Template Tree operations: Trees/Operations Performance · Trees/Removal
Tree Applications Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree · Binary Trees/ArrayBinTree Binary Trees/Cheat Sheet · Binary Trees/OOP · Binary Trees/Implementation Notes
|
