-3
$\begingroup$

Please click here to see the image

So here, I am not sure what the while statement means. In the lecture note there is no definition for T or N or u or v. My guess is T is the minimum spinning tree, but is N the node? Why condition T to be smaller than N - 1?

And how about the case of a cycle? shouldn't we take that into consideration as well?

I understand how Kruskal works but i am just not sure what this pseudocode means.

$\endgroup$

closed as off-topic by David Richerby, Evil, Juho, Thomas Klimpel, Tom van der Zanden Nov 1 '16 at 13:21

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – David Richerby, Evil, Juho, Thomas Klimpel, Tom van der Zanden
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ If you understand how Kruskal works, you should be able to answer your questions yourself: just fix the algorithm so that it works as intended! $\endgroup$ – Raphael Oct 23 '16 at 21:57
  • $\begingroup$ Welcome to Computer Science! Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Oct 23 '16 at 21:58
  • $\begingroup$ We're not here to debug your teacher's code, or to do your homework for you. $\endgroup$ – David Richerby Oct 24 '16 at 8:00
1
$\begingroup$

$|T|$ is the number of edges in the forest $T$, eventually $T$ will become the required minimum spanning tree. |N| is the number of nodes of the graph (for which you are finding a MST). You start by an empty forest and at each step you add an edge that does not form a cycle. You stop once you have picked exactly $|N| - 1$ edges.

$\endgroup$
0
$\begingroup$

Goal: Compute MST of $G = (V, E)$.

We have $ N = \lvert V \rvert $ in your pseudocode.

In the lecture note there is no definition for T or N or u or v.

You can represent an edge $e \in E$ as a tuple $(u, v)$, where $u,v \in V$, meaning vertex $u$ has a link with vertex $v$.

Also, note that a Tree must have $N - 1$ edges, and no cycles. Kruskal deals with cycles by using a Disjoint Set Data Structure.

Step 1: Initialization and Sorting

Initialize $ ~ T = \emptyset $.

Sort $~E~$ by edge weigth.

Step 2: Building T

If you naively take only the first $n$ edges there's a chance that $ ~ T ~$ will contain a cycle, and therefore be a MST. That's why there's an if statement checking whether two vertices are already in the same component. Looking at the example I've modified from Wikipedia:

Iteration from state (A) to (B).

If you greedily chose edge $(D,B)$ you'll end up with a cycle, however both $D$ and $E$ are in same component (green), so the if condition fails.

Now the next iteration will check the next edge in sorted $E$, i.e. $(B, E)$.

$\endgroup$

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