Graphs/Breadth First Traversal - Revision history

Admin: /* Pseudocode */

2017-09-09T12:10:09Z

Pseudocode

@@ Line 40: / Line 40: @@
                  queue.add(v)
 </pre>
 =Related=

2017-09-09T12:05:18Z

Edge Classification

← Older revision		Revision as of 12:05, 9 September 2017
Line 22:		Line 22:

	All edges are classified as:		All edges are classified as:
	* '''Cross edge''' - connects a vertex to a vertex that is not an ancestor or a descendant in the ~~DFS~~ tree		* '''Cross edge''' - connects a vertex to a vertex that is not an ancestor or a descendant in the BFS tree

	==Pseudocode==		==Pseudocode==

2017-09-09T12:05:06Z

BFS Tree

← Older revision		Revision as of 12:05, 9 September 2017
Line 11:		Line 11:
	==BFS Tree==		==BFS Tree==

	Edges discovered during a breadth-first search will form a tree~~. BFS is notable because the tree that is formed will yield the shortest path between two nodes~~.		Edges discovered during a breadth-first search will form a tree.

	~~Because of~~ the ~~fact that the depth-first search must proceed in an ordered manner, and cannot re-visit vertices that have already been vertices, we can think~~ of the ~~depth-first search as forming a tree~~.		BFS tree is notable because the tree consists only of the shortest paths between two nodes.

	==Edge Classification==		==Edge Classification==

2017-09-09T11:52:05Z

What BFS Gets Us

← Older revision		Revision as of 11:52, 9 September 2017
Line 8:		Line 8:

	The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.		The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.

			==BFS Tree==

			Edges discovered during a breadth-first search will form a tree. BFS is notable because the tree that is formed will yield the shortest path between two nodes.

			Because of the fact that the depth-first search must proceed in an ordered manner, and cannot re-visit vertices that have already been vertices, we can think of the depth-first search as forming a tree.

			==Edge Classification==

			For a depth-first search, edges were classified as back edges (connecting vertices to ancestor vertices), forward edges (connecting vertices to descendant vertices), and cross edges (connects vertices to other vertices that are not ancestors or descendants).

			For breadth-first search, all BFS tree edges form the shortest path between two vertices. That means that there are NO back edges or forward edges (because if they existed, they would be shorter paths and therefore provide a shorter path).

			All edges are classified as:
			* '''Cross edge''' - connects a vertex to a vertex that is not an ancestor or a descendant in the DFS tree

	==Pseudocode==		==Pseudocode==

2017-09-09T11:25:00Z

Pseudocode

2017-09-09T11:23:49Z

What BFS Gets Us

← Older revision		Revision as of 11:23, 9 September 2017
Line 8:		Line 8:

	The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.		The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.

			==Pseudocode==

			<pre>
			def bfs(g, s, discovered):
			discovered = empty map
			create new queue
			queue.add(s)
			while queue is not empty:
			u = queue.pop()
			for e in incident_edges(u):
			v = opposite_edge(u, e)
			if v not in discovered:
			// add (v,e) to discovered
			discovered[v] = e
			queue.add(v)
			</pre>

	=Related=		=Related=

2017-09-07T15:44:41Z

@@ Line 11: / Line 11: @@
 =Related=
-Graphs:
+{{TraversalRelated}}
 =Flags=

2017-09-07T15:42:49Z

← Older revision		Revision as of 15:42, 7 September 2017
Line 20:		Line 20:
	* [[Trees/Postorder]]		* [[Trees/Postorder]]
	* [[Trees/Inorder]]		* [[Trees/Inorder]]

			OOP design patterns:
			* [[Tree Traversal/Traversal Method Template]]

	[[:Category:Traversal]]		[[:Category:Traversal]]

2017-09-07T13:58:18Z

Resources

← Older revision		Revision as of 13:58, 7 September 2017
Line 9:		Line 9:
	The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.		The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.

	=~~Resources~~=		=Related=

	==Flags==		Graphs:
			* [[Graphs/Depth First Traversal]]
			* [[Graphs/Breadth First Traversal]]
			* [[Graphs/Euler Tour]]

			Traversals on trees:
			* [[Trees/Preorder]]
			* [[Trees/Postorder]]
			* [[Trees/Inorder]]

			[[:Category:Traversal]]

			=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

	[[Category:BFS]]		[[Category:BFS]]
			[[Category:Traversal]]

2017-09-07T13:40:06Z

← Older revision		Revision as of 13:40, 7 September 2017
Line 3:		Line 3:
	=Notes=		=Notes=

			==What BFS Gets Us==

			Breadth-first search is important because it gets us the shortest path (the path with the fewest number of edges) from a vertex u to a vertex v. To state this more rigorously, a path in a breadth-first search tree rooted at vertex u to any other vertex v is guaranteed to be the shortest path from u to v (where shortest path denotes number of edges).

			The fact that the BFS tree yields shortest paths is a natural consequence of how the BFS process works.

	=Resources=		=Resources=