Algorithms On Graphs Flashcards
1
Q
What is a minimum spanning tree?
A
The smallest possible spanning tree able to be formed
2
Q
What is kruskals algorithm used for?
A
Finding a minimum spanning tree
3
Q
How do you perform kruskals algorithm?
A
- sort ascending weight
- smallest arc starts tree
- add arcs in ascending order
- reject any arcs that form a cycle
4
Q
What does prims algorithm do?
A
Finds a minimum spanning tree
5
Q
How do you perform prims algorithm?
A
- choose any node to start
- select the smallest connected arc to a node that isn’t yet in the tree
- repeat until all are connected
6
Q
Which algorithm can be applied to a distance matrix?
A
Prims algorithm
7
Q
How do you perform prims algorithm using a matrix?
A
- choose any node
- delete its corresponding row and number accordingly
- ring the lowest Undeleted entry in numbered columns
- this become the next arc
- repeat until all rows are deleted
8
Q
What is Dijkstra’s algorithm used for?
A
To find the shortest path between two nodes in a network
