3. Algorithms on Graphs Flashcards
1
Q
Define the term MST (Minimum Spanning Tree)
A
A spanning tree such that the total length of its arc is as small as possible
2
Q
Name the 2 algorithms used to find the MST
A
- Kruskal’s algorithm
2. Prim’s algorithm
3
Q
What are the steps to Kruskal’s algorithm?
A
- Sort arcs into ascending order of weight
- Select arc of least weight to start the tree
- Consider the next arc of least weight
- If the arc forms a cycle, reject it
- If it does not, add it to the tree
- Repeat steps 3-5 until all vertices are added
4
Q
What are the steps to Prim’s algorithm?
A
- Choose any vertex to start tree.
- Select an arc of least weight that joins a vertex already in the tree to a vertex that is not
- Repeat step 2 until all vertices are added
5
Q
What are the steps to Prim’s algorithm in a distance matrix?
A
- Choose any vertex to start the tree
- Delete row in matrix of chosen vertex
- Number the column in matrix for chosen vertex
- Put a ring around the lowest undeleted entry in the numbered columns
- Ringed entry becomes next arc to be added to tree
- Repeat steps 2-5 until all rows have been deleted
6
Q
What is Dijkstra’s algorithm used for?
A
Finding the shortest route between two vertices
7
Q
What are the steps to Dijkstra’s algorithm?
A
- Label start vertex S with a final label 0
- Record a working value for each vertex that is directly connected to the vertex that just received a label
- Look at working values of all values with no final label and select the smallest one which becomes the final label for that vertex
- Repeat steps 2-3 until destination vertex receives its final label
- To find the shortest path, trace back from the destination vertex to the start vertex where the final labels subtracted equal the weight of the arc