Python_DSA/Graphs.py at master · AB00k/Python_DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#Lesson no: 30
#Graphs

class Graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict={}
        self.gdict=gdict

    def addedge(self,vertex,edge):
        self.gdict[vertex].append(edge)

    def bfs(self,vertex):
        visited=[vertex]
        queue=[vertex]
        while queue:
            dvertex=queue.pop(0)
            print(dvertex)
            for adjacentvertex in self.gdict[dvertex]:
                if adjacentvertex not in visited:
                    visited.append(adjacentvertex)
                    queue.append(adjacentvertex)
    def dfs(self,vertex):
        visited=[vertex]
        stack=[vertex]
        while stack:
            dvertex=stack.pop()
            print(dvertex)
            for adjacentvertex in self.gdict[dvertex]:
                if adjacentvertex not in visited:
                    visited.append(adjacentvertex)
                    stack.append(adjacentvertex)

dict={'a':['b','c'],
      'b':['a','e','d'],
      'c':['a','e'],
      'd':['b','f'],
      'e':['b','c','f'],
      'f':['d','e']}

graph=Graph(dict)
graph.dfs('a')