Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Alphabet
python, attributes, setter and getter the pythonic way (V2)
hw11
Python3 - product lists
sai hw user table for loop
Tuple_Exercise1_solution
Faiha Lesson 1, 2020: Python Basics
Random module
Reverse function
shuru8