CODEWITHSUNDEEP
pythonalgorithmsortinggraphdepth-first-search
William Merritt
William Merritt

Reputation: 439

Why does my DFS sorting algorithm ignore my graph?

I have the code below to perform a DFS sort on a directed graph (Topological sort, no cycles)

def dfs_recursive(graph, vertex, path=[]):
    path += [vertex]
    for neighbor in graph[vertex]:
        if neighbor not in path:
            path = dfs_recursive(graph, neighbor, path)
    return path

Yet every time I run the function with my directed graph it returns a graph with numerous cycles dfs_recursive(graph1, 'Comp Sci')

> ['Comp Sci', 'Structures', 'Algebra', 'COB', 'Digital Design', 'Compilers', 'GPU', 'Networking']

This is ran with the following Directed Graph:

graph1 =  {
    'Digital Design': ['COB', 'Compilers'], 
    'Structures': ['Algebra', 'Digital Design'], 
    'Creative Writing': ['Structures', 'System Admin', 'Databases'], 
    'Algebra': ['COB'], 
    'Comp Sci': ['Structures', 'GPU'], 
    'GPU': ['Networking'], 
    'Networking': ['Algebra'], 
    'Databases': ['System Admin'],
    'COB': [],
    'System Admin': [],
    'Compilers': []
    }

As shown, when working correctly, the function should return > ['Comp Sci', 'Structures', 'Algebra', 'COB'] as there shouldn't be any additional connections. ('COB' does not have any nodes in my Adjacency List, should only go in one direction)

Am I missing something? Is my Directed Graph incorrect? I'm only referencing the nodes in a single direction yet there are random cycles that I can't explain.

Upvotes: 0

Views: 65

Answers (1)

Dillon Davis
Dillon Davis

Reputation: 7750

Let me put the issue into another perspective. Forget about graphs for a second, lets say we're sorting numbers, and we're using Merge Sort. We split our list into multiple segments, and sort these segments recursively, and then concatenate the results, and return. Did you catch the issue there? Maybe we sorted [2, 4, 6] and [1, 3, 5] recursively, but then we just concatenated those for [2, 4, 6, 1, 3, 5] and returned, which is incorrect. We forgot about the relationships between elements in our recursive sorts; we forgot to merge!

You're facing a very similar problem in your topological sort. You sort each sub-DAG correctly, but then you just concatenate the lists, forgetting about any possible edges between them. You can trigger this edge case with a mere 3 nodes- A->C, A->B, B->C. If you recurse into C before B, you'll end up with [A, C, B].

Upvotes: 2

Related Questions