Skills for tackling LeetCode problems - Topological Sort (Graph).
Topological Sort is used to find a linear ordering of elements that have dependencies on each other. Source is any node that has no incoming edge and has only outgoing edges. Sink is any node that has only incoming edges and no outgoing edge. A topological ordering starts with one of the sources and ends at one of the sinks, and it’s only possible when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG).
1. Topological Sort
Topological Sort of a directed graph (a graph with undirectional edges) is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex V, U comes before V in the ordering. Given a directed graph, find the topological ordering of its vertices.
We can traverse the graph in a BFS way. We use a HashMap to count the in-degrees of each vertex, any vertex with 0 in-degree will be a source. Then we store the source into a Queue. For each source, we do 1) add it to the sorted list, 2) get all its children from the graph, 3) decrease the in degree of each child by 1, 4) if a child’s in-degree becomes 0, add it to the sources Queue, until the source Queue is empty.
# Time complexity O(V + E). Since each vertex will be a source only once and each edge will be accessed and removed once.
# Space complexity O(V + E). Since we store all edges for each vertex in an adjacency list.
from collections import deque
def topological_sort(vertices, edges):
sortedList = []
if vertices <= 0:
return sortedList
inDegree = {i: 0 for i in range(vertices)} # count in-degrees of all vertices
graph = {i: [] for i in range(vertices)} # store all children of each vertex - "adjacency list"
for edge in edges:
parent, child = edge[0], edge[1]
graph[parent].append(child)
inDegree[child] += 1 # number of children = number directed edges
sources = deque()
for key in inDegree:
if inDegree[key] == 0: # find the source
sources.append(key)
while sources:
vertex = sources.popleft()
sortedList.append(vertex)
for child in graph[vertex]:
inDegree[child] -= 1 # pop out the source, delete all edges connect to it
if inDegree[child] == 0: # any child becomes a source
sources.append(child)
# topological sort is not possible if the graph ahs a cycle
if len(sortedList) != vertices:
return []
return sortedList
2. Tasks Scheduling
There are N tasks, labeled from 0 to N-1. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pair, find out if it is possible to schedule all the tasks.
# Time complexity O(V + E). Space complexity O(V + E).
def is_scheduling_possible(tasks, prerequisites):
sortedList = []
if tasks <= 0:
return False
inDegree = {i: 0 for i in range(tasks)} # count incoming edges for each vertex
graph = {i: [] for i in range(tasks)} # adjacency list
for pre in prerequisites:
parent, child = pre[0], pre[1]
graph[parent].append(child) # construct the graph
inDegree[child] += 1 # count edges for each child, sources have 0 count
sources = deque()
for key in inDegree:
if inDegree[key] == 0: # find sources
sources.append(key)
while sources:
vertex = sources.popleft()
sortedList.append(vertex)
for child in graph[vertex]:
inDegree[child] -= 1 # remove the source, then any edges connect to the source are removed
if inDegree[child] == 0: # find the next source
sources.append(child)
# if false, there is a cyclic dependency between tasks
return len(sortedList) == tasks
3. Tasks Scheduling Order
There are N tasks, labeled from 0 to N-1. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, write a method to find the ordering of tasks we should pick to finish all tasks.
# Time complexity O(V + E). Space complexity O(V + E).
def find_order(tasks, prerequisites):
sortedList = []
if tasks <= 0:
return False
inDegree = {i: 0 for i in range(tasks)}
graph = {i: [] for i in range(tasks)}
for pre in prerequisites:
parent, child = pre[0], pre[1]
graph[parent].append(child)
inDegree[child] += 1
sources = deque()
for key in inDegree:
if inDegree[key] == 0:
sources.append(key)
while sources:
vertex = sources.popleft()
sortedList.append(vertex)
for child in graph[vertex]:
inDegree[child] -= 1
if inDegree[child] == 0:
sources.append(child)
if len(sortedList) != tasks:
return []
return sortedList
4. All Tasks Scheduling Orders
There are N tasks, labeled from 0 to N-1. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, write a method to print all possible ordering of tasks meeting all prerequisites.
At any stage, if we have more than one source available and since we can choose any source, therefore, in this case, we will have multiple orderings of the tasks. We can use a recursive approach with backtracking to consider all sources ay any step.
# Time complexity O(V! * E). Space complexity O(V! * E).
# V is the total number of tasks and E is the total prerequisites. There can be V! combination for N numbers, and removing all edges in recursive call takes O(E).
def print_orders(tasks, prerequisites):
sortedList = []
if tasks <= 0:
return False
inDegree = {i: 0 for i in range(tasks)}
graph = {i: [] for i in range(tasks)}
for pre in prerequisites:
parent, child = pre[0], pre[1]
graph[parent].append(child)
inDegree[child] += 1
sources = deque()
for key in inDegree:
if inDegree[key] == 0: # find the source
sources.append(key)
recursion(graph, inDegree, sources, sortedList)
def recursion(graph, inDegree, sources, sortedList):
if sources:
for vertex in sources:
## condition1: append current vertex into the sortedList
sortedList.append(vertex)
copy = deque(sources) # make a copy of source
copy.remove(vertex)
for child in graph[vertex]:
inDegree[child] -= 1
if inDegree[child] == 0:
copy.append(child)
# recursive call to print other ordering from thet remaining sources
recursion(graph, inDegree, copy, sortedList)
## condition2: backtrack
sortedList.remove(vertex) # do not remove
for child in graph[vertex]:
inDegree[child] += 1 # get teh in-degrees back
if len(sortedList) == len(inDegree):
print(sortedList)
