Winter Vacation Training Day 3 (01.29)

Area 3.2 : Prim

Example :

Figure 8.1 : Prim

Prim is the same type as Kruskal.

For the algorithm, we need two arrays, dis[] and vis[].

Step 1, start from a node(Here is 1).

Then set dis[1]=0, vis[1]=1.Update other points by its edges.

Table 8.1-a : Prim(a)

Then, find the mininum edge (1({vis[i]=1}, v) that vis[v]=0(Here is 3), do as that.

Table 8.1-b : Prim(b)

Wait… It seems like Dijkstra.

So, it can be optimized by heap(priority_queue).

If you know that, you can complete the problem with less time.

This is Prim.

Given Score :
    Difficulty : 2
x   Basic Score : 44
Score : 838