Further Maths - Prim's Algorithm

Created: November 08, 2021 | Updated: August 24, 2024 | Read markdown | About these notes | View in context | Study these flashcards | Expand all

---

See Also

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

Flashcards

What is the first step of Prim’s algorithm?

656676f06b5742d0bcf3b803d7904dad

Choosing any start vertex.

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

4c76ebe470424e838ac7e6e6987e9217

Repeatedly choose the shortest edge that connects a new vertex.

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

29900a40f472400cbc359da43c8ac297

\[O(n^3)\]

---

Related posts

• Further Maths - Graphs^A

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

  (outgoing)
• Further Maths - Travelling Salesperson Problem^A

  (incoming)
• Further Maths - Dijkstra's Algorithm^A

  (sim: 0.475)
• Further Maths - Syllabus^A

  (incoming)
• Computing - Searching Graphs^A

  (sim: 0.496)
• List of algorithms to memorise for DAA^U

  (sim: 0.502)