#include "stdafx.h"
#include <iostream>
int n;
int noe;
int graph_edge [100] [4];
int tree [10] [10];
int sets [100] [10];
int top [100];
using namespace std;

    void read_graph ();
    void initialize_span_t ();
    void sort_edges ();
    void algorithm ();
    int find_node (int);
    void print_min_span_t ();

void read_graph ()
{
cout << "Алгоритм Крускала"<<endl;
cout << "Введіть кількість вершин графа ";
cin >> n;
noe = 0;
cout << "Введіть відстань між вершинами ";
for (int i = 1; i <= n; i ++)
{
        for (int j = i + 1; j <= n; j ++)
{
cout << i << "," << j<<": ";
        int w;
cin >> w;
            if (w != 0)
{
noe ++;
graph_edge [noe] [1] = i;
graph_edge [noe] [2] = j;
graph_edge [noe] [3] = w;
}
}
}
cout << "\n \n Граф має такі відстані між вершинами: \n";
for (int i = 1; i <= noe; i ++)
{
cout << "<" << graph_edge [i] [1]<< "," << graph_edge [i] [2]<< ">: " << graph_edge [i] [3] << endl;
}
}
void sort_edges ()
{

for (int i = 1; i <= noe-1; i ++)
{
    for (int j = 1; j <= noe-i; j ++)
{
        if (graph_edge [j] [3]> graph_edge [j + 1] [3])
{
        int t = graph_edge [j] [1];
graph_edge [j] [1] = graph_edge [j + 1] [1];
graph_edge [j + 1] [1] = t;
t = graph_edge [j] [2];
graph_edge [j] [2] = graph_edge [j + 1] [2];
graph_edge [j + 1] [2] = t;
t = graph_edge [j] [3];
graph_edge [j] [3] = graph_edge [j + 1] [3];
graph_edge [j + 1] [3] = t;
}
}
}
cout << "\n \n Після сортування: \n";
for (int i = 1; i <= noe; i ++)
cout << "" << graph_edge [i] [1]<< "," << graph_edge [i] [2]<< ">: " << graph_edge [i] [3] << endl;
}
void algorithm ()
{
    for (int i = 1; i <= n; i ++)
{
sets [i] [1] = i;
top [i] = 1;
}
cout << "\n Початок алгоритму: \n \n";
    for (int i = 1; i <= noe; i ++)
{
    int p1 = find_node (graph_edge [i] [1]);
    int p2 = find_node (graph_edge [i] [2]);
        if (p1 != p2)
{
cout << "В дерево включено вершину "<< "<" << graph_edge [i] [1] << ","
<< graph_edge [i] [2] << ">" << endl << endl;
tree [graph_edge [i] [1]] [graph_edge [i] [2]] = graph_edge [i] [3];
tree [graph_edge [i] [2]] [graph_edge [i] [1]] = graph_edge [i] [3];
            for (int j = 1; j <= top [p2]; j ++)
{
top [p1] ++;
sets [p1] [top [p1]] = sets [p2] [j];
}
top [p2] = 0;
}
        else
{
cout << "Включення вершини "<< "<" << graph_edge [i] [1] << ","<< graph_edge [i] [2] << ">" << " формує цикл, отож вона видалена \n \n";
}
}
}
int find_node (int n)
{
    for (int i = 1; i <= noe; i ++)
{
        for (int j = 1; j <= top [i]; j ++)
{
        if (n == sets [i] [j])
            return i;
}
}
    return 999;
}
void print_min_span_t ()
{
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
cout << tree [i] [j] << " ";
cout << endl;
}
}

int main ()
{
setlocale(LC_ALL, "rus");
read_graph ();
sort_edges ();
algorithm ();
print_min_span_t ();
setlocale(LC_ALL, "OCP");
system("pause");
    return 0;
}