GATE Computer Science Engineering(CSE) 2027 Test: Graphs Algorithms- 2

Here Start with a and End with f.

a _ _ _ _ f

Blanks spaces are to be filled with b, c, d, e such that b comes before c, and d comes before e..
Number of ways to arrange b,c,d,e such that b comes before c and d comes before e. will be = 4!/(2!*2!) = 6

No of nodes at level 0(root) of tree =>1
No of nodes at level 1 of tree =>2
No of nodes at level 2 of tree =>4
No of nodes at level 3 of tree =>8
No of nodes at level 4 of tree =>16
Last node in level 4th is the node we are looking for => 1+2+4+8+16 => 31

(a) True.
(b) False.
(c) True.
(d) True.

Answer is A because floyd warshall algorithm used to find all shortest path which is a dynamic programming approach.

X - 3 DFS uses stack implicitly

Y-2 BFS uses queue explicitly in Algo
Z-1 Heap-Heapsort

BFS is used to count shortest path from source (If all path costs are 1 !)
now if u is visited before v it means 2 things.
1. Either u is closer to v.
2. if u & v are same distance from r, then our BFS algo chose to visit u before v.

DFS goes upto how much depth possible and then backtrack and go to the next link.

Here only 'abfehg' not possible because e and h consecutively is not possible by any backtracking of DFS traversal

In Dijkstra's algorithm at each point we choose the smallest weight edge which starts from any one of the vertices in the shortest path found so far and add it to the shortest path.

Take a tree for example

(A) False. Every vertex of tree(other than leaves) is a cut vertex
(B)True
(C)False. Without E in G1 and G2, G1 U G2 has no bridge.
(D)False. G1 U G2, G1, G2 three graphs have same chromatic number of 2.

(A) and (B) produce disconnected components with the GIVEN order in options which is NEVER allowed by
prims's algorithm.
(C) produces connected component every instant a new edge is added BUT when first vertex is chosen(first vertex is chosen randomly) first edge must be the minimum weight edge that is chosen . Therefore (A,D)
MUST be chosen BEFORE (A,B). Therefore (C) is FALSE

For 82a The answer should be Option A because edge 'e' is the lightest safe edge connecting X and Y so the minimum
spanning tree of G must contain 'e' (Greedy and optimal choice).
While B might seem correct but it is not always true. One such case is when G is not connected therefore there might not
be any path between 's' and 't'.
Since the question is about definitely true B is incorrect and A is the only correct option

Lets say AC =1 CD = 2 BD = 3 and AB=4

Then if s= A and t= B then AC is the lightest edge crossing X and Y where X = { A } and Y = { C, B, D}
But clearly AC is not on the shortest path from A to B. The shortest path is AB = 4.

Tree edges are the edges that are part of DFS tree.  If there are x tree edges in a tree, then  x+1 vertices in the tree.

The output of DFS is a forest if the graph is disconnected.  Let us see below simple example where graph is disconnected.

1. Bellman-Ford algorithm =>: O (nm) Assuming n as edges , m as vertices, for every vertex we relax all edges. m*n ,
O(mn)
2. Kruskal’s algorithm => Remaining Option ,A : O ( m log n)
3. Floyd-Warshall algorithm => Dynamic Programming Algo, O(N3)
4. Topological sorting => Boils Down to DFS, O(V+E) D

we can find single source shortest path in unweighted graph by using Breadth first search (BFS) algorithm which using "Queue" data structure , which time O(m+n) (i.e. linear with respect to the number of vertices and edges. )

Consider following graph

Dfs is .
so D is answer.

A graph is said to be strongly connected if every vertex is reachable from every other vertex.

The strongly connected component is always maximal that is if x is strongly connected component there should not exist another strongly connected component which contains x.

If we take R as a strongly connected component but which is part of PQRS and PQRS is part of PQRSVT.

As seen in quetion after 10 we have to go for p again and since p is finish and then r is start so r must be disconnected because if their is edges from q to r then r must be visited before of q and p ending.

Dijkastra and warshall 's algo only used for weighted graph.

Both DFS and BFS can be used for finding path between 2 vertices in undirected and unweighted graph but BFS can only give the shortest path as concern in given question so BFS is Ans.

Note :- finding only path(DFS) and finding shortest path(BFS) ..Matters a lot

Go with Vertex with indegree 0 remove that vertex with all edges foing from it . Follow that procedure.
We See 3 cannot come at first B/c indegree is not 0. so D is answer here .
ALL other options are Topologocal order.
Only 1 and 4 order matter for this quetion.

I'm gonna disprove all wrong options here.
A) d[u] < d[v] , Counter Example => Well if we directly start DFS on V first. Then I call DFS on X which visits U.
B) d[u] < f[v] Counter example => Same as A)
C) f[u] < f[v] Counter example => Same as A) again
So answer is D)

The minimum weight happens when (S,U) + (U,V) = (S,V)

Else (S,U) + (U,V) >= (S,V)

Given (S,U) = 53, (S,V) = 65

53 + (U,V) >= 63

(U,V) >= 12.

A) MNOPQR -> If you try to run BFS, after M, you must traverse NQR (In some order) Here P is traversed before Q, which
is wrong.
B) NQMPOR -> This is also not BFS. P is traversed before O !
C) QMNPRO -> Correct
D) QMNPOR -> Incorrect. Because R need to be traversed before O.(Because M is ahead of N in queue.
Answer :- > C

(d) all the vertices. Just simulate the Dijkstra's algorithm on it. Dijkstra's algorithm is not meant for graphs with negative edge- weight-cycle, but here it does give the correct shortest path.

Run DFS to find connected components. Its time complexity is 

1. After f is visited, c or g should be visited next. So, the traversal is incorrect.
4. After c is visited, e or f should be visited next. So, the traversal is incorrect.
2 and 3 are correct.