Implement Prim’s algorithm using ADT with a time complexity of O(n2).

[anonomyss]

Use
an AI tool and generate C++ code that will implement Prim’s algorithm using ADT with a time
complexity of O(n2).

I should adapt the code to read from txt file.
The output should list the minimum spanning tree paths.

My txt file has values of

7
9
0 1 6
0 2 5
1 4 2
1 6 4
4 5 10
0 3 2
3 4 8
2 6 5
2 5 7

This is the code I got :

#include <iostream>
#include <vector>
#include <limits>

// Function to find the minimum key value from the set of vertices
// not yet included in MST
int findMinKey(const std::vector<int>& key, const std::vector<bool>& mstSet) {
    int minKey = std::numeric_limits<int>::max();
    int minIndex = -1;

    for (int i = 0; i < key.size(); ++i) {
        if (!mstSet[i] && key[i] < minKey) {
            minKey = key[i];
            minIndex = i;
        }
    }

    return minIndex;
}

// Function to print the MST
void printMST(const std::vector<int>& parent, const std::vector<std::vector<int>>& graph) {
    std::cout << "Edge \tWeight\n";
    for (int i = 1; i < graph.size(); ++i) {
        std::cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << "\n";
    }
}

// Function to implement Prim's algorithm using ADT
void primMST(const std::vector<std::vector<int>>& graph) {
    int numVertices = graph.size();

    std::vector<int> parent(numVertices); // Array to store constructed MST
    std::vector<int> key(numVertices); // Key values used to pick minimum weight edge in cut
    std::vector<bool> mstSet(numVertices); // To represent set of vertices included in MST

    // Initialize all keys as infinite and mstSet[] as false
    for (int i = 0; i < numVertices; ++i) {
        key[i] = std::numeric_limits<int>::max();
        mstSet[i] = false;
    }

    // Always include first  vertex in MST
    key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
    parent[0] = -1; // First node is always root of MST

    // The MST will have V vertices
    for (int count = 0; count < numVertices - 1; ++count) {
        // Pick the minimum key vertex from the set of vertices not yet included in MST
        int u = findMinKey(key, mstSet);

        // Add the picked vertex to the MST set
        mstSet[u] = true;

        // Update key value and parent index of the adjacent vertices of the picked vertex
        for (int v = 0; v < numVertices; ++v) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    // Print the constructed MST
    printMST(parent, graph);
}

int main() {
    // Example usage
    std::vector<std::vector<int>> graph = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    primMST(graph);

    return 0;
}

[seeplus]

... and the question is?

[anonomyss]

ok So I changed it to

#include <iostream>
#include <fstream>
#include <vector>
#include <limits>

using namespace std;

// Function to implement Prim's algorithm using ADT
// with a time complexity of O(n^2)
void primAlgorithm(const string& datatest2) {
    // Read data from the text file
    ifstream inputFile(datatest2);
    if (!inputFile.is_open()) {
        cout << "Error opening file." << endl;
        return;
    }

    // Read the number of vertices
    int numVertices;
    inputFile >> numVertices;

    // Create an adjacency matrix to represent the graph
    vector<vector<int>> graph(numVertices, vector<int>(numVertices));

    // Initialize the adjacency matrix with infinity values
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            graph[i][j] = numeric_limits<int>::max();
        }
    }

    // Read the edges and their weights from the file
    int numEdges;
    inputFile >> numEdges;
    for (int i = 0; i < numEdges; i++) {
        int source, destination, weight;
        inputFile >> source >> destination >> weight;
        graph[source][destination] = weight;
        graph[destination][source] = weight;
    }

    // Create a vector to store the minimum spanning tree
    vector<int> mst(numVertices);

    // Create a vector to store the key values of vertices
    vector<int> key(numVertices, numeric_limits<int>::max());

    // Create a vector to store whether a vertex is included in the minimum spanning tree
    vector<bool> included(numVertices, false);

    // Set the key value of the first vertex to 0
    key[0] = 0;

    // Find the minimum spanning tree
    for (int count = 0; count < numVertices - 1; count++) {
        // Find the vertex with the minimum key value
        int minKey = numeric_limits<int>::max();
        int minIndex = -1;
        for (int i = 0; i < numVertices; i++) {
            if (!included[i] && key[i] < minKey) {
                minKey = key[i];
                minIndex = i;
            }
        }

        // Include the selected vertex in the minimum spanning tree
        included[minIndex] = true;

        // Update the key values of adjacent vertices
        for (int i = 0; i < numVertices; i++) {
            if (graph[minIndex][i] != 0 && !included[i] && graph[minIndex][i] < key[i]) {
                key[i] = graph[minIndex][i];
                mst[i] = minIndex;
            }
        }
    }

    // Print the minimum spanning tree
    cout << "Minimum Spanning Tree:" << endl;
    for (int i = 1; i < numVertices; i++) {
        cout << mst[i] << " - " << i << endl;
    }

    // Close the input file
    inputFile.close();
}

int main() {
    // Call the function to implement Prim's algorithm
    // and read data from a text file
    string thePath = "C:\\data\\";
    primAlgorithm(thePath);

    return 0;
}

The file I want it to open is C:\\data\\ and theres a txt file called datatest2.txt but it keep saying error opening file.

[salem c]

Having a parameter variable name of datatest2 doesn't make it a string containing "datatest2.txt".

Make this
string thePath = "C:\\data\\datatest2.txt";

[anonomyss]

thank you, I thought of this just now aswell and it worked

[seeplus]

You don't need L25-30. This can be done as part of L23:

vector<vector<int>> graph(numVertices, vector<int>(numVertices, numeric_limits<int>::max()));