Graph Edges in DFS
Have been supplied and referencing examples of Python code, this response will discuss transitive closure, topological ordering, and the categorisation of graph edges using Depth-First Search (DFS).
Transitive Closure
The transitive closure of a directed graph $\vec{G}$ is a new directed graph with the same set of vertices as $\vec{G}$, indicated as $\vec{G}^$. If a directed path from vertex $u$ to vertex $v$ in the original graph $\vec{G}$ exists, then $\vec{G}^$ has an edge $(u,v)$. Cases where $(u,v)$ is an existing edge in $\vec{G}$ are included in this.
The main reason for calculating the transitive closure is to provide effective answers to several reachability questions. Faster lookups following a precomputation phase are made possible by the transitive closure, as opposed to repeatedly executing graph traversals (such as DFS or BFS) for every query, which would take $O(n+m)$ time per query for an adjacency list/map representation.
The transitive closure can be calculated by doing a DFS or BFS traversal from each vertex in $\vec{G}$. If an adjacency list or map is used to represent $\vec{G}$, the temporal complexity of this method is $O(n(n+m))$.
Another approach is the Floyd-Warshall algorithm, which works especially well for networks that are represented by an adjacency matrix (where edge lookups take $O(1)$ time). This method calculates transitive closure by iteratively creating graphs $vecG k$. Starting with $\vec{G} 0 = \vec{G}$, $\vec{G}k$ is produced each round (from $1$ to $n$) by adding an edge $(v i, v j)$ if $\vec{G}{k-1}$ has both edges. For this strategy, $\vec{G} n$ equals $\vec{G}^*$ at the end of round $n$ if and only if there is a directed path from $v i$ to $v j$ with intermediate vertices from ${v 1, \ldots, v k}$. This means that it has an edge $(v i, v j)$.
Assuming $O(1)$ time for the lookup and update of adjacency information, the Floyd-Warshall method has a time complexity of $O(n^3)$. In reality, this is frequently faster because of simpler low-level operations, even if asymptotically it is no better than repeated DFS for sparse graphs employing an adjacency list/map. It performs as well as or better than repeated DFS in $O(n^3)$ for dense graphs or when an adjacency matrix is used.
The Floyd-Warshall algorithm is implemented in Python in Code Fragment 14.10. It computes the closure by copying the original graph and iteratively adding additional edges.
Topological Ordering
For a directed graph $\vec{G}$ with $n$ vertices, the topological ordering is a linear ordering of its vertices, where $i < j$ for each edge $(v i, v j)$. According to this ordering, any directed path in $\vec{G}$ will pass through vertices in ascending order. Several topological orderings are possible for a directed graph.
The fact that a directed graph $\vec{G}$ has a topological ordering only if it is acyclic—that is, devoid of directed cycles—is an important condition. As a cycle would imply an ordering $i 0 < i 1 < \dots < i {k-1} < i 0$, which is impossible, a network with topological order cannot have a cycle. It is possible to create a topological ordering if a graph is acyclic.
Topological sorting is an algorithm that takes advantage of this fact to compute a topological ordering. Finding a vertex with an in-degree of 0 (no incoming edges) and continually removing it is the main notion. Such a vertex $v 1$ is added to the ordering and its outgoing edges are eliminated if it exists. In order to find $v 2$, the procedure is then repeated on the remaining acyclic graph, and so on, until the graph is empty. In the event that the algorithm ends without ordering every vertex, a directed cycle is present.
The topological sorting algorithm requires $O(n)$ auxiliary space and executes in $O(n+m)$ time when using an adjacency list representation. Because every vertex is visited precisely once and every outgoing edge of a visited vertex is traversed once, this is the case.
In Code Fragment 14.11, the topological sorting algorithm is implemented in Python. In order to provide efficient $O(1)$ expected time access to the in-degree counts for each vertex, this implementation usually employs a dictionary to store the counts.
Python Code Example (Topological Sort – Pseudo-code concept):
def topological_sort(graph):
def dfs(node):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
stack.append(node)
visited = {node: False for node in graph}
stack = []
for node in graph:
if not visited[node]:
dfs(node)
return stack[::-1]
# Example DAG
graph = {
0: [1, 2],
1: [3],
2: [3],
3: []
}
order = topological_sort(graph)
print("Topological Order:", order)Output:
Topological Order: [0, 2, 1, 3]Classifying Graph Edges with DFS
Exploring a labyrinth using a string and paint is comparable to the graph traversal process known as Depth-First Search (DFS). One end of a string is fixed at $s$, and $s$ is marked as “visited,” beginning at a vertex $s$. We assume a random edge $(u,v)$ from vertex $u$. The edge is ignored if $v$ has been visited. If unvisited, $v$ becomes the current vertex, and the string is unrolled, visited, and tagged. The algorithm returns along the string to an earlier vertex with undiscovered edges when it hits a “dead end” where all incident edges lead to visited vertices. This method keeps on until there are no more undiscovered edges and backtracking returns to the start vertex.
Edges are categorised during a DFS traversal according to the manner in which they are investigated:
Discovery Edges (Tree Edges): Edges $(u,v)$ that are utilised to find a new (unvisited) vertex $v$ from a present vertex $u$ are known as discovery edges (sometimes called tree edges). With the root at the beginning vertex, these edges make up the DFS tree. The discovery edges in an undirected graph create a spanning tree of the linked component that contains the initial vertex. The DFS tree for a directed graph includes directed paths that connect each reachable vertex to the start vertex.
Nontree Edges: Any additional edges that lead to a previously visited vertex during DFS are referred to as nontree edges. For directed and undirected graphs, nontree edges are categorised differently:
- Undirected Graphs: An undirected graph has back edges for every nontree edge. In the DFS tree, a back edge joins the present vertex to one of its ancestors. A cycle is implied to exist in the graph when a back edge is present.
- Graphs that are directed can have nontree edges of one of three kinds.
Back Edges: Back edges are nontree edges found by graph traversal methods like Depth-First Search. Back edges are nontree connections that connect the current vertex to one of its DFS tree ancestors in an undirected graph. Back edges one of three nontree edges in directed graphs connect a vertex to an ancestor in the DFS tree. Back edges in undirected graphs are easier to find because all non-tree edges are classified.
Forward Edges: In Depth-First Search (DFS) on a directed graph, a “forward edge” is a nontree edge. Nontree edges lead to a previously visited vertex and are examined during DFS execution. A DFS tree forward edge connects a vertex to one of its descendants. A directed graph’s DFS can classify (DFW,ORD) or (BOS,SFO) as forward edges. Forward edges are not present in Breadth-First Search (BFS) for directed graphs, where all nontree edges are back or cross edges.
Cross Edges: Edges are characterised by their role in graph traversal, such as Depth-First Search (DFS) or Breadth-First Search (BFS). Unlike a discovery or tree edge, a “cross edge” connects a vertex to a previously visited vertex. In particular, a cross edge connects a vertex to another vertex that is neither its ancestor nor its descendent in a directed graph DFS. A directed DFS cross edge (SFO, LAX). For an undirected graph, BFS considers all nontree edges cross edges. Nontree edges in a directed graph undergoing BFS can be back or cross edges. This edge classification aids graph structure analysis.
While Figure 14.9 depicts a DFS example for an undirected graph, Figure 14.8 provides an example of DFS on a directed graph that demonstrates various edge types. In order to distinguish between ancestors and other previously visited vertices when an edge is studied, more bookkeeping is needed when using DFS to detect cycles in a directed graph.
Code Fragment 14.5 demonstrates the generic DFS algorithm in Python, which tracks visited vertices and the edges that lead to their discovery using a dictionary called “discovered.”
Python Code Example (DFS – Pseudo-code concept):
def dfs(graph, node, visited):
visited[node] = True
traversal.append(node)
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
# Example Graph
graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
}
visited = {node: False for node in graph}
traversal = []
# Perform DFS starting from node 0
dfs(graph, 0, visited)
print("DFS Traversal Order:", traversal)Output:
DFS Traversal Order: [0, 1, 2, 3]