35. Graphs-1 (basics)

# Note- 

1. it has nodes/vertices (N) connected by edges (E)
2. degree(N) = n(edges) connected to a node
3. in-degree(N) = no. of in-going edges 
4. out-degree(N) = no. of out-going edges 
5. Total degree of undirected graph = (2*E)
6. DAG- directed acyclic graph
7. Path-  a sequence of nodes where all adj nodes have a direct edge b/w them

--------------------------------------------------------------------------------------------------------------------------

1. Representation-

1. Adjacency Matrix:  space: O(n^2)

store info about presence of edges between 2 nodes

--------------------------------------------------------

2. Adjacency list:  space: O(n)

- store info about adjacent neighbours of a node
- for unweighted graph instead of a pair we will store them as integer array

-----------------------------------------------------------------------------------------------------------------------------

2. BFS-

time: O(N+E)

Level 0: has starting node

Level x: has nodes which are at a (dist = 1) from starting node

--------------------------------------------------------
1. create a visited array initialised to 0 for all nodes

2. Insert starting nodes in a queue & mark them visited

3. Pop out element from queue and store it in your answer
4. Push all its non visited neighbours into queue & mark them visited

Repeat till queue is filled

- We need visited array to avoid infinite loops in case of cycles
- using a queue ensures that we process all nodes at a distance d first before processing the nodes at distance d+1
- we mark nodes visited just after pushing and not after popping, because else wise multiple parents could have pushed the same node
---------------------------------------------------------------------------------------------------------------------------

3. DFS-

time: O(n+2E)

It is recursive
Process current node --> mark it visited --> traverse on its non visited neighbours

---------------------------------------------------------------------------------------------------------------------------

# Multi component graph-

For a multi component graph traversal, we declare visited array outside bfs or dfs and work as follows-

----------------------------------------------------------------------------------------------------------------------------

# Note-

1. Converting edge list --> adjacency list

-------------------------------------------------------------------

2. Converting adj matrix ---> adjacency list

--------------------------------------------------------------------------------------------------------------------------