Chapter 3 Network Algorithms : MST Kruskal And Prim

Question 1

Why are kruskal and prims bith greedy and optimal

Answer 1

Greedy = dies everythign at once, no consideration to what may happen later, no strategy

However optimal both will ALWAYS GIVE THE BEST SOLUTION

Question 2

How to do KRUSKAL algorithm

Remember ti record!

Answer 2

Need ti go for the SMALLEST WEIGTH EACH TIME, and shade it if it DOESNT CREATE A CYCLE

repeat and cross out the ones that do

Omce graoh becomes connected, your done !

HOWEVER YOU MUST RECORD EACH EDGE YOU CHOSE FIRST !

Question 3

For keuskal how to record

Answer 3

Each time you pick you must record the weight

And also recird the ones you DONT pick by crossing them out

Question 4

Remember a cycle can take a long route, be careful

Also what edges should you have when done

Answer 4

After done should have one less edge remember , thatdwhat trees have

Question 5

How to do prims
Remember order

Remember state weight + rewrite diagram

Answer 5

1) PICK ANY POINT (but they will prob tel, you)
2) now pick the least arc going out, shade , record

3) now from thr same point, AND THE POINT YOU CINNECTED TO, check again for the
smaleest arc possible, that WONT CONNECT A CYCLE
- write this down

Keep on doing this and you’ll have your tree ready

4)
THE ORDER IS PARAMOUTN, without it examiner won’t know it’s prims

MST= x , redraw diagram

Question 6

How can you tell if itd prims vs Kruskal

Answer 6

Prims kinda ‘prims’ all over from one point, whereas as Kruskal is just random

Question 7

A MUCH easier way to think about prims

Answer 7

Instead of oh look at next corner

Just look at the next possible connection which doesn’t make a cycle, and out of them what’s the smallest

This way you don’t have to think too much

Question 8

How to do PRIMS usinf incidence table?

Answer 8

1) pick a point , say A , to start from . Mark 1 on top and then DELETE THE WHOLE ROW
- deleting rows means you don’t create CYCLES
2) look down colomn and look for the SMALLEST WEIGHT
- identify, CIRCILE IT
- now record the connection (AD6) for example in the recording
3) now put a 2 abive the one you just connected to, and then DELETE ITS WHOLE ROW

Now look at both A and the colomn connected to, and find the smallest

Keep repeating until ALL ROWS ARE DELEGED

Mimics prims, find smallest weigth, delete row to avoid cycles, then look at both connectors to find the smallest new connection repeat

Question 9

Remember when drawing your final MST, make it eesdied to see as possible

Answer 9

So don’t over,ps them, curve them if needed

Question 10

What complexity is Kruskal and prims?

Answer 10

O (n2)

Question 11

For Kruskal, do you have to show ALL that you crossed out or what

Answer 11

Only until you reach your FINAL ONE