# Topologial Sort in Python

I am trying to self study algorithms and this is my attempt at topological sort using Tarjan's version of DFS. It runs correctly for the graph I included. Can someone tell me if this is correct and if/what optimizations I can make?

graph = {
'A':['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['F'],
'F': ['G'],
'G': [],
}

def topological_sort(graph):
visited, stack = set(), []

for vertex in graph:
handle_vertex(graph, vertex, visited, stack)

print(stack)

def handle_vertex(graph, vertex, visited, stack):
if vertex not in visited:

for neighbors in graph[vertex]:
if neighbors not in visited:
handle_vertex(graph, neighbors, visited, stack)

if vertex not in stack:
stack.insert(0, vertex)
return stack

print(topological_sort(graph))

• Do you only have one test case? Does the code work correctly for other test cases? – Phrancis Dec 2 '16 at 23:27
• @Phrancis it also works for the test case: graph2={ 0 : [], 1: [], 2: , 3: , 4: [0, 1], 5: [2, 0] } – driftdrift Dec 2 '16 at 23:36
• Excuse my ignorance, but can you please explain what's the output you expect for the graph in the code ? More, could you please add more context to what your code does ? Having some recursion going on there doesn't help :). PS: for example, when I'm testing you're first graph, I receive different outputs at every run, so I suspect your code as being broken. – Grajdeanu Alex Dec 3 '16 at 6:11
• @Dex'ter A topological sort returns things in order, where given an edge U->V in a graph, U always comes before V. – driftdrift Dec 3 '16 at 15:48

1. I don't get the point of returning the stack from the handle_vertex function. The return value is never used (and the stack which is passed as an argument is modified in place).
2. The topological_sort functions prints the stack, doesn't return anything and then it's returned value is printed: print(topological_sort(graph)). There're two reasonable options here:
• not printing the returned value of the topological_sort and just calling it instead
• Returning the stack from it instead of printing it inside the function.
3. The neighbors name here: for neighbors in graph[vertex] is misleading. This variable represent just one neighbor at a time. I don't see why would you make it plural.