Graphs/Depth First Traversal - Revision history

Admin: /* Reconstruct Path in DFS Tree */

2018-02-02T01:45:30Z

Reconstruct Path in DFS Tree

← Older revision		Revision as of 01:45, 2 February 2018
Line 75:		Line 75:
	* Add a boolean flag to the Vertex object, and an accessors methods visit() and unvisit()		* Add a boolean flag to the Vertex object, and an accessors methods visit() and unvisit()

	===Reconstruct Path in DFS Tree===		===Reconstruct Path U to V in DFS Tree===

	To reconstruct the path using the collection of vertex-edge pairs, we can write a reconstruct_path method that takes two vertices, and the collection of vertex-edge pairs:		To reconstruct the path using the collection of vertex-edge pairs, we can write a reconstruct_path method that takes two vertices, and the collection of vertex-edge pairs:

Admin: /* Construct DFS Tree */

2018-02-02T01:02:56Z

Construct DFS Tree

← Older revision		Revision as of 01:02, 2 February 2018
Line 72:		Line 72:

	There are (at least) two methods for tracking which vertices have been visited:		There are (at least) two methods for tracking which vertices have been visited:
	* Maintain a ~~set or~~ hash map containing the vertex~~'s label~~, allowing an O(1) determination of the vertex has been visited		* Maintain a hash map containing the vertex v as the key and the edge e as the value, allowing an O(1) determination of the vertex has been visited
	* Add a boolean flag to the Vertex object, and an accessors methods visit() and unvisit()		* Add a boolean flag to the Vertex object, and an accessors methods visit() and unvisit()

Admin: /* Construct DFS Tree */

2018-02-02T01:00:12Z

Construct DFS Tree

← Older revision		Revision as of 01:00, 2 February 2018
Line 63:		Line 63:

	def DFS(G, u):		def DFS(G, u):
			mark vertex u as visited
	for each outgoing edge e = (u,v) of u:		for each outgoing edge e = (u,v) of u:
	if vertex v not visited:		if vertex v not visited:

Admin: /* Construct DFS Tree */

2018-02-02T00:59:53Z

Construct DFS Tree

← Older revision		Revision as of 00:59, 2 February 2018
Line 69:		Line 69:
	call DFS(G,v)		call DFS(G,v)
	</pre>		</pre>

			There are (at least) two methods for tracking which vertices have been visited:
			* Maintain a set or hash map containing the vertex's label, allowing an O(1) determination of the vertex has been visited
			* Add a boolean flag to the Vertex object, and an accessors methods visit() and unvisit()

	===Reconstruct Path in DFS Tree===		===Reconstruct Path in DFS Tree===

Admin: /* Java Code */

2017-10-17T10:20:55Z

Java Code

