DFS - Revision history

Rice: /* Implementation */

2024-03-20T06:35:07Z

Implementation

← Older revision		Revision as of 06:35, 20 March 2024
Line 12:		Line 12:
	# This continues until every node is black.		# This continues until every node is black.

	== Implementation ==		= Implementation =

	<pre>		<pre>
	DFS_visit(u) {		DFS_visit(u) {
Line 27:		Line 26:
	}		}
	</pre>		</pre>

			= Analysis =
			Since DFS is only called when a node is white, and a node is marked as grey immediately afterwards, DFS is called ''V'' times.

			In each call, everything is completed in constant time, except the process of iterating the outgoing edges of that node. Over all iterations, that comes down to ''E'' times since that is the total number of edges.

			Therefore, under the normal implementation of DFS, the runtime complexity is O(V + E).

			== Adjacency lists ==
			Realistically, the only real change on the runtime would be using something other than adjacency lists to store the graph, in which case the time it takes to search for edges needs to be taken into account. For example, an adjacency matrix would take O(V^2), which is the time it takes to iterate through all the edges.

	= Variations and Applications =		= Variations and Applications =

Rice: /* Edge classification and cycle detection */

2024-03-20T06:26:43Z

Edge classification and cycle detection

← Older revision		Revision as of 06:26, 20 March 2024
Line 35:		Line 35:
	* If the node is ''white'' (unvisited), the edge is called a '''tree edge'''. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected).		* If the node is ''white'' (unvisited), the edge is called a '''tree edge'''. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected).
	* If the node is ''grey'' (visiting), the edge is called a '''back edge'''. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a '''cycle'''.		* If the node is ''grey'' (visiting), the edge is called a '''back edge'''. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a '''cycle'''.
	* If the node is ''black'' (visited), the edge is ~~called~~ a '''cross edge'''~~. They "cross" from one branch to another, neither being in the tree nor creating a cycle~~. I~~'ve~~ not ~~really~~ seen ~~any~~ uses for ~~this yet~~.		* If the node is ''black'' (visited), the edge is either a '''forward edge''' or a '''cross edge'''. I have not seen uses for these.

	== Entry time and exit time ==		== Entry time and exit time ==

Rice: /* Edge classification and cycle detection */

2024-03-20T06:24:58Z

Edge classification and cycle detection

← Older revision		Revision as of 06:24, 20 March 2024
Line 35:		Line 35:
	* If the node is ''white'' (unvisited), the edge is called a '''tree edge'''. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected).		* If the node is ''white'' (unvisited), the edge is called a '''tree edge'''. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected).
	* If the node is ''grey'' (visiting), the edge is called a '''back edge'''. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a '''cycle'''.		* If the node is ''grey'' (visiting), the edge is called a '''back edge'''. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a '''cycle'''.
	* If the node is ''black'' (visited), the edge is called a '''cross edge'''. They "cross" from one branch to another, neither being in the tree nor creating a cycle.		* If the node is ''black'' (visited), the edge is called a '''cross edge'''. They "cross" from one branch to another, neither being in the tree nor creating a cycle. I've not really seen any uses for this yet.

	== Entry time and exit time ==		== Entry time and exit time ==

Rice at 06:23, 20 March 2024

2024-03-20T06:23:41Z

← Older revision		Revision as of 06:23, 20 March 2024
Line 28:		Line 28:
	</pre>		</pre>

	= ~~Other~~ Applications =		= Variations and Applications =

	== Edge classification and cycle detection ==		== Edge classification and cycle detection ==
Line 38:		Line 38:

	== Entry time and exit time ==		== Entry time and exit time ==
	~~Keeping~~ track of the ~~order in which DFS enter~~ and exit nodes ~~can solve problems such~~ as '''topological sort'''.		An addition to DFS keeps track of the '''entry time''' and '''exit time''' of nodes: that is, it keeps an ordering of when nodes are marked as grey/black. An index is used to keep track of this, incrementing every time a node's color change.

			This is useful primarily for '''topological sort'''. A strategy for this problem involves DFS-ing the graph and sorting the nodes by exit times.
	[[Category:Algorithms]]		[[Category:Algorithms]]

Rice: /* DFS */

2024-03-20T06:20:24Z

DFS

← Older revision		Revision as of 06:20, 20 March 2024
Line 1:		Line 1:
	{{Infobox Algorithm\|runtime=O(V + E)\|space=O(V)\|class=[[Graph Algorithms]]}}		{{Infobox Algorithm\|runtime=O(V + E)\|space=O(V)\|class=[[Graph Algorithms]]}}

	~~= DFS =~~		'''Depth-first search''' is a graph traversal algorithm.

	~~Used for cycle detection~~		= Approach =
			The basic idea of DFS is to visit ''every child'' of the visiting node before moving on to the next unvisited node.

	~~Test link to another page: [[First_Page]]~~		# Every node besides one start out being unvisited (''white'').
			# DFS begin by visiting a source node. Upon entering a node, DFS marks it as visiting (''grey'').
			# DFS then visits all of its child nodes.
			# After it has visited all children of a grey node, it marks the visiting parent node as visited (''black'').
			# This continues until every node is black.

	== Implementation ==		== Implementation ==
Line 23:		Line 28:
	</pre>		</pre>

			= Other Applications =

			== Edge classification and cycle detection ==
			DFS can classify edges based on the color of the node it is visiting.

			* If the node is ''white'' (unvisited), the edge is called a '''tree edge'''. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected).
			* If the node is ''grey'' (visiting), the edge is called a '''back edge'''. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a '''cycle'''.
			* If the node is ''black'' (visited), the edge is called a '''cross edge'''. They "cross" from one branch to another, neither being in the tree nor creating a cycle.

			== Entry time and exit time ==
			Keeping track of the order in which DFS enter and exit nodes can solve problems such as '''topological sort'''.
	[[Category:Algorithms]]		[[Category:Algorithms]]

Rice at 23:34, 5 March 2024

2024-03-05T23:34:37Z

← Older revision		Revision as of 23:34, 5 March 2024
Line 1:		Line 1:
			{{Infobox Algorithm\|runtime=O(V + E)\|space=O(V)\|class=[[Graph Algorithms]]}}

	= DFS =		= DFS =

Admin at 03:36, 5 March 2024

2024-03-05T03:36:44Z

← Older revision		Revision as of 03:36, 5 March 2024
Line 20:		Line 20:
	}		}
	</pre>		</pre>

			[[Category:Algorithms]]

Rice at 01:15, 28 February 2024

2024-02-28T01:15:14Z

← Older revision		Revision as of 01:15, 28 February 2024
Line 7:		Line 7:
	== Implementation ==		== Implementation ==

	<~~code~~>		<pre>
	DFS_visit(u) {		DFS_visit(u) {
	time = time + 1		time = time + 1
Line 19:		Line 19:
	color[u] = black		color[u] = black
	}		}
	</~~code~~>		</pre>

Rice at 01:15, 28 February 2024

2024-02-28T01:15:03Z

← Older revision		Revision as of 01:15, 28 February 2024
Line 8:		Line 8:

	<code>		<code>
	DFS_visit(u) {		DFS_visit(u) {
	time = time + 1		time = time + 1
	d[u] = time		d[u] = time
	color[u] = 'grey'		color[u] = 'grey'
	for each v in adj[u] {		for each v in adj[u] {
	if color[u] == white		if color[u] == white
	DFS_visit(u)		DFS_visit(u)
	}		}
	f[u] = time++		f[u] = time++
	color[u] = black		color[u] = black
	}		}
	</code>		</code>

Rice at 01:14, 28 February 2024

2024-02-28T01:14:16Z

← Older revision		Revision as of 01:14, 28 February 2024
Line 8:		Line 8:

	<code>		<code>
	DFS_visit(u) {		DFS_visit(u) {
	time = time + 1		time = time + 1
	d[u] = time		d[u] = time
	color[u] = 'grey'		color[u] = 'grey'
	for each v in adj[u] {		for each v in adj[u] {
	if color[u] == white		if color[u] == white
	DFS_visit(u)		DFS_visit(u)
			}
			f[u] = time++
			color[u] = black
	}		}
	~~f[u] = time++~~
	~~color[u] = black~~
	}
	</code>		</code>