Aside from DFS and BFS, the most common graph concept that interviews will test is topological sorting. Topological sorting produces a linear ordering of nodes in a directed graph such that the direction of edges is respected.
A topological sort is an ordering of nodes for a directed acyclic graph (DAG) such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
An application of this algorithm is ordering a sequence of tasks given their dependencies on other tasks. In this application, there is a directed edge from u to v if task u must be completed before task v can start. For example, when cooking, we need to turn on the oven (task u) before we can bake the cookies (task v).
Topological sort is simply a modification of DFS. Topological sort simply involves running DFS on an entire graph and adding each node to the global ordering of nodes, but only after all of a node's children are visited. This ensures that parent nodes will be ordered before their child nodes, and honors the forward direction of edges in the ordering.
from collections import deque
def top_sort(graph):
sorted_nodes, visited = deque(), set()
for node in graph.keys():
if node not in visited:
dfs(graph, node, visited, sorted_nodes)
return list(sorted_nodes)
def dfs(graph, start_node, visited, sorted_nodes):
visited.add(start_node)
if start_node in graph:
neighbors = graph[start_node]
for neighbor in neighbors:
if neighbor not in visited:
dfs(graph, neighbor, visited, sorted_nodes)
sorted_nodes.appendleft(start_node)