Depth First Search - Find path, Python 3

Depth First Search - Find path

"""
Depth First Search
Finding path if it exists, between two points in graph

Author: Jayesh Chandrapal
"""

def readGraph():
    graph = {}
    
    N = int(input())
    
    for i in range(N):
        line = input()
        tokens = line.split()
        
        node = tokens[0]
        graph[node] = {}

for i in range(1, len(tokens) - 1, 2):
            graph[node][tokens[i]] = int(tokens[i + 1])
    
    return graph

def __findPathDFS(graph, current, goal, visited):
    if current == goal:
        return [current]
    
    if current in graph:
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add( neighbor )
                path = __findPathDFS(graph, neighbor, goal, visited)
                
                if path is not None:
                    path.insert(0, current)
                    return path

return None
    
def findPathDFS(graph, start, goal):
    if start not in graph or goal not in graph:
        return False
    
    visited = set()
    visited.add( start )
    
    return __findPathDFS(graph, start, goal, visited)
    
graph = readGraph()

print( findPathDFS(graph, 'Arad', 'Bucharest') )


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development