Graphs/Cycles - Revision history

Admin: /* Detecting Cycles on Undirected Graphs */

2017-09-09T09:06:56Z

Detecting Cycles on Undirected Graphs

← Older revision		Revision as of 09:06, 9 September 2017
Line 16:		Line 16:

	To classify each edge, when visiting a vertex u, iterate through each edge that is incident to the vertex. If the opposite vertex has already been visited, the edge is a back edge. Otherwise, the edge is a DFS tree edge.		To classify each edge, when visiting a vertex u, iterate through each edge that is incident to the vertex. If the opposite vertex has already been visited, the edge is a back edge. Otherwise, the edge is a DFS tree edge.

			<pre>
			// "visited" is a list of visited vertices
			def is_node_in_cycle(s, visited):
			if s not in visited:
			mark current node as visited
			// recur for all vertices:
			for each neighbor v of s:
			if v in visited:
			return true
			return false


			def is_graph_cyclic(g):
			initialize visited as empty list
			initialize path_stack as empty
			for each vertex v in g:
			if is_node_in_cycle(v, visited, path_stack):
			return true
			return false
			</pre>

	===Detecting Cycles on Directed Graphs===		===Detecting Cycles on Directed Graphs===

Admin: /* Detecting Cycles on Directed Graphs */

2017-09-09T09:03:35Z

Detecting Cycles on Directed Graphs

@@ Line 22: / Line 22: @@
 To do this, additional bookkeeping is needed for the DFS. The DFS must keep track of the vertices that are actively a part of the current recursive DFS call.
 =Flags=
 {{GraphsFlag}}

Admin: Created page with "=Notes= ==Detecting Cycles== Cycles can exist and be detected on either directed or undirected graphs. For both types of graphs, a cycle exists if and only if there is a ba..."

2017-09-09T08:34:37Z

Created page with "=Notes= ==Detecting Cycles== Cycles can exist and be detected on either directed or undirected graphs. For both types of graphs, a cycle exists if and only if there is a ba..."

New page

=Notes=

==Detecting Cycles==

Cycles can exist and be detected on either directed or undirected graphs.

For both types of graphs, a cycle exists if and only if there is a back edge on the graph. To detect a cycle, then, requires a depth-first search (see [[Graphs/DFS]]) and marking any back edges. If there are any back edges, the cycle exists.

==Algorithm==

To algorithmically find a back edge, we should consider undirected and directed graphs separately.

===Detecting Cycles on Undirected Graphs===

This is the easier case - each edge can be classified as either an edge that is part of the DFS tree, or a back edge. (There are no cross-edges in an undirected graph.)

To classify each edge, when visiting a vertex u, iterate through each edge that is incident to the vertex. If the opposite vertex has already been visited, the edge is a back edge. Otherwise, the edge is a DFS tree edge.

===Detecting Cycles on Directed Graphs===

For directed graphs, when visiting a vertex u, iterate through each outgoing edge that is incident to the vertex. If the opposite vertex has already been visited, we must determine if it is an ancestor of the current vertex (making it a back edge, and forming a cycle), or whether it is a cross edge (which connects to a vertex that is neither an ancestor nor a descendant, and not forming a cycle).

To do this, additional bookkeeping is needed for the DFS. The DFS must keep track of the vertices that are actively a part of the current recursive DFS call.

=Flags=

{{GraphsFlag}}