Graphs

These are few questions 1 should do while doing graphs

BFS	https://www.geeksforgeeks.org/problems/bfs-traversal-of-graph/1
DFS	https://www.geeksforgeeks.org/problems/depth-first-traversal-for-a-graph/1
	https://leetcode.com/problems/number-of-islands/description/
	https://leetcode.com/problems/number-of-provinces/description/
	https://www.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1	In undirected graphs, need to track of parent and skip when A-B, so skip pushing parent in queue
	https://leetcode.com/problems/01-matrix/description/	distance from all zeros, multi source bfs, push all zeros to queue
	https://leetcode.com/problems/course-schedule/description/	Topological sort
	https://leetcode.com/problems/course-schedule-ii/description/
	Cycle detection via dfs	https://jdecodes.wordpress.com/2025/06/13/detecting-a-cycle-in-a-directed-graph-a-thoughtful-progression/
	cycle detection via bfs	https://jdecodes.wordpress.com/2025/06/13/cycle-detection-directed-graph-bfs/
	https://leetcode.com/problems/find-eventual-safe-states/	Think of reverse graph for toposort , or simple dfs to find cycle nodes
	https://www.geeksforgeeks.org/problems/shortest-path-in-undirected-graph-having-unit-distance/1
Shortest path equal wt	https://www.geeksforgeeks.org/problems/shortest-path-in-undirected-graph-having-unit-distance/1	simple bfs
Shortest path unequal wt	https://www.geeksforgeeks.org/problems/shortest-path-in-undirected-graph/1	simple bfs -> V * E, every wt. can be better than previous if (dist[node] != INT_MAX && dist[node] + wt < dist[v]) { dist[v] = wt + dist[node]; } , may end with sending all edges to queue. better approach, do a toposort, so order is known that this comes first and then apply wts. according to topo sort apply wts.
Bipartite grapg	https://www.geeksforgeeks.org/problems/bipartite-graph/1	color the graph such that no 2 adjacent nodes have same color, linear graph can always be colored with 2 color,problem start with graph with cycle, if there is graph with cycle of odd length 1-2-1 , we can’t color with 2 colors, even length we can. so find if there is graph with odd cycle ? how to do it , assign each node a color, color the nbhs if already not colored, but if colored, check if the color is correct or not ? consider forsest as well,
	https://leetcode.com/problems/is-graph-bipartite/	dfs way find bipartite,check if same color is reached again or not.
dijkstra	https://www.geeksforgeeks.org/problems/implementing-dijkstra-set-1-adjacency-matrix/1	take min heap to find min each time to find shortest path
	https://www.geeksforgeeks.org/problems/topological-sort/1	topo sort using explicit stack, helpful for DAG
	https://www.geeksforgeeks.org/problems/alien-dictionary/1	which order comes first, classic topo sort, try with both dfs and bfs.with dfs check if cycle is there or not, if not a cycle keep in stack which is topological order. bfs is anyway based on indegree
application of dijkstra	https://leetcode.com/problems/path-with-minimum-effort/	dijkestra regular checks only minimum edge at each level, now this min edge can be replaced with any other condition like min edgeWt difference
	https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/description/	first thought would be that make 1 into 0, then find the path from start to end, but for 1- x how many 1 will you change to 0, then if at certain x , how would you decide to turn those into 1->0? how about finding minimum path from start to end . the min wt is actually our ans to minimum remomval.
0-1 bFS		with pq, we explore a node and put its edges into pq, so each each edge for all vertex is pushed and poped as per need, at any level, we get minimum on the top, why do we need to do a pq here ? because edge wts can be random 1,2,3,4, you can 1 and its corresponding node, it will find its corresponding nodes , lets here wts are 2,1,4, as it is min pq, we already had 2,3,4 and now got 2,1,4 so effectively it becomes 1,2,2,3,4,4.. so we need to store all the edge wts. but lets say when you have only 0/1 wts, so min will be 0, so at a time in your queue wt. could be 0,0,0,1,1,1,1 something like this, top will be alwasy 0, from this 0, you can either get a 0 or 1, lets say when you consume all zeros and you have only 1s , 1,1,1 like this, either next edge wt can be 0 or 1, so the queue can become 1,1,1,1,2 with 1 new 1 and one 2. so effectively always we have 2 types of nummbers at max in the queue, so in a sense we don’t need a priority queue. if we can have some data st. where we can maintain 2 states, 1 for X, other X+1, we should be okay, and poping from front, basic idea would be to have 2 queues, zeros queue, 1 queue , same number we push to 0 zero queue, +1 we push to 1 queue, we always pop first from zero queue, when it becomes empty, we start poping from 1 queue , and (effectively it becomes 0 queue0).. how about a deque, smaller numbers we push to front , bigger to end, and always pop from front.
	https://leetcode.com/problems/network-delay-time/description/	simple application of dijkestra
Count paths	https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/description/	we can use dijkestra for min path, but counting all min paths ?? how to check if this node contributes to min path ,may be along with cost, check no of ways to reach it.
	https://leetcode.com/problems/cheapest-flights-within-k-stops/	Simple bfs with k stops ? (k levels )