Alg_Lab_11 (lll semester)

#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;

void Prima(int* graph[], int V)
{
    int *parent = new int[V];
    int *key = new int[V];
    bool *mstSet = new bool[V];
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;
    key[0] = 0;
    parent[0] = -1;
    for (int count = 0; count < V - 1; count++)
    {
        int min = INT_MAX, min_index;
        for (int v = 0; v < V; v++)
            if (mstSet[v] == false && key[v] < min)
                min = key[v], min_index = v;
        int u = min_index;
        mstSet[u] = true;
        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
                parent[v] = u, key[v] = graph[u][v];
    }
    int sum = 0;
    for (int i = 1; i < V; i++)
    {
        cout << i << " edge " << parent[i] + 1 << "->" << i + 1 << "\t" << graph[i][parent[i]] << endl;
        sum += graph[i][parent[i]];
    }
    cout << "Weight of the minimal skeleton of the graph(Prima): " << sum << endl;
}
int parent[100];
void Kraskal(int* graph[], int V)
{
    int min, mincost = 0;
    int i, j, k, a, b, u, v, ne = 1;
    while (ne < V)
    {
        for (i = 0, min = INT_MAX; i < V; i++)
        {
            for (j = 0; j < V; j++)
            {
                if (graph[i][j] == 0)
                    graph[i][j] = INT_MAX;
                if (graph[i][j] < min)
                {
                    min = graph[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        while (parent[u])
            u = parent[i];
        while (parent[v])
            u = parent[i];
        if (u != v)
        {
            parent[v] = u;
            cout << ne++ << " edge " << (a + 1) << "->" << (b + 1) << "\t" << min << endl;
            mincost += min;
        }
        graph[a][b] = graph[b][a] = INT_MAX;
    }
    cout << "Weight of the minimal skeleton of the graph(Kraskal): " << mincost << endl;
}

int main()
{
    int V;
    cout << "Enter the dimension of the graph: ";
    cin >> V;
    int **VES = new int*[V];
    for (int i = 0; i < V; i++)
        VES[i] = new int[V];
    cout << "Enter weight:" << endl;
    for (int i = 0; i < V; i++)
        cout << "|x" << i + 1;
    cout << endl;
    for (int i = 0; i < V; i++)
    {
        cout << "X" << i + 1 << '|';
        for (int j = 0; j < V; j++)
            cin >> VES[i][j];
    }
    cout << "Edge\t\tWeight" << endl;
    Prima(VES, V);
    Kraskal(VES, V);
    system("pause");
}