Задача Прима - Крускала
Дана плоская сторона и в ней N городов. Эти города можно соединить телефонной связью так, чтобы общая длина телефонных линий была минимальной. в терминах теории графов это звучит так: Дан граф G<v,E> с N вершинами, длина ребер известна, Найти остковное дерево минимальной длины. Алгоритм Прима-Крускала относятся к жадным алгоритмам, и имеет таки шаги:
1) все вершины красим в разные света, например: соответственно номеру вершиную.
2) ищем минимальное ребро с вершинами на концах разного света.
3) все вершины связанные с вершинами последнего выбранного ребра красим в один свет.
4) повторяем пункты 2, 3, N-1 раз.
Алгоритмы Прима-Крускала отличаются тем, что в алгоритме Прима используется матрица смежности, а в алгоритме Крускала используется список ребер.
Алгоритм Прима:
#include <iostream>
#include<limits.h>
using namespace std;
const int MAXN=100;
int A[MAXN][MAXN], x[MAXN], y[MAXN], color[MAXN];
int n, m, S;
void Init()
{
int i,j,k,d;
cin>>n>>m;
for(k=1;k<=m;k++)
{
cin>>i>>j>>d;
A[i][j]=d; A[i][j]=d;
}
}
void Prima()
{
int i,j,k,z,col1,col2,mind,im,jm;
for(i=1;i<=n;i++) color[i]=i;
z=0;
for(k=1;k<n;k++)
{
mind=INT_MAX;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(A[i][j]!=0 && color[i]!=color[j] && mind>A[i][j])
{
mind=A[i][j]; im=i; jm=j;
}
z++; x[z]=im; y[z]=jm; S=S+mind;
col1=color[im]; col2=color[jm];
for(i=1;i<=n;i++)
if(color[i]=col1) color[i]=col2;
}
}
void obr()
{
int i;
cout<<S<<endl;
for(i=1;i<n;i++) cout<<x[i]<<' '<<y[i]<<end;
}
void main()
{
Init();
void Prima();
obr();
}
Алгоритм Крускала отличается от алгоритма Примы тем, что для поиска минимального ребра используется список ребер. Прежде чем начать поиск все ребера сортируются по длине ребра, которая требует O(n log2n):
|
|
|
const int MAXN=1000;
int x[MAXN], y[MAXN], x0[MAXN], y0[MAXN], d[MAXN], color[MAXN];
int n,m,S;
void Init()
{
int i,j,k;
cin>>n>>m;
for(k=1;k<=m;k++)
cin>>x[k]>>y[k]>>d[k];
}
void swap(int &a, int&b)
{
int t;
r=a; a=b; b=r;
}
void qsort(int left, int right)
{
int key,i,j;
if(l>r) return;
key=d[(left+right)/2]; i=left; j=right;
do
{
while(d[i]<key) i++;
while(key<d[j]) j--;
if(i<=j)
{
swap(d[i], d[j]); swap (x[i], x[j]); swap(y[i], y[j]); i++; j--;
}
}while(i<=j);
qsort(left,j); qsort(i,right);
}
void Kruskal()
{
int i,j,k,col1,col2;
for(i=1;i<=n;i++) color[i]=i;
qsort(1,n); j=0;
for(k=1;i<n;k++)
{
for(i=k;i<=m;i++)
{
if(color[x[i]]!=color[y[i]])
{
j++; x0[j]=x[i]; y0[j]=y[i]; S=S+d[i]; break;
}
}
col1=color[x[i]]; col2=color[y[i]];
for(i=1;i<n;i++)
if(color[i]= =col1) color[i]=col2;
}
}
void main()
{
Init(); Kruskal(); obr();//x=x0,y=y0
}
Можно использовать сортировку из стандартной библиотеки. Для этого необходимо использовать следующие переменные
typedef struct tedge{int x,y,d;}
tedge edge[MAXN];
int compare(const void*p1, const void*p2)
{
tedge x1=*((tedge*)p1);
tedge x2=*((tedge*)p2);
return x1.d-x2.d;
}
qsort(edge, m+1, sizeof(edge[0]), compare);
30.09.2015
Дата добавления: 2016-01-06; просмотров: 40; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!