# How do I use this depth first search code to obtain a topological sort?

Problem: I need to implement a topological search using the following depth first search code.

Note: The original code comes from here, and this is a problem given in at the end of the chapter.

I'll be honest. On a coding level, I feel pretty lost. I've added line comments to help show what I think each line is doing. While I'm fairly new to the depth first search, I understand how they work on a functional level (as opposed to my limited knowledge of their implementation). I've attempted to add the start vertices and finish times to a list so that I could then sort them later on, but I've had trouble returning that list. So that I could then sort the vertices in decreasing order of finishing time.

Note that while some solutions seem to use a stack, this code does not state the use of a stack explicitly. Rather, the stack is implicit in the recursive call to dfsvisit.

from pythonds.graphs import Graph
# Definitions
# discovery time == iterations it took for the program to find the vertex and turn it gray
# finish time == iterations it took for the program to turn the vertex black
# pred == predecessor indicator

class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0                       # self has an attribute 'time' (counter) that initiates at 0

def dfs(self):
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)

def print_graph(self):
for key in sorted(list(self.vertices.keys())):
print(key + str(self.vertices[key].neighbors + " " + str(self.vertices[key].dis)))

def dfsvisit(self,startVertex):                     # Initiate the visit vunction of the current object (self) at the starting vertex (startVertex)
finish_times = []                                       # Instantiate the a list to keep finish times for each node
startVertex.setColor('gray')                    # Set the color of the starting vertex to 'gray' (discovered)
self.time += 1                                  # Increment the timer
startVertex.setDiscovery(self.time)             # Assign the discovery time to the current vertex (startVertex)
for nextVertex in startVertex.getConnections(): # Begin cycling through the connected vertices (nextVertex) of startVertex
if nextVertex.getColor() == 'white':        # If a vertex (nextVertex) with the attribute color of white is found, then do the following:
nextVertex.setPred(startVertex)         # Set the predecessor indicator of the next vertex as the current vertex (ie if B is white and connected to A, set B's predecessor as A)
self.dfsvisit(nextVertex)               # Recursively calls itself with the next vertex until the color of the next vertex is no longer white (i.e. all have been explored)
startVertex.setColor('black')                   # Set the current vertice's color to black (explored)
self.time += 1                                  # Increment the timec counter
startVertex.setFinish(self.time)                # Assign the finish time to the current vertex (startVertex)
finish_time = [startVertex, startVertex.setFinish(self.time)]  # append vertex and finish times to finish_time list
return finish_time                                             # return the finish_time list


Again, I'm hoping to understand how to implement the topological search either within this code.

• Do you mean topological sort? Sep 2, 2019 at 22:12
• "End of the chapter" of what? Sep 2, 2019 at 22:12
• My apologies @BrianSpiering. Yes, topological sort, and the 'end of chapter' referred to this link that didn't copy over for me. Sep 2, 2019 at 22:38

It appears to me that you are doing too much with the code. For DFS, visit every node following adjacent nodes. As you do that, track the topological ordering.

Here is a straightforward implementation of recursive topological sorting a DAG in Python:

from collections import defaultdict

class Graph:

def __init__(self):
self.graph = defaultdict(list) # Node: [adjacency nodes]
self.nodes = set()

"Directed edge from vertex u to vertex v"
self.graph[u].append(v)

def mark_as_visited(self, v, visited, topological_ordering):
visited[v] = True

# Recur for all the vertices adjacent to this vertex
for current_vertex in self.graph[v]:
if visited[current_vertex] == False:
self.mark_as_visited(current_vertex, visited, topological_ordering)

topological_ordering.insert(0, v)

def topological_sort(self):

visited = [False]*len(self.nodes) # Mark all the vertices as not visited
topological_ordering = []

# Sort starting from all vertices one by one
for i in range(len(self.nodes)):
if visited[i] == False:
self.mark_as_visited(i, visited, topological_ordering)


# Create a sample DAG
g = Graph()