|
#include<iostream>
using namespace std;
#define maxsize
typedef int vertype;
typedef struct node
{
int data;
int rank;
int parent;
}UFSTree;
typedef struct Edge
{
int begin;
int end;
int w;
bool operator<(const Edge &e)const
{
return w < e.w;
}
}Edge;
void MAKE_SET(UFSTree t[], int n)
{
for (int i = 0; i < n; i++)
{
t[i].rank = 0;
t[i].parent = 0;
}
}
int FIND_SET(UFSTree t[], int x)
{
if (x != t[x].parent)
return (FIND_SET(t, t[x].parent));
else
return (x);
}
void UNION(UFSTree t[], int x, int y)
{
x = FIND_SET(t, x);
y = FIND_SET(t, y);
if (t[x].rank > t[y].rank)
t[y].parent = x;
else
{
t[x].parent = y;
if (t[x].rank = t[y].rank)
t[y].rank++;
}
}
void Kruskal(MGraph g)
{
int i, j, k, u1, u2, sn1, sn2;
UFSTree t[maxsize];
Edge E[maxsize];
k = 0;
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
{
if (g.edge[i][j] != 0 && g.g.edge[i][j] != 0)
{
E[k].begin = i; E[k].end = j; E[k].w = g.edge[i][j];
k++;
}
}
sort(E, E + k);
MAKE_SET(t, g.n);
k = 1; j = 0;
while (k < g.n)
{
u1 = E[j].begin;
u2 = E[j].end;
sn1 = FIND_SET(t, u1);
sn2 = FIND_SET(t, u2);
if (sn1 != sn2)
{
cout << "u1=" << u1 << " u2" << u2 << "E[j].w" << E[j].w << endl;
k++;
UNION(t, u1, u2);
}
j++;
}
}
图片中显示的问题,该如何解决?
|
-
上一篇: const修饰指针下一篇: 自己定义的MyStrcpy不能实现字符串复制的原因?
|