AI Generated Answers. Questions came from graph-mining material on this blog and are attributed to Sayed Ahmed. The new AI-generated explanations and code are provided for reuse without copyright restrictions asserted by the blog; external materials retain their own terms. An inconsistency in the original sample MST is corrected here and documented explicitly.
Graph Mining – 1 course index · Original post: Graph Mining: K-Spanning Trees.
Original weighted example: edges (1,2,7), (1,3,2), (1,4,4), (2,3,3), (2,4,5), (3,4,2), (3,5,6), (4,5,4). Weights here represent distances or costs.
Q08.01. What is a Spanning Tree?
Answer. A spanning tree of a connected undirected graph is a connected, cycle-free subgraph containing every original vertex. It has exactly V−1 edges.
Q08.02. What is a Minimum Spanning Tree?
Answer. A minimum spanning tree (MST) is a spanning tree whose edge-weight sum is the smallest possible among all spanning trees. Weights typically represent costs or distances. Multiple different MSTs can tie.
Q08.03. For the undirected Graph below, what is a Spanning Tree? First, draw the Graph, then Try to find the answer, and then check the answer below. Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}
Answer. For the original weighted graph on vertices 1–5, {(1,2,7),(1,3,2),(3,4,2),(3,5,6)} is a valid spanning tree of weight 17: five vertices, four edges, connected, no cycle. It is not minimum. Draw each weighted edge as a labeled line and compare it with the MST below.
Q08.04. What is a minimum spanning tree?
Answer. A minimum spanning tree minimizes Σ_{e in T} w(e) subject to T connecting all graph vertices without cycles. It is different from a shortest-path tree, which minimizes distances from one chosen root.
Q08.05. What is the minimum spanning tree for the graph as provided above?
Answer. The correct MST cost for the source graph is 11, using (1,3,2),(3,4,2),(2,3,3),(4,5,4). All five nodes are connected and the sum is 2+2+3+4=11. Correction: the source’s earlier weight-17 tree is spanning but not minimum; its later Prim sequence establishes 11.
Q08.06. What is Prim’s Algorithm for Spanning Trees?
Answer. Prim’s algorithm grows an MST from a starting vertex by repeatedly selecting the lightest edge crossing from the included vertices to a vertex not yet included. It uses the MST cut property.
Q08.07. Describe the steps as used in Prim’s Algorithm?
Answer. Initialize a set S with one chosen vertex; collect edges crossing from S to V\S; add the minimum-weight eligible edge and its new endpoint; repeat until all vertices are included. A priority queue can speed edge selection.
Q08.08. Give the Algorithm i.e. Prim’s Algorithm?
Answer. For a connected undirected weighted graph: start with S={s}, T=∅. While |S|<|V|, choose argmin w(u,v) over edges with u∈S and v∉S; add (u,v) to T and v to S. Return T.
Q08.09. Write pseudo-code for Prim’s Algorithm?
Answer. Pseudocode:T ← ∅; S ← {start}; Q ← edges leaving startwhile |S|<n: choose minimum-weight crossing edge (u,v) add v and (u,v); update Qreturn T.
With an adjacency-list heap implementation, complexity is O(E log V) under standard assumptions.
Q08.10. Implement Prim’s Algorithm in Python, R, Matlab, or in any other language of your choice?
Answer. See the from-scratch Python heap implementation below. It yields a weight-11 MST for the source graph and checks against NetworkX’s minimum_spanning_tree implementation.
Q08.11. What is the initialization step in Prim’s Algorithm?
Answer. Choose any starting vertex; mark it visited/in the growing tree; initialize the priority queue with all incident edges. The tree initially contains that one vertex and zero edges.
Q08.12. Can you choose any node to start with Prim’s Algorithm?
Answer. Yes. On a connected undirected graph with fixed edge weights, Prim’s algorithm can begin at any vertex and still yield an MST, though equal weights may produce different MST edge sets.
Q08.13. True or False, Prim’s algorithm does not include all nodes in the output?
Answer. False for a connected graph: an MST spans all vertices. On a disconnected input, Prim from one vertex only covers its component; a minimum spanning forest covers all components.
Q08.14. How an edge/path is selected in Prim’s Algorithm?
Answer. Choose a minimum-weight edge with exactly one endpoint in the current tree and the other outside it. This cut-crossing condition prevents cycles and allows the tree to grow.
Q08.15. True or False, to proceed and when to select an edge, the edge does not need to belong to the already formed Minimum Spanning Tree (MST)?
Answer. False. A selected edge must cross the cut between vertices already in the growing tree and vertices outside it; hence one endpoint must belong to the tree.
Q08.16. True or False, to proceed and to select a new edge, the edge will need to have the highest weight outgoing from the MST or from the vertex under consideration)?
Answer. False. Prim chooses a minimum-weight eligible crossing edge, not a maximum-weight one.
Q08.17. True or False, to proceed and to select a new edge, the edge will need to have the minimum weight outgoing from the MST (or from the vertex under consideration)?
Answer. True if stated precisely: choose the lightest edge across the current tree/outside cut, not merely the lightest edge incident to the last-added vertex.
Q08.18. True or False? The new edge selection steps are as follows. Step 1. For the new edge, exactly one of its vertices/edge-points will need to be in the MST already Step 2. The new edge has the minimum weight that satisfies step 1.
Answer. True. Exactly one endpoint is already in the growing tree, and the selected edge has the minimum weight among all such crossing edges. This is the correct rule for extending Prim’s tree.
Q08.19. How long will you continue to add new edges to the MST? i.e. terminating condition for your algorithm.
Answer. Stop when all V vertices have been added, equivalently when T has V−1 edges. If no eligible crossing edge exists before that, the input is disconnected and a single spanning tree cannot exist.
Q08.20. Apply Prim’s algorithm to find the MST in Graph given above/below: See the answer after you give it a try Edges with weights: {1, 2, 7} {1, 3, 2} {1, 4, 4} {2, 3, 3} {2, 4, 5} {3, 4, 2} {3, 5, 6} {4, 5, 4}
Answer. Run Prim starting at vertex 5: choose (5,4,4), then (4,3,2), then (3,1,2), then (3,2,3). Total 11. This is an MST. Any order of the same eligible ties with the same final minimum cost is acceptable.
Q08.21. What is K-Spanning tree?
Answer. In the source article, ‘K-Spanning Tree’ means MST-based k-clustering: build an MST, then delete k−1 large distance edges to obtain k components. Caution: in optimization literature, a k-minimum spanning tree can mean a minimum tree spanning only k vertices, which is a different problem.
Q08.22. What are the steps in K-Spanning Tree?
Answer. Compute an MST; sort its edges by distance weight descending; remove the k−1 heaviest MST edges; return the k connected components. The simple procedure assumes a connected graph and 1≤k≤V.
Q08.23. Give the Algorithm for K-Spanning?
Answer. Algorithm: T ← MST(G); remove k−1 highest-weight edges from T; clusters ← connectedComponents(T). With distance weights, this is closely related to single-linkage hierarchical clustering.
Q08.24. Write pseudo-code for K-Spanning?
Answer. Pseudocode:T ← PRIM(G)for e in top(k−1, T.edges, by=weight): remove ereturn CONNECTED_COMPONENTS(T).
If weights tie, specify a deterministic tie policy, because different cuts may give different group membership.
Q08.25. Implement the K-Spanning tree algorithm in Python, R, Matlab, or in any other language of your choice?
Answer. The implementation below uses NetworkX to compute the MST, sorts its edges, and cuts the heaviest k−1. It validates k and returns clusters. You can replace NetworkX’s MST with the from-scratch Prim implementation in the same lesson.
Q08.26. What is K in the K-Spanning Tree algorithms?
Answer. k is the desired number of clusters/components in the source’s MST-cut procedure, not the number of vertices included in the MST. Valid range on a connected n-vertex graph: 1≤k≤n.
Q08.27. How many edges do you remove to create k Clusters?
Answer. Remove exactly k−1 edges from a tree to split it into k connected components. Every removed tree edge increases the component count by one.
Q08.28. What is the first step in the K-Spanning tree?
Answer. First compute a minimum spanning tree of the weighted connected input graph. Then identify its highest-weight distance edges for cutting.
Q08.29. When you remove edges from an MST – which edges do you remove? Edges represent distance. The ones with the highest weights or the lowest weights?
Answer. Remove the highest-weight MST edges if weights mean distances or dissimilarities. If higher weights instead mean stronger similarity, you must transform/interpret weights appropriately; blindly deleting largest weights would be wrong.
Verified Python: Prim’s MST and k-way clustering
import heapq
import networkx as nx
edges = [(1,2,7),(1,3,2),(1,4,4),(2,3,3),
(2,4,5),(3,4,2),(3,5,6),(4,5,4)]
G = nx.Graph()
G.add_weighted_edges_from(edges)
def prim(G, start):
seen = {start}; result = []
heap = [(d["weight"], start, v)
for v,d in G[start].items()]
heapq.heapify(heap)
while heap and len(seen) < len(G):
w,u,v = heapq.heappop(heap)
if v in seen: continue
seen.add(v); result.append((u,v,w))
for nxt,data in G[v].items():
if nxt not in seen:
heapq.heappush(heap,(data["weight"],v,nxt))
if len(seen) != len(G):
raise ValueError("Graph must be connected")
return result
my_mst = prim(G,5)
print(my_mst, "total:", sum(w for _,_,w in my_mst))
# Total weight: 11
T = nx.minimum_spanning_tree(G,weight="weight")
assert sum(d["weight"] for _,_,d in T.edges(data=True)) == 11
def mst_clusters(G,k):
if not nx.is_connected(G) or not 1 <= k <= len(G):
raise ValueError("Need connected G and 1<=k<=n")
T = nx.minimum_spanning_tree(G,weight="weight")
heavy = sorted(T.edges(data=True),
key=lambda e:e[2]["weight"],reverse=True)
for u,v,_ in heavy[:k-1]: T.remove_edge(u,v)
return [sorted(c) for c in nx.connected_components(T)]
print("k=2 clusters:", mst_clusters(G,2))
Interpretation: the source’s four-edge spanning tree of total 17 is not minimum. The correct minimum is 11. Cutting the largest MST edge can isolate one vertex, so evaluate cluster usefulness instead of relying on the distance rule alone.
