3 - Algorithms on Graphs Flashcards
Define minimum spanning tree.
A minimum spanning tree is a tree that contains all vertices and the total length of its arcs (or total weight) is as small as possible.
What is Kruskal’s algorithm?
.Sort arcs into ascending order of weight.
.Select arc of least weight.
.Select next arc of least weight - reject if forms a cycle or add to tree if it doesn’t.
.Consider each arc in turn if equal then repeat step 3 until all vertices are connected.
What is Prim’s algorithm?
.Choose a vertex to start the tree.
.Select arc of least weight joining a vertex already in the tree to one not in the tree and choose any if of equal weight.
.Repeat step 2 until all vertices are connected.
How do you use create the matrix form of Prim’s algorithm?
.Choose vertex to start the tree.
.Delete row of chosen vertex.
.Number column of chosen vertex.
.Put a ring around the lowest undeleted entry in numbered columns.
.Add ringed entry to tree.
.Repeat until all rows are deleted.
What is Dijkstra’s algorithm?
.Start is S, final label 0.
.Write working values for anything directly connected to anything receiving it’s final label, replace if smaller than current and don’t write if it already has a final label.
.Select smallest working value and make it the final label of an unlabelled vertex.
.Repeat.
.Trace end to start as vertex - previous final label = that arc.
What does Dijkstra’s algorithm give you?
The shortest route between the start vertex and any other vertex with a final label. Can also be used on digraphs.
