10

Use the BFS or the DFS algorithms. They work in $O(n)$ and output a spanning tree if the input is a connected graph


9

Just do a graph traversal algorithm, like DFS or BFS.


2

This is not the case. If an edge $e$ is a bridge in the graph, then every MST has to include $e$. There can exist some cut in which $e$ is the heaviest edge, but this does not change the fact that $e$ must be included (there is some other cut in which $e$ is the only - and therefore the lighest - edge).


1

While I agree with the other answers as the "best" way to find a spanning tree, your intuition to just assume all edge weights are 1 and then use an algorithm for MST is also good. Prim's and Kruskal's algorithms are both quite fast. In particular, if you avoid sorting the edges by weight (which you know you don't have to do because you set all the ...


1

The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree. Let's call $T$ the solution for the input graph $G$. Let's also call $T_i$ the solution for the problem $G_i$ which is the subgraph of $G$ containing vertices with range index lower or equal to $i$ (I ...


1

The best approach would simply be to negate the weight of all edges, and then run an algorithm such as Prim's or Kruskal's, which work with negative edges.


1

It seems to be a group Steiner tree problem. See the answer by @Juno in connecting an unconnected forest of subtrees in a graph?


1

We can show that any complete graph of size $n > 3$ has two edge-disjoint linear trees. Choose $1 < k < n-1$ relatively prime to $n$; this is always possible when $n > 3$. One spanning tree is obtained by the edges $$ E_1 = \{ \{i, i+1\}: 0 \leq i < n-1\} $$ where we identify the vertices with $\{0, \ldots, n-1\}$. For the second tree define $...


1

If all of the weights are integers, then given n nodes, we know the spanning tree will have a maximum of n-1 edges. Therefore multiply all edges so the new edge weight is w_i'=n*w_i+(1 if blue else 0). If non-integer data, then it can always be ordered, discretized and preserved to its original value with a dictionary. This means that the gap between ...


1

The harder part seems to be finding the superlight edges. Isura Manchanayake has provided a good implementation for determining other and superheavy edges. However, using the bridge processor which is effectively a depth first search to do an optimized strongly connected components algorithm, makes this $O(m^2+mn)$ considering a worst case where there are $...


Only top voted, non community-wiki answers of a minimum length are eligible