// kruskal.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include "stdafx.h"
#include <vector>
#include <queue>
#include <climits>
#include <iostream>
#include <conio.h>
#include <locale.h>
#include <ctime>
#include <iomanip>
#include <array>
using namespace std;
int weight,visited[20],d[20],p[20];
int **new_weight = new int*[weight];
int v,e;
int sizeArray;
int **creategraph()
{
	cout<<"Введите количество вершин"<<endl;
	cin>>sizeArray;
	int ** mas = new int *[sizeArray];
	for(int i = 0; i< sizeArray; i++)
	{
		mas[i] = new int[sizeArray];
	}
	for(int i = 0; i < sizeArray; i++)
	{
		for(int j = 0; j < sizeArray; j++)
		{
			mas[i][j] ;
			scanf_s("%d",&mas[i][j]);
		}
	}
	return mas;
};

int **graphrandom()
{
	cout<<"Введите количество вершин"<<endl;
	cin>>sizeArray;
	int ** mas = new int *[sizeArray];
	for(int i = 0; i< sizeArray; i++)
	{
		mas[i] = new int[sizeArray];
	}
	for(int i = 0; i < sizeArray; i++)
	{
		for(int j = 0; j < sizeArray; j++)
		{
			mas[i][j]= rand()%20+1 ;
		}
	}
	return mas;
};
void printmatrix(int **graph)
{
	cout<<"Введенный массив:"<<endl;
	for(int i = 0; i < sizeArray; i++)
	{
		for(int j = 0; j < sizeArray; j++)
		{
			cout << graph[i][j]<< "    ";
		}
		cout<<endl;
	}
};
void printrandom(int **graph)
{
	cout<<"Созданный массив:"<<endl;
	for(int i = 0; i < sizeArray; i++)
	{
		for(int j = 0; j < sizeArray; j++)
		{
			cout << graph[i][j] << "   ";
		}
		cout<<endl;
	}

};



void kruscal()//вот тут переделать алгоритм под мои массивы
{
int current,totalvisited,mincost,i;
current=1;d[current]=0;
totalvisited=1;
visited[current]=1;
while(totalvisited!=v)
{
  for(i=1;i<=v;i++)
  {
    if(new_weight[current][i]!=0)
      if(visited[i]==0)
    if(d[i]>new_weight[current][i])
    {
      d[i]=new_weight[current][i];
      p[i]=current;
    }
  }
  mincost=32767;
  for(i=1;i<=v;i++)
  {
    if(visited[i]==0)
      if(d[i]<mincost)
      {
    mincost=d[i];

    current=i;
      }
  }
  visited[current]=1;
  totalvisited++;
}
mincost=0;
for(i=1;i<=v;i++)
  mincost+=d[i];
  cout<<"\nМинимальный вес=  "<<mincost;
cout<<"\nМинимальное остовное дерево:  ";
for(i=1;i<=v;i++)
  cout<<"\nНачальная вершина  "<<i<<" конечная  "<<p[i];
_getch();
}
void cra()
{
	
};



int _tmain(int argc, _TCHAR* argv[])
{
	setlocale(LC_ALL, ".1251");
	
	int numberSelectMenu;
	printf("Меню: \n\r");
	printf("1. Создание графа и заполнение в ручную \n\r");
	printf("2. Создание графа и заполнение автоматически случайным образом \n\r");
	printf("Введите пункт меню: ");
	cin >> numberSelectMenu;
	switch (numberSelectMenu)
	{
	case 1:
		{
			int **graph = creategraph();
			printmatrix(graph);
			kruscal();
			break;
		}
	case 2:
		{
			int **graph = graphrandom();
			printrandom(graph);
			kruscal();
			break;
		   }
	default:
		break;
	}

kruscal();
_getch();

}
