Further Maths - Prim's Algorithm

Created: November 08, 2021
Updated: August 24, 2024

---

See Also

• [[Further Maths - Graphs]]^A
• [[Further Maths - Kruskal’s Algorithm]]^A

Flashcards

What is the first step of Prim’s algorithm?

---

Choosing any start vertex.

What do you do after choosing a first vertex for Prim’s algorithm?

---

Repeatedly choose the shortest edge that connects a new vertex.

What is the worst-case complexity of Prim’s algorithm?

---

\[O(n^3)\]

---

Related posts

• [[Further Maths - Graphs]]^A

  (outgoing)
• [[Further Maths - Kruskal's Algorithm]]^A

  (outgoing)
• [[Further Maths - Syllabus]]^A

  (incoming)
• [[Further Maths - Travelling Salesperson Problem]]^A

  (incoming)
• [[List of algorithms to memorise for DAA]]^U

  (sim: 0.523)
• [[Lecture - DAA HT23, XIV]]^U

  (sim: 0.504)
• [[Lecture - DAA HT23, XI]]^U

  (sim: 0.504)