Graphs/Traversal: Difference between revisions
From charlesreid1
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
= | =Notes= | ||
Graph traversal is a | ==Definition== | ||
Graph traversal is a systematic method for walking through every vertex and edge in the graph. In general, each vertex 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. | 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. | |||
==Usefulness for Algorithms== | |||
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 Graph Traversal== | |||
==Breadth First Search and Graph Traversal== | |||
As mentioned on the [[BFS]] page, the most convenient way to implement a breadth first search is to use a [[Queue]] data structure - as each vertex is visited, its unvisited, connected components are added to the back of the queue. Once a particular vertex has been visited, the next vertex to be visited is determined by popping the next item from the queue. | |||
=Resources= | |||
==Related Pages== | ==Related Pages== | ||
Recursion: | |||
* See [[Recursion]] | |||
Related pages on tree traversal: | Related pages on tree traversal: | ||
| Line 19: | Line 40: | ||
* [[DFS]] - depth first search | * [[DFS]] - depth first search | ||
* [[DFT]] - depth first traversal | * [[DFT]] - depth first traversal | ||
==Flags== | ==Flags== | ||
{{GraphsFlag}} | {{GraphsFlag}} | ||
Revision as of 09:09, 5 September 2017
Notes
Definition
Graph traversal is a systematic method for walking through every vertex and edge in the graph. In general, each vertex 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.
Usefulness for Algorithms
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 Graph Traversal
Breadth First Search and Graph Traversal
As mentioned on the BFS page, the most convenient way to implement a breadth first search is to use a Queue data structure - as each vertex is visited, its unvisited, connected components are added to the back of the queue. Once a particular vertex has been visited, the next vertex to be visited is determined by popping the next item from the queue.
Resources
Related Pages
Recursion:
- See Recursion
Related pages on tree traversal:
Related pages on breadth-first search and traversal:
Related pages on
Flags
