# Chapter 3 Algorithms on Graphs Flashcards

What is a MST?

Minimum spanning tree

A MST is a spanning tree such that the total lengths of all its arcs is as small as possible

What are the 4 algorithms you need to know?

Kruskal’s

Prim’s

Dijkstra’s

Floyd’s

What is a tree?

A tree is a connected graph with no cycles

What is a spanning tree?

A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree

What is a MST sometimes called?

A minimum connector

State Kruskal’s algorithm?

What can Kruskal’s algorithm be used for?

Finding the MST

What is counter intuitive when using Kruskal’s algorithm?

It may grow as 2 unconnected graphs but it will always finish as 1 connected spanning tree

What can Prim’s algorithm be used for?

Finding the MST

State Prim’s algorithm?

What is the main difference between Kruskal’s algorithm and Prim’s algorithm?

The difference between Prim’s and Kruskal’s algorithm is that Prim’s algorithm considers vertices whereas Krukal’s algorithm considers edges

What 2 versions of Prim’s algorithm do you need to know?

A normal graph version and a distance matrix version

State the distance matrix form of Prim’s algorithm?

When using the distance matrix form Prim’s algorithm what workings out do you need to show?

The final annotated table

Plus

A list of arcs in the correct order

What is a practical application of Dijkstra’s algorithm?

Finding the cheapest or fastest way to transport goods

What can Dijkstra’s algorithm be used to find?

(In terms of graph theory)

Dijkstra’s algorithm can be used to find the shortest path through S and T through a network

How do you pronounce Dijkstra?

Dike-Stra

State Dijkstra’s algorithm?