x Turn on thread page Beta
 You are Here: Home >< Maths

# AQA D1 Prims algorithm help watch

1. I can do the algorithm however after I finish it all the lines do not connect and I need to pick a line to connect this. Is there a way without drawing a diagram that I can do this?
Also when I write my lines like this
EG 13
AC 15
AB 18
DE 19
FG 27

do they have to be in size order to get the marks or doesn't it matter?]

EDIT: Kruskals algorithm not prims wrong title
2. (Original post by Sayless)
I can do the algorithm however after I finish it all the lines do not connect and I need to pick a line to connect this. Is there a way without drawing a diagram that I can do this?
Also when I write my lines like this
EG 13
AC 15
AB 18
DE 19
FG 27

do they have to be in size order to get the marks or doesn't it matter?
For your first question, look at all the possible options and pick the one with the least weight. There can't be that many of them left!

For your second question, I'm not familiar with AQA but I would hope that it doesn't matter which order you write them in.
3. (Original post by SeanFM)
For your first question, look at all the possible options and pick the one with the least weight. There can't be that many of them left!

For your second question, I'm not familiar with AQA but I would hope that it doesn't matter which order you write them in.
Thanks, do you have to draw all the lines out in order to decide which one will connect them all together?
4. If you've done the algorithm correctly you should be able to get from one point to any other point, without drawing an additional line. all the lines don't need to be connected, but you shouldn't have any points that can't reach any other.

you should write them out in the order that you select each line, that's what you'll get the marks for, more than the answer, is the method. So write them down in the order you work them out
5. (Original post by Sayless)
Thanks, do you have to draw all the lines out in order to decide which one will connect them all together?
That would be the best way to do it - if you're not given a template then you could make a neat shape depending on how many vertices you have (maybe a square of some sort).
6. (Original post by Sayless)
I can do the algorithm however after I finish it all the lines do not connect and I need to pick a line to connect this. Is there a way without drawing a diagram that I can do this?
Also when I write my lines like this
EG 13
AC 15
AB 18
DE 19
FG 27

do they have to be in size order to get the marks or doesn't it matter?]

EDIT: Kruskals algorithm not prims wrong title
With 7 vertices you'll need 6 edges (number of vertices - 1).
I don't know how AQA questions are worded, but since Kruskal involves picking the smallest edge first, etc, you can only show that you have applied the algorithm properly if you list the edges in ascending length, i.e. in the order that you picked them.
7. (Original post by tiny hobbit)
With 7 vertices you'll need 6 edges (number of vertices - 1).
I don't know how AQA questions are worded, but since Kruskal involves picking the smallest edge first, etc, you can only show that you have applied the algorithm properly if you list the edges in ascending length, i.e. in the order that you picked them.
what are vertices?

also i use the algorithm and do the first 6 in correct ascending order, then i draw the diagram to find the 7th one which connects them all together and stick that one at the end e.g looking something like this

EG 13
AC 15
AB 18
DE 19
FG 27
BE 21 (One which connects them all together)

would that be right since i don't know how to find it out without drawing the diagarm and using that to visually see there is a gap, then i pick the smallest unused length
8. (Original post by Sayless)
what are vertices?

also i use the algorithm and do the first 6 in correct ascending order, then i draw the diagram to find the 7th one which connects them all together and stick that one at the end e.g looking something like this

EG 13
AC 15
AB 18
DE 19
FG 27
BE 21 (One which connects them all together)

would that be right since i don't know how to find it out without drawing the diagarm and using that to visually see there is a gap, then i pick the smallest unused length
A vertex (plural vertices) is another word for a node.

If you are using Kruskal's algorithm properly, your sequence of edges (arcs) must be in increasing size all the way, so you can't have 27 then 21.

I don't understand why you would be doing this without already having a diagram. Having looked at a few AQA exam papers, there is always a drawing of the original graph. You should therefore mark on the edges as you include them, so that you know when it is joined up. But you should always consider the edges starting with the shortest and then the second shortest, etc. The safest way (even if it is a bit tedious) is to make a list of all the edges in order of size and then go through deciding whether to include them on your tree or not, by deciding whether they make a cycle (in which case don't use them).
9. (Original post by tiny hobbit)
A vertex (plural vertices) is another word for a node.

If you are using Kruskal's algorithm properly, your sequence of edges (arcs) must be in increasing size all the way, so you can't have 27 then 21.

I don't understand why you would be doing this without already having a diagram. Having looked at a few AQA exam papers, there is always a drawing of the original graph. You should therefore mark on the edges as you include them, so that you know when it is joined up. But you should always consider the edges starting with the shortest and then the second shortest, etc. The safest way (even if it is a bit tedious) is to make a list of all the edges in order of size and then go through deciding whether to include them on your tree or not, by deciding whether they make a cycle (in which case don't use them).
Theres a diagram on the question but it is a fully connected diagram not a minimum span diagram.

I use Kurskal's algorithm to get the smallest sides in order however, if I have AB and CA I won't use another AB line since I already have an A and B component in use already.

I do this in order then at the end I draw a minimum spam diagram, then if I look at it then it is missing a connection, so it is broken. I will relook at the pre minimum span diagram given in the question and looking for the shortest unused side which when drawn on my minimum span diagram, will connect it all together.

I add the smallest unused side at the end of all of my algorithm since I can only do it at the end as thats the only time I know when a side is unused and/if my minimum span diagram is fully connected or not.

I do it increasing all the way, without using the same letter twice as stated above, then at the end I will put it the smallest unused side in order to connect it together as a minimum span diagram.
10. (Original post by Sayless)
Theres a diagram on the question but it is a fully connected diagram not a minimum span diagram.

I use Kurskal's algorithm to get the smallest sides in order however, if I have AB and CA I won't use another AB line since I already have an A and B component in use already.

I do this in order then at the end I draw a minimum spam diagram, then if I look at it then it is missing a connection, so it is broken. I will relook at the pre minimum span diagram given in the question and looking for the shortest unused side which when drawn on my minimum span diagram, will connect it all together.

I add the smallest unused side at the end of all of my algorithm since I can only do it at the end as thats the only time I know when a side is unused and/if my minimum span diagram is fully connected or not.

I do it increasing all the way, without using the same letter twice as stated above, then at the end I will put it the smallest unused side in order to connect it together as a minimum span diagram.
Are A, B etc your nodes (vertices, points) or are they your edges (arcs, lines)?

If A, B etc are your nodes, what you are doing is not Kruskal's algorithm.
11. (Original post by tiny hobbit)
Are A, B etc your nodes (vertices, points) or are they your edges (arcs, lines)?

If A, B etc are your nodes, what you are doing is not Kruskal's algorithm.
AB is an edge, A is a point on the edge, yeah it is kruskals algorithm though

e.g F-----------G
that is the edge FG
12. (Original post by Sayless)
AB is an edge, A is a point on the edge, yeah it is kruskals algorithm though

e.g F-----------G
that is the edge FG
Right then. Once you have chosen AB, there is no reason why you can't next choose another edge going from A or B. In fact, if one of those is the next shortest, then you must choose that edge. What you must not do is choose an edge which causes you to draw a cycle, e.g a triangle or a quadrilateral. Drawing the edges that you have already chosen on the diagram of the whole graph helps you to look out for cycles.
13. (Original post by tiny hobbit)
Right then. Once you have chosen AB, there is no reason why you can't next choose another edge going from A or B. In fact, if one of those is the next shortest, then you must choose that edge. What you must not do is choose an edge which causes you to draw a cycle, e.g a triangle or a quadrilateral. Drawing the edges that you have already chosen on the diagram of the whole graph helps you to look out for cycles.
Thats prims algorithm, prims algorithm is starting from A and going from there for the shortest unused sides, not jumping around.

kruskals is just choosing the smalling unused side and putting it in order without making a cycle,

but i understand the part about drawing the edges on the whole graph to look for cycles i'll do that in future to help me notice it, i guess i could always do my method then cross it all out and rewrite it but in order and they'll never know
14. (Original post by Sayless)
Thats prims algorithm, prims algorithm is starting from A and going from there for the shortest unused sides, not jumping around.

No, Prim's goes to the nearest vertex, which may mean that the edges you pick are not gradually increasing in size.

kruskals is just choosing the smalling unused side and putting it in order without making a cycle,

Yes, but that smallest unused side may come from one of the vertices you've already used. You are ignoring some of the possible options.

but i understand the part about drawing the edges on the whole graph to look for cycles i'll do that in future to help me notice it, i guess i could always do my method then cross it all out and rewrite it but in order and they'll never know
They will notice you've done it wrongly if your tree is not the shortest possible, which it may well not be, the way you are doing it.

You could have a look at https://www.youtube.com/watch?v=5XkK88VEILk

I suggest that you don't argue too much with people who try to help you by telling you where you are going wrong. It may be that they know better than you.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: October 18, 2015
Today on TSR

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams