3
$\begingroup$

I've been asked the following question:

Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \{1,2\}$, suggest an efficient algorithm that finds an MST of the graph.

After a few clarifications, the algorithm should run in time $O(|V|+|E|)$. I believe we can do this because of the fact that there are two types of weight of edges.

I tried the following idea, which did not work (I had a contradicting example):

Run BFS on the graph, and output the BFS tree.

I thought that shortest paths in this case would also mean easiest trees, but this is not the case.

I also tried to make each edge $e$ such that $w(e)=2$ into two edges of weight $1$ but my friend also gave a contradicting example.

Can you help please? This is not a homework question, this is a previous exam question as I am studying for my algorithms exam which is soon.

$\endgroup$
4
$\begingroup$

Since you have only 2 possible edge weights you can perform a linear time sort on the edges, then perform Kruskal's algorithm. The complexity of Kruskal's algorithm comes from its need to sort the edges in terms of weight, which previously had to be done in $O(ElogE)$ time, now however, you can sort the edges in linear time and then perform Kruskal's to complete the search. Creating the vertex set is $O(|V|)$ time, sort in $O(|E|)$ ,build MST in $O(|E|)$ total time is $O(|E|+ |V|)$

$\endgroup$
  • 2
    $\begingroup$ You can certainly sort the edges in linear time, but using Kruskal you have to check while building the MST that a candidate edge lies in two different components, i.e., that the edge won't create a cycle with the edges included so far. It would be good to specify how this cycle detection would be done. $\endgroup$ – Rick Decker Jul 22 '14 at 17:21
  • $\begingroup$ You put flags on the vertex set as you add to visited, if both ends of an edge are visited already, adding it will create a cycle, this is a constant time check. This is no different from the normal algorithm $\endgroup$ – lPlant Jul 22 '14 at 17:24
  • 1
    $\begingroup$ Actually, it's slightly different, since a candidate edge $e=\{u,v\}$ might have endpoints that have already been visited. If $u$ and $v$ lie in the same component then $e$ would be rejected, but if they lie in different components then it would be permissible to include the edge in the MST. In other words, you'd need to flag vertices by which component their edge lay in. $\endgroup$ – Rick Decker Jul 22 '14 at 20:13
  • $\begingroup$ I think @RickDecker right here, It's a issue. usually Kruskal's algorithm use disjoint-set data structure (union–find data structure) to check if the edge's two endpoints added to same component. That have O(log*V) for single (union) action at the best, So it's not O(|E|+|V|). $\endgroup$ – ChaosPredictor Jul 22 '18 at 6:09
4
$\begingroup$

Alternatively use Prim's algorithm. No need to keep track of components. Prim considers each edge once (assuming adjacency-lists). The most costly part of Prim is looking for the next vertex to add: the one of the remaining vertices that has the cheapest connection to the tree already constructed. Here we only have to know whether there are still vertices that have a connection of weight 1 (because they have priority to those of weight 2). I would say that a single list can handle this.

I also think that there might be another approach. Start building spanning trees for the components when we only use edges of weight 1, just ignoring edges of weight 2. Then the components are "big vertices" that can be connected by a tree using the remaining edges of weight 2. Keeping components here is easy: all vertices reached in a new component are labelled with the same number. That number identifies the "big vertex".

$\endgroup$
  • 1
    $\begingroup$ I thought of this; your "big vertices" argument made it clear that the result will indeed be a MST. Nice work. $\endgroup$ – Rick Decker Jul 23 '14 at 0:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.