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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Name the 2 algorithms used to find the MST

A
  1. Kruskal’s algorithm

2. Prim’s algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are the steps to Kruskal’s algorithm?

A
  1. Sort arcs into ascending order of weight
  2. Select arc of least weight to start the tree
  3. Consider the next arc of least weight
  4. If the arc forms a cycle, reject it
  5. If it does not, add it to the tree
  6. Repeat steps 3-5 until all vertices are added
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the steps to Prim’s algorithm?

A
  1. Choose any vertex to start tree.
  2. Select an arc of least weight that joins a vertex already in the tree to a vertex that is not
  3. Repeat step 2 until all vertices are added
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the steps to Prim’s algorithm in a distance matrix?

A
  1. Choose any vertex to start the tree
  2. Delete row in matrix of chosen vertex
  3. Number the column in matrix for chosen vertex
  4. Put a ring around the lowest undeleted entry in the numbered columns
  5. Ringed entry becomes next arc to be added to tree
  6. Repeat steps 2-5 until all rows have been deleted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is Dijkstra’s algorithm used for?

A

Finding the shortest route between two vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the steps to Dijkstra’s algorithm?

A
  1. Label start vertex S with a final label 0
  2. Record a working value for each vertex that is directly connected to the vertex that just received a label
  3. Look at working values of all values with no final label and select the smallest one which becomes the final label for that vertex
  4. Repeat steps 2-3 until destination vertex receives its final label
  5. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly