Recommended Free Tools
iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
A spanning tree algorithm selects edges from a connected, undirected graph so that every vertex is included, the resulting subgraph stays connected, and no cycle remains. Breadth-first search (BFS) and depth-first search (DFS) can build spanning trees; Kruskal’s and Prim’s algorithms solve a different problem: finding a minimum spanning tree (MST) with the least total edge weight.
What is a spanning tree?
For a connected, undirected graph G = (V, E), a spanning tree is a subgraph T = (V, ET) that uses edges from the original graph and includes all of its vertices. It must be connected and contain no cycles. In other words, every vertex can be reached from every other, and there is exactly one path between any pair of vertices within the tree. e-PG Pathshala / INFLIBNET
| # | Preview | Product | Price | |
|---|---|---|---|---|
| 1 |
|
Introduction to Algorithms, fourth edition | $99.47 | Buy on Amazon |
| 2 |
|
Algorithms (4th Edition) | $68.77 | Buy on Amazon |
| 3 |
|
Introduction to Algorithms, 3rd Edition | $83.63 | Buy on Amazon |
| 4 |
|
Algorithms | $142.22 | Buy on Amazon |
| 5 |
|
Algorithm Design | $214.81 | Buy on Amazon |
A tree with n vertices has n − 1 edges. That is the fewest edges that can connect all n vertices without leaving the graph disconnected.
How does a spanning tree algorithm work?
A graph traversal can build a spanning tree by recording how each newly discovered vertex was reached. Start at one vertex, explore the graph, and add the discovery edge whenever the search reaches a vertex for the first time. When every vertex has been reached, those recorded edges form a spanning tree.
#1 Best Overall
- color: White
- INTRODUCTION TO ALGORITHMS, FOURTH EDITION
Breadth-first search (BFS)
BFS explores outward from the starting vertex, visiting nearby vertices before vertices farther away. It typically uses a queue. The discovery edges form a tree that grows in levels from the start.
Depth-first search (DFS)
DFS follows one path as far as possible before backtracking to explore another. It can be implemented with a stack or recursion. Its discovery edges form a spanning tree, but the tree shape may differ from the one produced by BFS.
Rank #2
The outcome is not necessarily unique: the starting vertex, neighbor order, and traversal choices can lead to different valid spanning trees for the same graph. BFS and DFS do not need edge weights because their purpose is to traverse the graph, not minimize a cost. OpenStax / Rice University
Quick wins for a faster PC:
Scan for outdated or missing drivers - takes under a minuteDriver Scan →Repair Windows errors before they cause bigger problemsFix Now →Spanning tree versus minimum spanning tree
A spanning tree is any tree that connects every vertex of a connected graph. A minimum spanning tree is a spanning tree for a weighted graph whose selected edges have the smallest possible total weight. The word “minimum” therefore implies both edge weights and an optimization goal; it does not apply to every spanning tree.
Rank #3
| Algorithm | Goal and growth pattern | Uses edge weights? |
|---|---|---|
| BFS | Builds a spanning tree by exploring level by level. | No |
| DFS | Builds a spanning tree by following paths and backtracking. | No |
| Kruskal | Builds an MST by considering edges in increasing weight order and joining separate components. | Yes |
| Prim | Builds an MST by extending one existing tree across its boundary using a least-weight crossing edge. | Yes |
Kruskal rejects an edge if its endpoints are already in the same component, since adding it would create a cycle. Prim considers only edges that cross from the growing tree to a vertex outside it. Both are greedy MST algorithms. OpenStax / Rice University University of Texas at Austin
What if the graph is disconnected?
A single spanning tree cannot cover a disconnected graph: there is no path connecting its separate components. A traversal can instead produce a spanning forest, which contains a tree for each component. If the goal is to minimize weights, finding an MST separately in each component produces a minimum spanning forest.
Rank #4
How efficient are the MST algorithms?
Theoretical running times depend on the implementation and the way the graph is represented. In the notation below, n is the number of vertices and m is the number of edges; these are algorithmic bounds, not benchmark measurements.
What’s actually slowing this PC down?
Pick the symptom - the matching free tool is one click away.
| Algorithm and implementation context | Published bound | Source |
|---|---|---|
| Kruskal, using disjoint sets to track components | O(|E| log |E|) | OpenStax / Rice University |
| Kruskal, sorting-dominated bound plus amortized union-find work | O(m log n) plus O(m·α(n)) amortized | University of Texas at Austin |
| Prim, OpenStax treatment | O(|E| log |V| + |V| log |V|) | OpenStax / Rice University |
| Prim, binary heap | O((n+m) log n) | University of Texas at Austin |
| Prim, Fibonacci heap | O(m+n log n) | University of Texas at Austin |
The choice of method follows the task: use BFS or DFS when you need a spanning tree from graph traversal; use Kruskal or Prim when you need the lowest-weight way to connect all vertices.
Quick Recap
Best Value
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
