I've created a Node class and a Graph class
class Node:
def __init__(self, val):
self.val = val
self.edges = []
class Graph:
def __init__(self, nodes=[]):
self.nodes = nodes
def add_node(self, val):
newNode = Node(val)
self.nodes.append(newNode)
def add_edge(self, node1, node2):
node1.edges.append(node2)
node2.edges.append(node1)
I have also added functions to the Graph class for performing breadth first search and depth first search on a given graph.
def bfs(self):
if self.nodes is None:
return []
visited, toVisit = [], [self.nodes[0]]
while toVisit:
node = toVisit.pop()
visited.append(node)
print(node.val)
for nd in node.edges:
if nd not in visited and nd not in toVisit:
toVisit.insert(0,nd)
return visited
def dfs(self):
if self.nodes is None:
return []
visited, toVisit = [], [self.nodes[0]]
while toVisit:
node = toVisit.pop()
visited.append(node)
print(node.val)
for nd in node.edges:
if nd not in visited and nd not in toVisit:
toVisit.append(nd)
return visited
Here is an example implementation
graph = Graph()
graph.add_node(5)
graph.add_node(3)
graph.add_node(8)
graph.add_node(1)
graph.add_node(9)
graph.add_node(2)
graph.add_node(10)
# 2
# /
# 5 - 3 - 8 - 9 - 10
# \ /
# 1
graph.add_edge(graph.nodes[0], graph.nodes[1])
graph.add_edge(graph.nodes[0], graph.nodes[3])
graph.add_edge(graph.nodes[1], graph.nodes[2])
graph.add_edge(graph.nodes[0], graph.nodes[1])
graph.add_edge(graph.nodes[2], graph.nodes[3])
graph.add_edge(graph.nodes[2], graph.nodes[5])
graph.add_edge(graph.nodes[2], graph.nodes[4])
graph.add_edge(graph.nodes[4], graph.nodes[6])
graph.dfs()
graph.bfs()
The depth first search returns 5,1,8,9,10,2,3
The breadth first search returns 5,3,1,8,2,9,10
From what I can tell, this is a correct implementation. However, I'm curious if there are more efficient ways to do some of these things. Or maybe ways that make more logical sense. For example, am I storing the edge list in a reasonable way? Is this generic enough that it could easily be extended to work with directed vs undirected graphs? Any feedback would be much appreciated.