We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Prim's (MST) : Special Subtree
  5. Discussions

Prim's (MST) : Special Subtree

Sort by

recency

|

158 Discussions

|

  • yashdeora98294
     + 0 comments

    here is solution in python, java, c++ and c programming - https://programmingoneonone.com/hackerrank-prims-mst-special-subtree-problem-solution.html

  • mrweisu
     + 0 comments

    My naive implementation without using heap. It is still good to try this way at least once I guess :)

    import sys sys.setrecursionlimit(3500)

    def add_a_vertex(covered, uncovered, edges, distance):

    for i, j, w in edges[:]:
    if i in uncovered and j in covered:
        distance[i] = min(distance[i], w)
    if j in uncovered and i in covered:
        distance[j] = min(distance[j], w)

weight = min([i for i in distance.values()])

for k in distance.keys():
    if distance[k] == weight:
        next_vertex = k
        break

covered.add(next_vertex)
uncovered.remove(next_vertex)
del distance[next_vertex]

if len(distance) == 0:
    return weight
else:
    return weight + add_a_vertex(covered, uncovered, edges, distance)

    def prims(n, edges, start): # Write your code here

    weight = 0

covered = set()
covered.add(start)
uncovered = set(range(1,n+1))
uncovered.remove(start)

distance = {}
for i in uncovered:
    distance[i] = float('inf')

# print(f'distance {distance}')

weight += add_a_vertex(covered, uncovered, edges, distance)

return weight

  • vutrantrung14821
     + 0 comments
    def prims(n, edges, start):
    d={}
    score=0
    for i,j,k in edges:
        if i not in d:
            d[i]=[]
        if j not in d:
            d[j]=[]
        d[i].append([j,k])
        d[j].append([i,k])
    dp=deque([[start,0]])
    m=set()
    while dp:
        a=dp[0][0]
        if a in m:
            dp.popleft()
            continue
        score+=dp[0][1]
        r=dp.popleft()
        m.add(r[0])
        for i,j in d[a]:
            if i in m:
                continue
            if len(dp)==0:
                dp.append([i,j])
            else:
                x=0
                y=len(dp)-1
                while y>=x:
                    if j>dp[x][1]:
                        x+=1
                    else:
                        dp.insert(x,[i,j])
                        break
                    if j<dp[y][1]:
                        y-=1
                    else:
                        dp.insert(y+1,[i,j])
                        break    
    return score

  • zoyashah41306
     + 0 comments

    Locksmiths in Barnsley offer professional solutions for your security needs, but when it comes to Prim's (MST) algorithm, it’s all about finding the special subtree. Prim's algorithm is used to create the minimum spanning tree of a graph, starting from any node and gradually adding edges that connect the nearest unconnected nodes. The process ensures minimal total edge weight, forming the most cost-effective and efficient spanning tree for the graph.

  • mah_shamim
     + 0 comments

    /* * Complete the 'prims' function below. * * The function is expected to return an INTEGER. * The function accepts following parameters: * 1. INTEGER n * 2. 2D_INTEGER_ARRAY edges * 3. INTEGER start */

    function prims(edges, Extra open brace or missing close bracemst = [total = 0;

    // Sort edges based on weight
usort(`$edges, function($`a, $b) {
    return `$a[2] - $`b[2];
});

// Prim's algorithm: Add the lowest weight edge that connects to the MST
while (count(`$mst) < $`n) {
    foreach (`$edges as $`edge) {
        list(`$u, $`v, `$w) = $`edge;
        `$uInMST = in_array($`u, $mst);
        `$vInMST = in_array($`v, $mst);

        // Check if one vertex is in MST and the other is not (XOR logic)
        if (`$uInMST xor $`vInMST) {
            // Add vertices to MST
            if (!`$uInMST) $`mst[] = $u;
            if (!`$vInMST) $`mst[] = $v;

            // Add weight to total
            `$total += $`w;
            break;
        }
    }
}

return $total;

    }

    fwrite(result . "\n");

    fclose($fptr);