DataStructure: Graph

Graph Notes ### Main Points 1. Nodes * Fundamental unit is called Nod 2. Edges * Nodes are connected with Edges 3. Directed * Edges can be Directed or un directed 3. Representation * Adjency List * Matrix 4. Traversal * BFS * DFS

### Create a UnDirectedGraph 1. Create DefautDict(list) 2. add src to dest,dest to source 3. print function

#Foreasy reference we use default dict wih value as list
from collections import defaultdict
class Graph:
    def __init__(self, nodes): 
        self.graph = defaultdict(list)
    def addEdge(self, src, dest): 
        self.graph[src].append(dest)
        self.graph[dest].append(src)

    def printGraph(self): 
    	for key in self.graph:
            print(key,end=": ")
            print(self.graph[key])
            print("\n")
		 
if __name__ == "__main__": 
    V = 4
    graph = Graph(V) 
    graph.addEdge(0, 1) 
    graph.addEdge(0, 3) 
    graph.addEdge(1, 2)
    graph.addEdge(1, 3) 
    graph.addEdge(2, 3) 
     
    graph.printGraph() 

#Output
python3 grapah_basic.py
0: [1, 3]
1: [0, 2, 3]
3: [0, 1, 2]
2: [1, 3]

### Check cycle in directed Graph 1. Create Graph 2. DFS 3. If you reach a visitd node check it is in recursion stack then there is cycle 4. We may visit a node multiple time, That dosent mean its a cycle 5. Keep track of two list visted and recursionStack 6. ``` 1-- >2 -- >3 | | | | v v 4---->5 ```