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

learn more… | top users | synonyms

2
votes
2answers
311 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 ...
1
vote
0answers
28 views

Question about spanning trees and creating them through BFS and/or DFS algorithms

The question is as follows: True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the ...
5
votes
3answers
132 views

Minimal spanning tree with degree constraint

I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of ...
1
vote
2answers
71 views

Applications of Depth-First Spanning Tree

I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that ...
3
votes
0answers
95 views

Prim's Algorithm - Building the Priority Queue

Suppose we were using a priority queue(PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then ...
1
vote
2answers
94 views

Spanning Tree - Equivalent Properties

I am working on the following problem: Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') ...
-1
votes
2answers
105 views

Proof of Correctness of Prim's algorithm [duplicate]

what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case? Is it because of after any number of steps, $S$ might not be in a sub ...
-1
votes
1answer
111 views

Minimal Spanning tree and Prim's Algorithm

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
-1
votes
1answer
44 views

Satisfying condition to be in minimum spanning tree of an edge (maximum weight)

Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always ...
0
votes
1answer
72 views

Find a diffrent minimal spanning tree for a graph

For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST: Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$. I want to find another minimum ...
3
votes
2answers
167 views

Minimum spanning tree and its connected subgraph

This problem is from the book Algorithms, Chapter 5: Greedy algorithms. In case of being closed as a duplication to that in Minimum Spanning tree subgraph, I will first make a defense: The accepted ...
2
votes
2answers
427 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
vote
2answers
57 views

Showing that graph of spanning trees are connected

Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$. We create an edge between 2 vertices in $H$ if $ST_1$ (spanning tree) contains exactly one edge not in ...
1
vote
1answer
119 views

Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?

I'm given this problem: Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen ...
4
votes
1answer
498 views

MST: Prim's algorithm complexity, why not $O(EV \lg V)$?

According to CLRS, the Prim's algorithms is implemented as below -- $\mathtt{\text{MST-PRIM}}(G,w,r)$ for each $u \in V[G]$ do $\mathtt{\text{key}}[u] \leftarrow \infty$ ...
1
vote
1answer
74 views

Upper bound on the number of edges relative to the height of a DFS tree

Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of ...
9
votes
3answers
1k 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 ...
4
votes
3answers
1k views

How many minimal spanning trees are there when all edge costs are distinct?

Suppose all costs on edges are distinct. How many minimal spanning trees are possible? I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because ...
2
votes
1answer
86 views

DFS miniumum spanning tree

Just a quick question, If i were to alter the general DFS algorithm to do this: ...
3
votes
2answers
1k views

Minimum spanning tree with two minimum edge weights

Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree? I know the proof for if all edge weights are ...
2
votes
1answer
471 views

Question about Prims algorithm where weights are between 1 and some constant W

I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of ...
1
vote
0answers
129 views

What edges are not in any MST

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed. My motivation is to find what edges ...
2
votes
1answer
685 views

Depth First Search to find Minimum spanning tree

A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example ...
11
votes
1answer
248 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 ...
4
votes
1answer
176 views

Why do the swap step in Prim's algorithm for minimum spanning trees?

I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees. Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
5
votes
0answers
137 views

Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$. The weight function assigns a ...
9
votes
1answer
366 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: ...
7
votes
1answer
1k 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 ...
2
votes
1answer
587 views

NP-completeness of a spanning tree problem

I was reviewing some NP-complete problems on this site, and I meet one interesting problem from NP completeness proof of a spanning tree problem In this problem, I am interested in the original ...
3
votes
2answers
426 views

Does spanning tree make sense for DAG?

Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.