35. Graphs-1 (basics)

Graph- structure which has nodes & edges

Directed vs undirected graph
Nodes are called vertices
Edge is a line connecting 2 nodes
graph can be open or an enclosed structure
nodes are randomly numbered
BT & single node is also a graph

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

Undirected graph-

1. edges are bi directional
2. Degrees of a node in a graph = n(edges) going inside & outside that node
3. total Degrees of graph = 2 x total edges = (2E)

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

Directed graph-

1. all edges are directed
2. we can have multiple edges between 2 nodes
3. indegree- no. of ingoing edges into that node
4. outdegree- no. of outgoing edges from that node

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

Cycle in a graph:

when we start from a node--->traverse graph-->reach again to starting node
cyclic graph- it has at least 1 cycle
acyclic graph- it has no cycles
DAG- directed acyclic graph

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

Path-  sequence of nodes with each of them being reachable
In a path, adj nodes must have an edge b/w them, like below 1-3 do not have a direct edge

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

Edge Weights- if weight is not given to any edge, assume unit weight

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

Graph Representation-

Method-1: using adj matrix (space=n^2)
store info about edges b/w 2 nodes (i.e., if 2 nodes have a edge b/w them or not )

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

Method-2 :  using adj list  (space = n)
here we will store info about adjacent neighbors of a node


for weighted graphs, store in pairs (neighbor, wt of connecting edge)

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

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

Connected components-

below is a graph with 4 components
-------------------------------------------------------------------------------------------------------------------------
BFS (breadth first search)-

time: O(n+2E)🤔         space: O(3n)

unlike trees, here we can print nodes of a level in any order
LEVEL 0 is the level having starting node (told in ques)
LEVEL 1  nodes are the nodes which are at a dist of 1 from level 0 starting node
ALGO-
1. make a queue and insert starting node in it
2. make vis array of n+1 size (for 1-based graph) and mark all indices 0, except for starting node which will be 1
3. pop out element from queue--> find its neighbors from adjacency list and push non vis waale into queue and mark them 1 in vis array
4. repeat step 3
---------------------------------------------------------------------------------------------------------------------------
DFS (depth first search)-

time: n+2E    space: n


---------------------------------------------------------------------------------------------------------------------------
NOTE- 

0.) n-->nodes & m-->edges
1.) converting edge list -----> adjacency list


2.) converting adj matrix ---> adjacency list


3.) if some nodes have more than 2 neighbors then we declare adjacency list as :
vector<vector<int>>(n+1);

for 1-based graph (nodes are numbered from 1) and we make a (n+1)*(n+1) matrix

4.) if graph has multiple components, we need a visited array to help in traversal of all components
--------------------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more