Test: Graphs Algorithms- 1 - Computer Science Engineering (CSE) MCQ

Relaxation at every vertex is as follows
Note the next vertex is taken out here is in RED colour

Now We see for S to T its (S->A->C->E->.T)
which is Option d

Time complexity of Bellman-Ford algorithm is    is number of vertices and   is number of edges. If the graph is complete, the value of  becomes    So overall time complexity becomes     And given here is n vertices. So answers ends up to 

The C option has been copied wrongly
C) Both PSRQ and SPRQ are topological orderings
i)Apply DFS by choosing P or S as starting vertices
ii)As the vertex gets a finishing time assign it to the head of a linked list
iii)The linked list is your required topological ordering

BFS always having starting node. It does not calculate shortest path between every pair but it computes shorted path between W and any other vertex ..

 is possible when both u and v have an edge from t and t is in the shortest path from s to u or v .

  is possible when v and t are in the shortest path from s to u and both t  and v are siblings- same distance from s to both t and v causing t-u to both and causing v-u

  is possible as explained above by interchanging u and v.

  is not possible. This is because on BFS traversal we either visit u first or v . Let's u take first. Now, we put all neighbors of u on queue. Since v is a neighbour and v is not visited before as assumed, d(v) will become d(u)+1

Similarly, for v being visited first.

Applying BFS on Undirected graph give you twin pointer .Visit every vertex level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take 0(m+n) time.

take extra field for storing no. of linked list for perticular vertex. take extra m+n time( m vertex and n edges).
So B is answer

> MST is not unique only when edges are not distinct. Here the edges are distinct. Be careful for the keyword
DISTINCT.

> Shortest Path can be different even if the edges are distinct. Example is shown below. Shortest path from A
to C is not unique here.

In BFS starting from a node, we traverse all node adjacent to it at first then repeat same for next nodes

Here you can see only D is following BFS sequence properly

As per BFS if we start from M then RQN has to come after it in any order but in A here O comes so it is not
As per BFS if we start from Nthen QMO has to come after it in any order but in A here P comes so it is not
As per BFS if we start from M then MNOP has to come after it in any order but in A here R comes so it is not but D following the sequences

so D is correct answer

Correct option is C. If {u, v} is not an edge in G then u is a leaf in T

Since they said that whenever their is a choice we will have to select the node which is alphabetically earlier , therefore we choose the starting node as A .

The tree then becomes A-B-E-C . Therefore no of tree edges is 3 that is (T=3) .
Now there is one cycle B-E-C so we will get a back edge from C to B while performing DFS. Hence B=1 .
Now D becomes disconnected node and it can only contribute in forming cross edge . There are 2 cross edges D-A , D-B .
Therefore C=2 .

Arrange files in increasing order of records

5(D) 10(A)
No of movements=15+30+45+75=165

The most important statement in question is

each task requires one unit of time

This shows that we can greedily choose the better task and that should give us the optimal solution. The best task would be the one with maximum profit. Thus we can sort the tasks based on deadline and then profit as follows:

0 ----T7 ----- 1----T2-----2-----T9-----3-----T5-----4-----T3-----5-----T8-----6-----T1------7

T4 and T6 left out

The most important statement in question is

each task requires one unit of time

This shows that we can greedily choose the better task and that should give us the optimal solution. The best task would be the one with maximum profit. Thus we can sort the tasks based on deadline and then profit as follows:

0 --T7 -- 1 -- T2 -- 2 -- T9 -- 3 -- T5 -- 4 -- T3 -- 5 -- T8 -- 6 -- T1 -- 7

so we know that T4 and T6 are left
so profit will not include T4 and T6 = 15 + 20 +30 +18 + 16 + 23 + 25 = 147

A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.