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.

/* * 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, mst = [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);

include

using namespace std;

string ltrim(const string &); string rtrim(const string &); vector split(const string &);

int prims(int n, vector> edges, int start) { vector>> graph(n + 1);

// Constructing the graph from the given edges
for (auto& edge : edges) {
    int u = edge[0];
    int v = edge[1];
    int w = edge[2];
    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
}

// Priority queue to store the edges based on weights
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

vector<bool> visited(n + 1, false);
visited[start] = true;

// Adding edges connected to the starting node to the priority queue
for (auto& edge : graph[start]) {
    pq.push({edge.second, edge.first});
}

int minWeight = 0;

// Applying Prim's algorithm
while (!pq.empty()) {
    pair<int, int> p = pq.top();
    pq.pop();
    int u = p.second;
    int weight = p.first;

    // If the node is already visited, continue to the next iteration
    if (visited[u]) {
        continue;
    }

    // Mark the node as visited and add its weight to the minimum weight
    visited[u] = true;
    minWeight += weight;

    // Add all the edges connected to the current node to the priority queue
    for (auto& edge : graph[u]) {
        if (!visited[edge.first]) {
            pq.push({edge.second, edge.first});
        }
    }
}

return minWeight;

}

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string first_multiple_input_temp;
getline(cin, first_multiple_input_temp);

vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

int n = stoi(first_multiple_input[0]);
int m = stoi(first_multiple_input[1]);

vector<vector<int>> edges(m);

for (int i = 0; i < m; i++) {
    edges[i].resize(3);

    string edges_row_temp_temp;
    getline(cin, edges_row_temp_temp);

    vector<string> edges_row_temp = split(rtrim(edges_row_temp_temp));

    for (int j = 0; j < 3; j++) {
        int edges_row_item = stoi(edges_row_temp[j]);

        edges[i][j] = edges_row_item;
    }
}

string start_temp;
getline(cin, start_temp);

int start = stoi(ltrim(rtrim(start_temp)));

int result = prims(n, edges, start);

fout << result << "\n";

fout.close();

return 0;

}

string ltrim(const string &str) { string s(str);

s.erase(
    s.begin(),
    find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);

return s;

}

string rtrim(const string &str) { string s(str);

s.erase(
    find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
    s.end()
);

return s;

}

vector split(const string &str) { vector tokens;

string::size_type start = 0;
string::size_type end = 0;

while ((end = str.find(" ", start)) != string::npos) {
    tokens.push_back(str.substr(start, end - start));

    start = end + 1;
}

tokens.push_back(str.substr(start));

return tokens;

}

python3

def prims(n, edges, start):
    
    mst = {start}
    total = 0
    edges.sort(key=lambda x: x[2])

    # Prim: Add lowest weight edge that starts anywhere in the mst and ends on any of the remaining vertices (guarantees no cycles), until no vertices remain.
    while len(mst) < n:
        for u, v, w in edges:
            if (u in mst) ^ (v in mst):
                mst = mst.union({u, v})
                total += w
                break
    return total