3. Graph Traversals

BFS for connected and disconnected graph¶

• Disconnected graph: https://www.geeksforgeeks.org/bfs-disconnected-graph/?ref=lbp

In [1]:

from collections import defaultdict
from utils.graph_traversal import GraphTraversal as gt

from collections import defaultdict from utils.graph_traversal import GraphTraversal as gt

In [2]:

class Graph:
    def __init__(self) -> None:
        # dictionary of list
        self.graph = defaultdict(list)
        self.test = []

    def insert_node(self, vertex, data):
        self.graph[vertex].append(data)

    def print_graph(self):
        for k, v in self.graph.items():
            print(f"{k}: {v}")

class Graph: def __init__(self) -> None: # dictionary of list self.graph = defaultdict(list) self.test = [] def insert_node(self, vertex, data): self.graph[vertex].append(data) def print_graph(self): for k, v in self.graph.items(): print(f"{k}: {v}")

In [3]:

g = Graph()
g.insert_node(0, 1)
g.insert_node(0, 2)
g.insert_node(1, 2)
g.insert_node(2, 0)
g.insert_node(2, 3)
g.insert_node(3, 3)

g = Graph() g.insert_node(0, 1) g.insert_node(0, 2) g.insert_node(1, 2) g.insert_node(2, 0) g.insert_node(2, 3) g.insert_node(3, 3)

In [4]:

# g = Graph()
# g.insert_node(0, 1)
# g.insert_node(0, 6)
# g.insert_node(1, 2)
# g.insert_node(1, 5)
# g.insert_node(2, 3)
# g.insert_node(2, 8)
# g.insert_node(3, 4)
# g.insert_node(4, 4)
# g.insert_node(5, 6)
# g.insert_node(5, 8)
# g.insert_node(6, 0)
# g.insert_node(6, 7)
# g.insert_node(7, 8)
# g.insert_node(8, 2)
# g.insert_node(8, 3)
# g.insert_node(8, 4)

# g = Graph() # g.insert_node(0, 1) # g.insert_node(0, 6) # g.insert_node(1, 2) # g.insert_node(1, 5) # g.insert_node(2, 3) # g.insert_node(2, 8) # g.insert_node(3, 4) # g.insert_node(4, 4) # g.insert_node(5, 6) # g.insert_node(5, 8) # g.insert_node(6, 0) # g.insert_node(6, 7) # g.insert_node(7, 8) # g.insert_node(8, 2) # g.insert_node(8, 3) # g.insert_node(8, 4)

In [5]:

g.print_graph()

g.print_graph()

0: [1, 2]
1: [2]
2: [0, 3]
3: [3]

In [6]:

gt.BFS(g.graph, start_idx=2)

gt.BFS(g.graph, start_idx=2)

2
0
3
1

In [7]:

gt.BFS_disconnected_graph(g.graph)

gt.BFS_disconnected_graph(g.graph)

0
1
2
3

In [8]:

gt.DFS(g.graph, vertex=2)

gt.DFS(g.graph, vertex=2)

2
0
1
3

In [9]:

gt.DFS_disconnected_graph(g.graph)

gt.DFS_disconnected_graph(g.graph)

0
1
2
3