Kruskal's and Prim's algorithms are greedy methods used to construct what structure in a weighted graph?

• A. Shortest path
• B. Minimum Spanning Tree
• C. Vertex Cover
• D. Maximum Flow

Answer: (B)

Kruskal's and Prim's algorithms are greedy methods used to construct a minimum spanning tree in a weighted graph. They aim to connect all vertices with the smallest possible total edge weight while avoiding cycles. Prim's algorithm builds the tree by starting from a vertex and repeatedly adding the lightest edge that reaches a new vertex, extending the single growing tree. Kruskal's algorithm looks at edges in increasing order of weight and adds an edge if it connects two different components, using a union-find structure to prevent forming cycles. If the graph is connected, both approaches produce a minimum spanning tree; if not, they yield a minimum spanning forest. The other options describe different problems: a shortest path finds the best route between two vertices, a vertex cover is a set of vertices that touches every edge, and maximum flow deals with the greatest possible flow through a network with capacities.