[Programmers - Graph] Prim Algorithm, Fallest node question.

---

Getting Started

 

At first, I have a mind to only deal with the algorithm solutions, but after considering, I thought additionally writing about the related data structures or algorithm theories is more effective. So I decide to modify the original page.

By the way, this time, I'll introduce the prim algorithm.

... is greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

https://en.wikipedia.org/wiki/Prim%27s_algorithm

Of course, the start line is the graph.

 

However, now I don't need to explain the basics of graph. But if you need that, I have a mind for write about that.

 

---

What is prim algorithm?

 

In fact, it is a very popular algorithm, so if you search on YouTube, there are many videos that are easily explained.

https://www.youtube.com/results?search_query=prim+algorithm

https://www.youtube.com/results?search_query=prim+algorithm

The prim algorithm makes a minimum spanning tree which expresses the minimum cost from the root.

 

Here is my acknowledges.

1. Make it possible to record distance values at all vertices. And all are recorded to infinity.
2. (Randomly) Take one vertex and set 0 to that vertex as distance value.
3. Visit the other vertices connected to the selected vertex.
4. At this time, if the distance value is smaller, it is updated and the vertex is stored in the queue.
5. Take one from the queue and continue the 3-4 processes.

Actually it is difficult to understand in texts, so I will explain it with pictures.

 

---

Process 1.

 

As I said, Make it possible to record distance values at all vertices. And all are recorded to infinity. In this figure, I select the A.

 

---

Process 2, 3.

 

 

So, set the value 0 to A and pop the A from the queue, then Visits the connected vertices with A.

 

---

Process 4.

 

In the case of C, infinity is smaller than 0+5=5. So that updates the value of C to 5.

 

---

Keep Going.

 

Repeat the above processes.

 

Then, we get the minimum spanning tree which start from the A.

 

Perhaps we can optimize the whole process, like preventing the duplicated vertices in the queue.

 

---

Time Complexity

 

Refer from wiki

Prim's algorithm - Wikipedia

Minimum edge weight data structure	Time complexity (total)
adjacency matrix, searching	$ O(\lvert{V}\rvert^2) $
binary heap and adjacency list	$ O((\lvert{V}\rvert+\lvert{E}\rvert)log\lvert{V}\rvert) $
Fibonacci heap and adjacency list	$ O(\lvert{E}\rvert+\lvert{V}\rvert log\lvert{V}\rvert) $

You can notice that data structure affects the time complexity of prim algorithm. For example, the binary heap and adjacency list save more time than just using the adjacency matrix. (related explain) Because it records the minimum weight(distance) from heap to vertex, not a cumulative value.

 

---

Related Question

 

This is what can be solved by prim algorithm. Because it demands the minimum distance from the specific vertex.

 

Goto [Programmers Graph Level 3] 가장 먼 노드

코딩테스트 연습 - 가장 먼 노드

This is solution in $O(\lvert{V}\rvert^2)$.

Google Colaboratory