-
Bertrand Néron authored
this second implementation implement graph with reachability list
Bertrand Néron authoredthis second implementation implement graph with reachability list
main_2.py 908 B
from graph.graph_2 import NDGraph, Node, BFS, DFS
# We want to create a toy graph (not directed) to check our algos
# no
# / \
# n1 n3
# | |
# n2 n4
# \ /
# n5
nodes = [Node() for _ in range(6)]
g = NDGraph(nodes)
g.add_edge(nodes[0], (nodes[1], nodes[3]))
g.add_edge(nodes[1], (nodes[2],))
g.add_edge(nodes[2], (nodes[5],))
g.add_edge(nodes[3], (nodes[4],))
g.add_edge(nodes[4], (nodes[5],))
# The graph is created we will test
# a Depth First Search
# starting from n0
# the possible solutions are
# n0, n1,n2,n5,n4,n3
# n0, n3, n4, n5, n2, n1
print("DFS")
for n in DFS(g, nodes[0]):
print(n.id)
# a Breadth First Search
# starting n0
# the possible solutions are
# n0, n1, n3, n2, n4, n5
# n0, n3, n1, n2, n4, n5
# n0, n1, n3, n4, n2, n5
# ....
print("BFS")
for n in BFS(g, nodes[0]):
print(n.id)