D1, C3 - Algorithm's on Graphs Flashcards
What is a minimum spanning tree
A spanning tree of minimum weight
What are the steps of Kruskal’s algorithm
1) List the edges in ascending weight
2) Start with the edge with least weight to start the graph
3) Look at the edge with the next lowest weight. Do NOT use if edge forms a cycle. Add it to tree if doesn’t form a cycle
4) Repeat until all vertices are connected
What should you do in Kruskal’s algorithm if there are more than once choice
Look at each choice in turn
What is Prim’s algorithm
1) Start at any vertex
2) Choose the edge with the lowest weight to join a vertex not yet in the tree
3) Repeat until all vertices are in the tree
What are the differences between Kruskal’s and Prim’s algorithm
Kruskal’s jumps around and starts at the lowest weighted edge
Prim’s grows and starts at any vertex
How do you apply Prim’s algorithm to a distance matrix
1) Choose any starting vertex
2) Delete this row
3) Number this column (1, 2, …)
4) Circle the lowest undeleted number (in any numbered column)
5) Repeat steps 2-4 with the circle number and repeat until all rows have been deleted
If you have n values in row A (e.g. 6) and need to find the lowest number, how many comparisons are required to find the smallest / largest value
n - 1
e.g. 5
How many comparisons are needed for an n * n distance matrix
(n-1) values –> (n-1)-1 comparisons
2(n-2) values –> 2(n-2)-1
3(n-3) values –> 3(n-3)-1
…
(n-1)(n-(n-1) values –> (n-1)(n-(n-1))-1
Answer: (n^3 - 7n + 6) / 6
For an n * n matrix you need to do (n^3 - 7n + 6) / 6 comparisons, what is the order of this implementation in terms of the number of vertices, n
Order is n^3 (greater power)
What does Dijkstra’s algorithm do
Allows us to find shortest path through a network
What goes in each of the boxes for Dijkstra’s algorithm (left, middle, right, bottom)
Left- vertex label
Middle- order of labelling
Right- final label (value)
Bottom (working values)
What working value should you use for Dijkstra’s algorithm
The smallest one
How do you perform Dijkstra’s algorithm
1) Label the start vertex (order of labelling 1, final label 0)
2) Look at the vertices directly connected to the last vertex, add the weight of these vertices and write down this working value(s)
3) Select the vertex with the smallest working value and make this the final label, and add the order of labelling (2,3,4,…)
4) Repeat steps 2-4
5) Repeat until the end vertex has a final label
What does Floyd’s algorithm do
Finds the shortest distance between any two vertices in a network
How do you perform Floyd’s algorithm
1) Complete a distance table and a route table for the network
2) Make a copy of the first row and column (A) of the distance table (and the dashes -) and highlight this row/column
3) Look at the unshaded part of the table and compare the row / column total with the original distance table
3a) If the ‘copy table’ total < original table, change distance table value and change route table letter
3b) If the ‘copy table’ total >= original table, copy over distance / route from original table
4) Copy the ‘copy table’ and highlight the next row / column (B) (this is one iteration)
5) Repeat from steps 3-4 until all rows / columns are complete
