g topological sort Algorithm
The topological sort algorithm is a linear ordering algorithm used for directed graphs, specifically directed acyclic graphs (DAGs). It is designed to produce a linear sequence of vertices, such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. This ordering has various applications, including scheduling tasks with dependencies, determining the sequence of courses to take in a curriculum with prerequisites, and organizing build systems where some components must be compiled before others.
The algorithm works by first identifying vertices with no incoming edges, as they have no dependencies and can be processed first. These vertices are added to a set or a queue, and they are also added to the final topological sorted list. The algorithm then iterates through the set or queue, processing each vertex by removing its outgoing edges and decrementing the incoming degree of its adjacent vertices. If any adjacent vertex's incoming degree becomes zero, it is added to the set or queue for processing. The algorithm continues until all vertices have been processed and added to the sorted list. If there are still vertices with incoming edges remaining, this indicates that the graph is not a DAG, and a topological sort is not possible due to cycles in the graph.
# Author: Phyllipe Bezerra (https://github.com/pmba)
clothes = {
0: "underwear",
1: "pants",
2: "belt",
3: "suit",
4: "shoe",
5: "socks",
6: "shirt",
7: "tie",
8: "watch",
}
graph = [[1, 4], [2, 4], [3], [], [], [4], [2, 7], [3], []]
visited = [0 for x in range(len(graph))]
stack = []
def print_stack(stack, clothes):
order = 1
while stack:
current_clothing = stack.pop()
print(order, clothes[current_clothing])
order += 1
def depth_first_search(u, visited, graph):
visited[u] = 1
for v in graph[u]:
if not visited[v]:
depth_first_search(v, visited, graph)
stack.append(u)
def topological_sort(graph, visited):
for v in range(len(graph)):
if not visited[v]:
depth_first_search(v, visited, graph)
if __name__ == "__main__":
topological_sort(graph, visited)
print(stack)
print_stack(stack, clothes)
