// Anmol tiwari roll no. 11 panel j
// to add switch case (create menu driven program)

#include <iostream>
#define max 20
using namespace std;

class graph
{
    int cost[max][max];

public:

    int cities;
    graph()
    {
        cout << "Enter the number of cities: ";
        cin >> cities;

        for (int i = 0; i < cities; i++)
        {
            for (int j = 0; j < cities; j++)
            {
                if (i == j)
                    cost[i][j] = 0;
                else
                    cost[i][j] = 999;
            }
        }
    }

    void create();
    void display();
    int primAlg(int startVertex);
};

void graph::create()
{
    char ch;
    for (int i = 0; i < cities; i++)
    {
        for (int j = i + 1; j < cities; j++)
        {
            cout << "Is there a connection between city " << i + 1 << " and city " << j + 1 << "? (y/n): ";
            cin >> ch;

            if (ch == 'y' || ch == 'Y')
            {
                int connectCost;
                cout << "Enter the distance between the two cities: ";
                cin >> connectCost;
                cost[i][j] = connectCost;
                cost[j][i] = connectCost;
            }
        }
    }
}

void graph::display()
{
    cout << "\nAdjacency Matrix:\n";
    for (int i = 0; i < cities; i++)
    {
        for (int j = 0; j < cities; j++)
        {
            if (cost[i][j] == 999)
                cout << "∞ ";
            else
                cout << cost[i][j] << " ";
        }
        cout << endl;
    }
}

int graph::primAlg(int startVertex)
{
    int nearest[max];
    int minCost = 0;

    for (int i = 0; i < cities; i++)
    {
        if (i != startVertex)
            nearest[i] = startVertex;
        else
            nearest[i] = -1;
    }

    cout << "\nEdges in the Minimum Spanning Tree:\n";

    for (int i = 0; i < cities - 1; i++)
    {
        int min = 999, j = -1;

        for (int k = 0; k < cities; k++)
        {
            if (nearest[k] != -1 && cost[k][nearest[k]] < min)
            {
                min = cost[k][nearest[k]];
                j = k;
            }
        }

        cout << "City " << nearest[j] + 1 << " -> City " << j + 1 << " (Cost: " << min << ")\n";
        minCost += min;
        nearest[j] = -1;

        for (int k = 0; k < cities; k++)
        {
            if (nearest[k] != -1 && cost[k][j] < cost[k][nearest[k]])
                nearest[k] = j;
        }
    }

    cout << "\nTotal cost of the Minimum Spanning Tree: " << minCost << endl;
    return minCost;
}

int main()
{
    graph g;
    int choice, startVertex;

    do 
    {
        cout << "\nMenu:\n";
        cout << "1. Create Graph\n";
        cout << "2. Display Graph\n";
        cout << "3. Find MST\n";
        cout << "4. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) 
        {
        case 1:
            g.create();
            break;

        case 2:
            g.display();
            break;

        case 3: 
            cout << "Enter the starting vertex (0 to " << g.cities - 1 << "): ";
            cin >> startVertex;
            if (startVertex < 0 || startVertex >= g.cities)
                cout << "Error: Invalid vertex.\n";
            else
                g.primAlg(startVertex);
            break;        
       
        case 4:
            cout << "Exiting program.\n";
            break;

        default:
            cout << "Invalid choice. Please try again.\n";
            break;
        }
    } while (choice != 5);

    return 0;
}