Graphs/Traversal - Revision history

Admin: /* Related */

2017-09-07T15:54:49Z

@@ Line 22: / Line 22: @@
 * See [[Recursion]]
-On a graph:
+{{TraversalRelated}}
 =Flags=
 {{GraphsFlag}}

Admin: /* Related */

2017-09-07T15:40:50Z

← Older revision		Revision as of 15:40, 7 September 2017
Line 27:		Line 27:
	* [[Graphs/Euler Tour]]		* [[Graphs/Euler Tour]]

	~~Related pages on tree~~ traversal:		Tree traversal:
	* [[Trees/Preorder]]		* [[Trees/Preorder]]
	* [[Trees/Postorder]]		* [[Trees/Postorder]]
	* [[Trees/Inorder]]		* [[Trees/Inorder]]

	~~Related pages on breadth~~-first search and traversal:		Breadth-first search and traversal on trees:
	* [[BFS]] - breadth first search		* [[BFS]] - breadth first search
	* [[BFT]] - breadth first traversal		* [[BFT]] - breadth first traversal

	~~Related pages~~ on		Depth-first search and traversal on trees:
	* [[DFS]] - depth first search		* [[DFS]] - depth first search
	* [[DFT]] - depth first traversal		* [[DFT]] - depth first traversal

Admin at 15:40, 7 September 2017

2017-09-07T15:40:17Z

← Older revision		Revision as of 15:40, 7 September 2017
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.

	~~==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.		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!

	==Depth First ~~Search and Graph~~ Traversal==		[[Graphs/Depth First Traversal\|Depth first search and traversal]] generally uses recursion and backtracking to traverse all vertices on the graph.

	~~==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=~~		[[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 ~~Pages=~~=		=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==		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Definition */

2017-09-07T15:14:48Z

Definition

← Older revision		Revision as of 15:14, 7 September 2017
Line 3:		Line 3:
	==Definition==		==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.		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.		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.

Admin at 09:09, 5 September 2017

2017-09-05T09:09:33Z

← Older revision		Revision as of 09:09, 5 September 2017
Line 1:		Line 1:
	=~~=Introduction=~~=		=Notes=

	Graph traversal is a ~~way of~~ walking through the ~~entire~~ graph, ~~visiting~~ each vertex ~~in the graph~~ once.		==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}}

Admin at 08:48, 5 September 2017

2017-09-05T08:48:09Z

← Older revision		Revision as of 08:48, 5 September 2017
Line 21:		Line 21:




			==Flags==

	{{GraphsFlag}}		{{GraphsFlag}}

Admin at 08:46, 5 September 2017

2017-09-05T08:46:39Z

← Older revision		Revision as of 08:46, 5 September 2017
Line 19:		Line 19:
	* [[DFS]] - depth first search		* [[DFS]] - depth first search
	* [[DFT]] - depth first traversal		* [[DFT]] - depth first traversal



			{{GraphsFlag}}

Admin at 08:46, 5 September 2017

2017-09-05T08:46:17Z

@@ Line 1: / Line 1: @@
 Graph traversal is a way of walking through the entire graph, visiting each vertex in the graph once.
-There are some similarities with tree traversal. Also see:
+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.
 * [[Trees/Preorder]]
 * [[Trees/Postorder]]
 * [[Trees/Inorder]]

Admin: Created page with "Graph traversal is a way of walking through the entire graph, visiting each vertex in the graph once. There are some similarities with tree traversal. Also see: * Trees/Pr..."

2017-09-05T08:40:05Z

Created page with "Graph traversal is a way of walking through the entire graph, visiting each vertex in the graph once. There are some similarities with tree traversal. Also see: * Trees/Pr..."

New page

Graph traversal is a way of walking through the entire graph, visiting each vertex in the graph once.

There are some similarities with tree traversal. Also see:
* [[Trees/Preorder]]
* [[Trees/Postorder]]
* [[Trees/Inorder]]