If we find shortestt path fram C to D then it is
13 currently. So we can use maximum 12 value
for x
so x = 12Data Structures and Algorithms MCQ - Design Techniques
If we find shortestt path fram C to D then it is
13 currently. So we can use maximum 12 value
for x
so x = 12
there are 3 aoticulation point in the given graph
which break the graph in to component.
{2, 3, 5}
A graph is said to be strongly connected if there
is path from each vertex of graph to every other
vertex means every vertex is reachable from every
other vertex. The strongly connected component
is always maximal that is if A is strongly
connected component there should not exist
another strongly connected component which
contains A
Topological ordering of a directed graph is a linear
ordering of its vertices such that for every directed
edge uv from vertex u to vertex v, u comes before
v in the ordering. Topological ordering is possible
iff graph has no directed cycles.
(A) As the given graph doesn’t contain any directed
cycles, it has at least one topological ordering.
So option (A) is false
(B) PQRS cannot be topological ordering because
S should come before R in the ordering as there
is a directed edge from S to R. SRQP cannot be topological ordering, because P should
come before Q in the ordering as there is a
directed edge from P to Q
(C) PSRQ and SPRQ are topological orderings as
both of then satisfy the above mentioned
topological ordering conditions.
(D) PSRQ is not the only one topological ordering
as SPRQ is other possibility.
For krushkal’s algorithm time complexity is O (log V)
∵ E → edges
∵ V → ventices
So O (m log n)
