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
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!