StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POgraph - How to obtain the Minimum Weight Connected Subset?
text
Body
copied!<p>Here is an excise:</p> <blockquote> <p>Consider the problem of finding a minimum weight connected subset T of edges from a weighted connected graph G. The weight of T is the sum of all the edge weights in T.Give an efficient algorithm to compute the minimum weight connected subset T. </p> </blockquote> <p>Here are what I have got:</p> <ol> <li><p>I have to assume the weights are mixed by both positive and negative ones. Only the mix of both kinds of weights can make sense for this excise.</p></li> <li><p>I will sort the edges first, so the negative edges will come first.</p></li> <li><p>I will consider utilise Kruskal's algorithm, but should be with some modifications</p></li> <li><p>Because I welcome negative edges, I will try to add as many negative edges as possible. </p></li> <li><p>In addition, some positive edges may be added to just in case that not all negative edges are connected and they may need some positive edges as bridges.</p></li> </ol> <hr> <p>Ok, above is my thinking. But when I try to get my hands dirty, I get stuck.</p> <p>How can I always record the possible minimum weights set?</p> <p>For example, </p> <p>{0, 1} is with weight -20</p> <p>{2, 3} is with weight -10</p> <p>if {1, 3} has weight of 11, then of course I don't want {1, 3}</p> <p>or if {1, 3} has weight of 9, then I want</p> <p>With what kind of data structure I can always keep the minimum weight and the vertices for that weight?</p> <hr> <p>It is worth to note that the subset this excise seeks for aim at <code>edges</code>. </p> <blockquote> <p>Consider the problem of finding a minimum weight connected <strong>subset T of edges</strong> from a weighted connected graph G</p> </blockquote> <p>This means that all vertices still need to be included. </p> <p>Also it is more than a MST. Consider that if a vertex has two edges, one is -1, another is -2. In a normal MST algorithm, only edge of -2 will be taken. But in this excise, both -1 and -2 need to be taken to reduce the overall weight further. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload