Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
9 Cards in this Set
- Front
- Back
|
Minimum Spanning Tree/ Minimum Connector |
A spanning tree such that the total length of its arcs is as small as possible. |
|
|
What can both Prim's and Kruskal's algorithm do? |
Find the minimum spanning tree. In other words, they find the shortest, cheapest or fastest way of linking all the nodes into one system. |
|
|
Kruskal's Algorithm |
1. Sort all the arcs (edges) into ascending order of weight. 2. Select the arc of least weight to start the tree. 3. Consider the next arc of least weight. - If it would form a cycle with the arcs already selected, reject it. - If it does not form a cycle, add it to the tree. If there is a choice of equal arcs, consider them each in turn. 4. Repeat step 3 until all vertices are connected. |
|
|
Prim's Algorithm |
1. Choose any vertex to start the tree. 2. - Select an arc of least weight that joins a vertex that is already in the tree to a vertex that is not yet in the tree. - If there is a choice of arcs of equal weight, choose randomly. 3. Repeat step 2 until all the vertices are connected. |
|
|
In which form are networks (particularly large ones) often described in? What is useful about this? How does this relate to Prim's algorithm? |
Distance matrix form. Networks can be inputted into computers in this form. Prim's algorithm is easily adapted to a distance matrix, so Prim's algorithm (in matrix form) that is best suited to computerisation. |
|
|
Prim's Algorithm (Distance Matrix Form) |
1. Choose any vertex to start the tree. 2. Delete the row in the matrix for the chosen vertex. 3. Number the column in the matrix for the chosen vertex. 4. Put a ring round the lowest undeleted entry in the numbered columns. (If there is an equal choice, choose randomly.) 5. The ringed entry becomes the next arc to be added to the tree. 6. Repeat steps 2, 3, 4 and 5 until all rows are deleted. |
|
|
Dijkstra's Algorithm |
- Start vertex is given final value of 0. Every vertex directly connected is given a working value: Final value at start + Weight of arc. - Select the smallest working value. This is the final value for that vertex. - Repeat until destination vertex receives its final label. - Find the shorted path by tracing back from destination to start. Include an arc AB on the route if B is already on the route and Final label B - Final label A = weight of arc AB |
|
|
What is Dijkstra's algorithm used for? |
Finding the shortest path between two vertices in a network. |
|
|
Dijkstra's algorithm: draw out the box that replaces each vertex. |
|Vertex | Order of labelling | Final Value | |Working Values | |
