Minimum Spanning Trees and Greedy Algorithms (VCE SSCE General Mathematics): Flashcards

Connected graph; no cycles, loops, or multiple edges

$n - 1$ edges

Tree connecting all vertices in a connected graph

Spanning tree with smallest possible total weight

Edges from vertices already in the tree

Smallest edge from anywhere, avoiding cycles

Prim's expands from vertex; Kruskal's sorts all edges

Makes best choice at each step for optimal solution

Find shortest path between two specific vertices

Step-by-step instructions to solve a problem or task