← Older revision		Revision as of 10:20, 17 October 2017
Line 101:		Line 101:

	See [[Graphs/Java/Adjacency Map Lite#Algorithms]] for an implementation of a depth-first search.		See [[Graphs/Java/Adjacency Map Lite#Algorithms]] for an implementation of a depth-first search.

			The code for the DFS is given below, but refer to [[Graphs/Java/Adjacency Map Lite#Algorithms]] for implementation details (particularly the Graph, Vertex, and Edge classes). These are straightforward enough to understand here though.

			<pre>
			/** Recursive depth-first search that populates HashMap discovered
			* with all edges/vertices discoverable from u.*/
			public static void dfs(Graph g, Vertex u,
			HashSet<Vertex> known,
			HashMap<Vertex, Edge> discovered) {
			known.add(u);
			for(Edge e : u.outgoingEdges()) {
			Vertex v = e.getOpposite(u);
			if(!known.contains(v)) {
			// e = edge that discovered v
			discovered.put(v,e);
			dfs(g, v, known, discovered);
			}
			}
			}
			</pre>

			This results in a map, discovered, that maps vertices to the edge by which they were discovered. Each vertex on a particular connected component on a graph will be contained in discovered, except the original vertex (u) that was passed with the original dfs() function call. That vertex is the root vertex of the component, and is left out of the discovered map.

			If there are multiple components, DFS can be called on each component. The number of vertices on the graph that are missing from the discovered map gives the number of connected components on the graph. Again, refer to [[Graphs/Java/Adjacency Map Lite#Algorithms]] for details.

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

Admin: /* Pseudocode */

2017-10-17T10:04:36Z

Pseudocode

← Older revision		Revision as of 10:04, 17 October 2017
Line 97:		Line 97:
	return reversed(path)		return reversed(path)
	</pre>		</pre>

			==Java Code==

			See [[Graphs/Java/Adjacency Map Lite#Algorithms]] for an implementation of a depth-first search.

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

Admin: /* Reconstruct Path in DFS Tree */

2017-10-17T10:03:49Z

Reconstruct Path in DFS Tree

← Older revision		Revision as of 10:03, 17 October 2017
Line 78:		Line 78:
	# using the list of vertex-edge pairs		# using the list of vertex-edge pairs
	# in the DFS tree.		# in the DFS tree.
	reconstruct_path(u, v, vertex_edge_pairs):
			def reconstruct_path(u, v, vertex_edge_pairs):
	initialize reconstructed path		initialize reconstructed path
	if v not in vertex_edge_pairs:		if v not in vertex_edge_pairs:

Admin: /* Construct DFS Tree */

2017-10-17T10:03:39Z

Construct DFS Tree

← Older revision		Revision as of 10:03, 17 October 2017
Line 61:		Line 61:
	# Results in a collection of vertices reachable from vertex u,		# Results in a collection of vertices reachable from vertex u,
	# in the form of (v,e) pairs (vertex v reachable from vertex u via edge e)		# in the form of (v,e) pairs (vertex v reachable from vertex u via edge e)
	DFS(G, u):
			def DFS(G, u):
	for each outgoing edge e = (u,v) of u:		for each outgoing edge e = (u,v) of u:
	if vertex v not visited:		if vertex v not visited:

Admin: /* Properties of DFS */

2017-09-10T07:16:16Z

Properties of DFS

← Older revision		Revision as of 07:16, 10 September 2017
Line 145:		Line 145:
	DFS is called at most once on each vertex - once DFS has been called on a vertex, it is marked as visited and is not visited a second time. On an undirected graph, each edge is examined at most twice (once from each end of its vertex). On a directed graph, each edge is examined at most once (from the origin vertex).		DFS is called at most once on each vertex - once DFS has been called on a vertex, it is marked as visited and is not visited a second time. On an undirected graph, each edge is examined at most twice (once from each end of its vertex). On a directed graph, each edge is examined at most once (from the origin vertex).

	===Big O Cost===		==Big O Cost==

	If we use a data structure for the graph that implements the following operations with the specified big-O cost:		If we use a data structure for the graph that implements the following operations with the specified big-O cost:

Admin: /* What DFS Gets Us */

2017-09-09T12:04:27Z

What DFS Gets Us

← Older revision		Revision as of 12:04, 9 September 2017
Line 20:		Line 20:
	* Find the path between two given vertices, or report that none exists		* Find the path between two given vertices, or report that none exists
	* Test whether a graph is connected		* Test whether a graph is connected
	* Compute the spanning tree of a graph (which can, in turn, be used to bootstrap a [[Graphs/Minimum Spanning Tree~~\|minimum spanning tree~~]])		* Compute the spanning tree of a graph (which can, in turn, be used to bootstrap a minimum spanning tree): see [[Graphs/Minimum Spanning Tree]]
	* Find the connected components of a graph		* Find the connected components of a graph
	* Determine whether a graph has any cycles		* Determine whether a graph has any cycles
Line 31:		Line 31:
	* Test whether a graph is strongly connected		* Test whether a graph is strongly connected
	* Determine whether a graph has any cycles		* Determine whether a graph has any cycles
	* Compute the [[Graphs/Transitive Closure~~\|transitive closure~~]] ~~of a graph~~		* Compute the transitive closure of a graph: [[Graphs/Transitive Closure]]

	On a directed graph, to discover vertices reachable from a source vertex, do a DFS! To discover cycles, do a DFS and look for back-edges!		On a directed graph, to discover vertices reachable from a source vertex, do a DFS! To discover cycles, do a DFS and look for back-edges!