Skip to content

Instantly share code, notes, and snippets.

@otaviomguerra
Created August 4, 2018 02:31
Show Gist options
  • Save otaviomguerra/034f5e8ce4f70a81370a6d7879b4d371 to your computer and use it in GitHub Desktop.
Save otaviomguerra/034f5e8ce4f70a81370a6d7879b4d371 to your computer and use it in GitHub Desktop.
BFS algorithm implemented with networkx library
import networkx as nx
def path_exists(G, node1, node2):
"""
This function checks whether a path exists between two nodes (node1, node2) in graph G.
"""
visited_nodes = set()
queue = [node1]
for node in queue:
neighbors = G.neighbors(node)
if node2 in neighbors:
print('Path exists between nodes {0} and {1}'.format(node1, node2))
return True
break
else:
visited_nodes.add(node)
queue.extend([n for n in neighbors if n not in visited_nodes])
# Check to see if the final element of the queue has been reached
if node == queue[-1]:
print('Path does not exist between nodes {0} and {1}'.format(node1, node2))
# Place the appropriate return statement
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment