1. Which edge is chosen in a phase of Kruskal’s algorithm? A. An edge that is on

Question

1. Which edge is chosen in a phase of Kruskal’s algorithm?

            A. An edge that is on a shortest path from the source

            B. The unprocessed edge (x, y) of smallest weight such that find(x)!=find(y) maybe

            C. The unprocessed edge (x, y) of smallest weight such that find(x)==find(y)

            D. An edge of maximum-weight in a cycle (to be excluded)

2. Which edge is chosen in a phase of Kruskal’s algorithm?

A.   An edge of maximum-weight in a cycle (to be excluded)

B.   A minimum-weight edge that keeps the result free of cycles

C.   A minimum-weight edge connecting T to S.

D.   An edge that is on a shortest path from the source

3. The cycle property for minimum spanning trees may be used to find an MST by:

            A. Growing the MST by repeatedly including a maximum weight edge from some vertex in the tree to some vertex that has not yet been placed in the tree.

            B. Growing the MST by repeatedly including a minimum weight edge from some vertex in the tree to some vertex that has not yet been placed in the tree.

            C. Remove the maximum weight in any cycle until only a tree of edges remains.

  D. Remove the minimum weight in any cycle until only a tree of edges remains.

Explanation / Answer

1) 1. Which edge is chosen in a phase of Kruskal’s algorithm?

Kruskal algorithm :

Kruskal's algorithm is a minimum-spanning-tree algorithm.

In this algorithm we finds an edge of the least possible weight that connects any two trees in the forest.ie.,

finds the minimum distance from Source to destination point with no loops(cycles)

so,

answer is, A. An edge that is on a shortest path from the source.

2). Which edge is chosen in a phase of Kruskal’s algorithm?

answer is:B.   A minimum-weight edge that keeps the result free of cycles.

3)The cycle property for minimum spanning trees may be used to find an MST by:

A minimum spanning tree  or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph .

That connects all the vertices together, without any loops or cycles and with the minimum possible total edge weight.

so the answer is,

B. Growing the MST by repeatedly including a minimum weight edge from some vertex in the tree to some vertex that has not yet been placed in the tree.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.