3: Algorithms on graphs

Question 1

What is Kruskal’s?

Answer 1

Sort lengths, select smallest, check if forms cycle, if not add it.

Question 2

What is Prim’s?

Answer 2

Choose any start vertex, select the smallest arc connected to the tree, repeat.

Question 3

Learn Prim’s for tables!

Answer 3

1. Choose start vertex.
2. Delete the row in the matrix for that one.
3. Number the column in the matrix for the chosen vertex.
4. Put a ring around the lowest undeleted entry.
5. The ringed entry becomes the next arc to be added.
6. repeat 2,3,4,5 until all rows have been deleted.

Question 4

What is Dijkstra’s for?

Answer 4

Shortest path from A to B!

Question 5

What is Floyd’s for?

Answer 5

Shortest path from any vertex to another.