Created
August 4, 2018 02:31
-
-
Save otaviomguerra/034f5e8ce4f70a81370a6d7879b4d371 to your computer and use it in GitHub Desktop.
BFS algorithm implemented with networkx library
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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