Graphs/Traversal: Difference between revisions
From charlesreid1
No edit summary |
|||
| Line 8: | Line 8: | ||
[[Recursion]] is an important concept in both graph and tree traversal - specifically for depth-first traversal methods. | [[Recursion]] is an important concept in both graph and tree traversal - specifically for depth-first traversal methods. | ||
Traversal is a useful building block for other algorithms. Traversal helps address questions of reachability - whether and how you can reach one vertex from another, finding the shortest path, finding whether a graph is connected, finding cycles, and finding spanning trees. | Traversal is a useful building block for other algorithms. Traversal helps address questions of reachability - whether and how you can reach one vertex from another, finding the shortest path, finding whether a graph is connected, finding cycles, and finding spanning trees. | ||
| Line 15: | Line 13: | ||
These algorithms all build on the idea of graph traversal, so this is a really important concept to nail down before moving on to other graph algorithms! | These algorithms all build on the idea of graph traversal, so this is a really important concept to nail down before moving on to other graph algorithms! | ||
[[Graphs/Depth First Traversal|Depth first search and traversal]] generally uses recursion and backtracking to traverse all vertices on the graph. | |||
[[Graphs/Breadth First Traversal|Breadth first search and traversal]] generally uses a queue data structure to traverse all vertices on a graph. As each vertex is visited, neighbors of said vertex are added to the queue. Once a particular vertex is visited, the next vertex to visit is obtained by popping an item from queue. | |||
=Related= | |||
Recursion: | Recursion: | ||
* See [[Recursion]] | * See [[Recursion]] | ||
On a graph: | |||
* [[Graphs/Breadth First Traversal]] | |||
* [[Graphs/Depth First Traversal]] | |||
* [[Graphs/Euler Tour]] | |||
Related pages on tree traversal: | Related pages on tree traversal: | ||
| Line 41: | Line 40: | ||
* [[DFT]] - depth first traversal | * [[DFT]] - depth first traversal | ||
=Flags= | |||
{{GraphsFlag}} | {{GraphsFlag}} | ||
Revision as of 15:40, 7 September 2017
Notes
Definition
Graph traversal is a systematic method for walking through every vertex and edge in the graph. Generally, a traversal visits each vertex exactly once. However, with an Euler tour (traversal), each edge is visited exactly once.
There are some similarities with tree traversal, but graph traversal is basically a more general version of tree traversal - trees are DAGs (directed acyclic graphs), so tree traversals are traversals on a DAG.
Recursion is an important concept in both graph and tree traversal - specifically for depth-first traversal methods.
Traversal is a useful building block for other algorithms. Traversal helps address questions of reachability - whether and how you can reach one vertex from another, finding the shortest path, finding whether a graph is connected, finding cycles, and finding spanning trees.
These algorithms all build on the idea of graph traversal, so this is a really important concept to nail down before moving on to other graph algorithms!
Depth first search and traversal generally uses recursion and backtracking to traverse all vertices on the graph.
Breadth first search and traversal generally uses a queue data structure to traverse all vertices on a graph. As each vertex is visited, neighbors of said vertex are added to the queue. Once a particular vertex is visited, the next vertex to visit is obtained by popping an item from queue.
Related
Recursion:
- See Recursion
On a graph:
Related pages on tree traversal:
Related pages on breadth-first search and traversal:
Related pages on
Flags
