#include<iostream>
#include<iomanip>
#include<string>
#include<fstream>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<array>
#include<vector>
#include<map>
#include<queue>
using namespace std;
class MapInit {
public:
int num;
int** datainit;
char* name;
MapInit(int num)
{
this->num = num;
name = new char[num];
for (int i = 0; i < num; i++)
{
datainit = new int* [num];
}
for (int i = 0; i < num; i++)
{
datainit[i] = new int[num];
}
for (int i = 0; i < num; i++)
{
cin >> name[i];
}
for (int i = 0; i < num; i++)
{
for (int j = 0; j < num; j++)
{
cin >> datainit[i][j];
}
cout << "---------------------" << endl;
}
}
};
void Prim_D(MapInit map)
{
int num = map.num;
int* length = new int[num];
char* pre = new char[num];
bool* Isvisited = new bool[num];
for (int i = 0; i < num; i++)
{
length[i] = map.datainit[0][i];
Isvisited[i] = false;
pre[i] = map.name[0];
}
//0 表示已经访问过
Isvisited[0] = true;
length[0] = 0;
int count = 0;
while (count < num - 1)
{
count++;
int min = INT_MAX;
int minpoint;
for (int i = 0; i < num; i++)
{
if (Isvisited[i] == false && length[i] != -1 && length[i] < min)
{
min = length[i];
minpoint = i;
}
}
//我们这里得到连接在X上最小的点
cout << pre[minpoint] << " -> " << map.name[minpoint] <<" : "<<min<< endl;
Isvisited[minpoint] = true;
for (int i = 0; i < num; i++)
{
if (map.datainit[minpoint][i] != -1)
{
if (length[i] ==-1&&Isvisited[i]==false)
{
length[i] = map.datainit[minpoint][i];
pre[i] = map.name[minpoint];
}
else if (length[i] > map.datainit[minpoint][i]&&Isvisited[i]==false)
{
length[i] = map.datainit[minpoint][i];
pre[i] = map.name[minpoint];
}
}
}
}
}
void Dijkatre_D(MapInit map,int startpoint)
{
int num = map.num;
int* length = new int[num];
char* pre = new char[num];
bool* Isvisited = new bool[num];
for (int i = 0; i < num; i++)
{
length[i] = map.datainit[startpoint][i];
Isvisited[i] = false;
pre[i] = map.name[startpoint];
}
Isvisited[startpoint] = true;
length[startpoint] = 0;
int count = 0;
while (count < num - 1)
{
count++;
int min = INT_MAX;
int minpoint;
for (int i = 0; i < num; i++)
{
if (Isvisited[i] == false && length[i] != -1 && length[i] < min)
{
min = length[i];
minpoint = i;
}
}
//我们这里得到连接在X上最小的点
cout << pre[minpoint] << " -> " << map.name[minpoint] << " : " << min << endl;
Isvisited[minpoint] = true;
for (int i = 0; i < num; i++)
{
if (map.datainit[minpoint][i] != -1)
{
if (length[i] == -1 && Isvisited[i] == false)
{
length[i] = map.datainit[minpoint][i]+length[minpoint];
pre[i] = map.name[minpoint];
}
else if (length[i] > map.datainit[minpoint][i]+length[minpoint]&&Isvisited[i]==false)
{
length[i] = map.datainit[minpoint][i]+length[minpoint];
pre[i] = map.name[minpoint];
}
}
}
}
for (int i = 0; i < num; i++)
{
cout << length[i];
}
cout << endl;
for (int i = 0; i < num; i++)
{
cout << pre[i];
}
cout << endl;
}
void Floyd(MapInit map)
{
int num = map.num;
int** a = new int* [num];
for (int i = 0; i < num; i++)
{
a[i] = new int[num];
}
for (int i = 0; i < num; i++)
{
for (int j = 0; j < num; j++)
{
a[i][j] = map.datainit[i][j];
}
}
for (int p = 0; p< num; p++)
{
for (int i = 0; i < num; i++)
{
for (int j = 0; j < num; j++)
{
if (a[i][j] == -1&&i!=j)
{
if (a[i][p] != -1 && a[p][j] != -1)
{
a[i][j] = a[i][p] + a[p][j];
}
}
else if(a[i][j] !=-1)
{
if (a[i][p] != -1 && a[p][j] != -1 && a[i][p] + a[p][j] < a[i][j])
{
a[i][j] = a[i][p] + a[p][j];
}
}
}
}
}
for (int i = 0; i < num; i++)
{
for (int j = 0; j < num; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
}
class line{
public:
int start;
int end;
int length;
friend bool operator<(line a, line b);
};
bool operator <(line a,line b)
{
if (a.length == b.length)
{
return false;
}
else if (a.length == -1)
{
return false;
}
else if (b.length == -1)
{
return true;
}
else if (a.length < b.length)
{
return true;
}
else
{
return false;
}
}
bool Samefather(int a, int b, int* pre)
{
return pre[a] == pre[b];
}
void Kruskal(MapInit map)
{
int num = map.num;
vector<line> newlinevector;
for (int i = 0; i < num; i++)
{
for (int j = i; j < num; j++)
{
newlinevector.push_back({ i,j,map.datainit[i][j] });
}
}
sort(newlinevector.begin(), newlinevector.end());
vector<line>::iterator it;
for (it = newlinevector.begin(); it != newlinevector.end(); it++)
{
cout << it->start << " " << it->end << " " << it->length << endl;
}
int count = 0;
int nowpoint = 0;
int* pre = new int[num];
for (int i = 0; i < num; i++)
{
pre[i] = i;
}
while (count < num - 1)
{
for (int i = 0; i < num; i++)
{
cout << pre[i] << " ";
}
cout << endl;
count++;
while (true)
{
line p = newlinevector[nowpoint];
int x = p.start;
int y = p.end;
if (Samefather(x, y,pre))
{
nowpoint++;
continue;
}
else
{
int max = x > y ? x : y;
for (int i = 0; i < num; i++)
{
if (pre[i] == pre[max])
{
pre[i] = pre[x];
}
}
cout << map.name[x] << " -> " << map.name[y] << endl;
nowpoint++;
break;
}
}
}
}
int main()
{
MapInit map(6);
Prim_D(map);
cout << "------------------------------" << endl;
Dijkatre_D(map, 0);
cout << "------------------------------" << endl;
Floyd(map);
cout << "------------------------------" << endl;
Kruskal(map);
// Prim(map);
// Dijkatra(map, 0, 3);
}
//下面这个东西直接复制输入道控制台即可
/*
abcdef
-1 6 1 5 -1 -1
6 -1 5 -1 3 -1
1 5 -1 5 6 4
5 -1 5 -1 -1 2
-1 3 6 -1 -1 6
-1 -1 4 2 6 -1
*/
Prim算法 Kruskal算法 Dijkatre算法 Floyd算法
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
