1
$\begingroup$

I have a connected,undirected and unweighted graph with blue and red edges G(V,E,color). I need to find the spanning tree which has the maximal number of blue edges.

The easy solution to this problem is to give the blue edges lower weight than the red edges and then use either Kruskal or Prim.

I have thought of a different solution and I need help understanding whether my solution is correct or wrong. My algorithm:

1. Turn the graph into an DAG using DFS. the edges are either tree edges or backward/forward edges. For the second type of edges I choose the direction of the edges to be forward. 2. Find the topological sort of the graph 3. Go over the sorted order of the nodes from top to bottom. go over all the outgoing edges from the node and update the distance of the node at the other end with max(current node #blues, source node #blues + 1 if the edge is blue and 0 if the edge is red). All the #blues of the nodes are initiated to be 0. Every time the #blues is changed, also save the parent node of the max. 4. Go over the sorted order again this time from bottom up. choose the parent node for each node and add that edge to the spanning-tree graph.

Any help will be appreciated!

$\endgroup$
1
$\begingroup$

No, you approach is not right. Let $G = (\{\,1, 2, 3\,\}, \{\,\{\,1, 2\,\}, \{\,1, 3\,\}, \{\,2, 3\,\}\,\})$. The edge $\{\,1, 2\,\}$ is red and two other edges are blue. Let DFS start from 1 and choose neighbouring vertices in increasing order. Then we have arcs $(1, 2)$, $(2, 3)$ and $(1, 3)$, so the order $1, 2, 3$ is topological. You have “distances” 0, 0 and 1 and take only one blue edge.

There is an appropriate algorithm which doesn't deal with weighted spanning tree.

Use disjoint set data structure and unite sets by all blue edges. (If edge connects vertices from different sets add this edge to a spanning tree and unite corresponding sets.) After that unite remaining sets with red edges. This give minimum number of blue edges takes $O(n \alpha^{-1}(n) + m)$ time where $n$ is the number of vertices, $m$ is the number of edges and $\alpha^{-1}(\cdot)$ is the inverse Ackermann function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy