As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [spanning-trees]

The spanning tree of a connected undirected graph G is a tree having all the vertices and some number of edges of G.

139 questions
Filter by
Sorted by
Tagged with
111k views

### Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
• 1,183
43k views

### When is the minimum spanning tree for a graph not unique

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G? I know that the MST is unique when all of the weights are distinct, but ...
• 467
5k views

### Do any two spanning trees of a simple graph always have some common edges?

I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to ...
• 1,263
14k views

### Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
• 1,121
11k views

### Graph Has Two / Three Different Minimal Spanning Trees?

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
• 293
17k views

### Why is the k-bounded spanning tree problem NP-complete?

The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$. I ...
• 131
2k views

### Minimal Spanning Tree With Double Weight Parameters

Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The ...
• 1,505
1k views

### Tighter analysis of modified Borůvka's algorithm

Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$. The pseudo-code is: ...
• 4,037
20k views

### If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time? Intuitively this sounds correct, as ...
• 571