Режа: Минимал нархли дарахтлар склети

Танланган тугунлар тўплами	(u,v) қирра	V/U танланмаган тугунлар тўплами
Изоҳ
	{ }		{A,B,C,D,E,F,G}	Бошланғич граф
	{D}	(D,A)=5 V (D,B) = 9 (D,E)= 15 (D,F) = 6	{A,B,C,E,F,G}	D тугундан бошлаймиз A, B, E и F лар D билан боқланган. A тугун — D га энг яқин бўлганлиги учун шу тугун олинади.
	{A,D}	(D,B) = 9 (D,E)= 15 (D,F) = 6  (A,B) = 7 V	{B,C,E,F,G}	D ёки A га энг яқин бўлган тугунни топамиз. B - D 9, A —D 7. E гача масофа 15, F —гача 6. F энг яқин тугун.
	{A,B,D,F}	(B,C) = 8 (B,E)=7 V  (D,B) = 9 цикл (D,E)= 15 (F,E) = 8 (F,G)= 11	{C,E,G}
	{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 цикл (D,E) = 15 цикл (E,C) = 5 V (E,G) = 9 (F,E) = 8 цикл (F,G) = 11	{C,G}
	{A,B,C,D,E,F}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (E,G) = 9 V (F,E) = 8 цикл (F,G) = 11	{G}
	{A,B,C,D,E,F,G}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (F,E) = 8 цикл (F,G) = 11 цикл	{ }	Минимал нархли дарахтлар склети қурилди. Бунда оғирлиги 39 бўлди.

Қуйида Прим алгоритми келтирилган.
1-дастур. Прим алгоритми
procedure Prim ( G: граф; var T: қирралар тўплами );
var
U: қирралар тўплами;
u, v: қирра;
begin
T:= ø;
U:= {1};
while U ≠ V do begin
энг кам нархли ва uU ва vV\U бўлган (u, v) қиррани топиш;
Т:= Т{u, V));
U:= U{v}
end
end; { Prim }


Юқоридаги граф учун қўшнилик матрицаси
A B C D E F G
0 7 0 5 0 0 0
7 0 8 9 7 0 0
0 8 0 0 5 0 0
5 9 0 0 15 6 0
0 7 5 15 0 8 9
0 0 0 6 8 0 11
0 0 0 0 9 11 0


Дастур
#include
using namespace std;
int main()
{
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0}, min, mincost=0,cost[10][10];
int path[100]={0}; //ushbu massivda yulni tashkil qiladigan tugunlar yoziladi
int path_index=0;
cout<<"Tugunlar sonini kiriting "; cin>>n;
cout<<"Qushnilik matritsasini kiriting\n";
for(i=0;i for(j=0;j {
cin>>cost[i][j];
if(cost[i][j]==0)
cost[i][j]=999; // 999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе
}
visited[0]=1;
cout<<"\n";
while(ne < n)
{
for(i=0, min=999; i for(j=0;j if(cost[i][j]< min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
path[path_index]=b;
path_index++;
ne++;
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
cout<<"\n";
cout<<1<<" --> ";
for (int i=0;i {
cout<
if (i ";
}
cout<<"\n Minimal narx "<return 0;
}

Алгоритмни баҳолаш

,
Ёмон ҳолатда - .
Краскал алгоритми.
Ушбу алгоритм 1956 йили Краскал томонидан ишлаб чикилган.
Фараз қиламиз, V = {1, 2, .... n} бўғимлар тўпламидан иборат ва Е қирралар тўпламида аниқланган с нарх функцияси билан берилган G=(V, Е) боғланган граф бўлсин. Крускал алгоритмида G граф учун минимал нархли дарахтлар склетини қуриш G графнинг фақат n та бўғимларидан ташкил топган ва қирралари бўлмаган Т=(V, ø) графдан бошланади. Шундай қилиб, ҳар бир бўғим боғланган (ўзи-ўзи билан) компонент ҳисобланади. Алгоритм бажарилиши вақтида боғланган компонентлар наборига эга бўламиз, аста-секин бирлаштириб дарахтлар склетини ташкиллаштирамиз.
Аста-секин ўсувчи боғланган компонентларни қуришда Е тўпламдан қирралар уларнинг нархи ўсиши тартибида навбатма-навбат текширилади. Агар навбатдаги қирра турли компонентлардаги иккита бўғимни бирлаштирса, у ҳолда бу қирра Т графга қўшилади. Агар бу қирра битта компонентнинг иккита бўғимини бирлаштирса, у ташлаб юборилади, чунки унинг боғланган компонентга қўшилиши цикл ҳосил бўлишига олиб келади. G графнинг барча бўғимлари битта компонентга тегишли бўлса, Т минимал нархли дарахтлар склетини қуриш бу граф учун тугайди.
Мисол

С боғланган компонентлар тўплами керак, бу учун қуйидаги операторлар ишлатилади:

1. MERGE(A, В, С) оператори С набордан А ва В боғланган компонентларни бирлаштиради ва натижани А ёки В га жойлаштиради.
2. FIND(v, С) функцияси С набордан v бўғимни ўз ичига олган компонентнинг номини қайтаради.
3. INITIAL(A, v, С) оператори наборда фақат v бўғимдан иборат А номли компонентни яратади.
Ушбу алгоритм O (M log N + N²) вақтда бажарилади. Қирраларни саралаш учун О(M logN) та операция керак булади. Тугун у ёки бу қисм дарахтга тегишли бўлса, tree_id массив ёрдамида сақланади, бу массивда ҳар бир тугун учун у тегишли бўлган дарахт номери сақланади. Ҳар бир қирра учун О(1) вақтда унинг тугунлари турли дарахтларга тегишли эканлигини аниқланади. Ниҳоят, иккита дарахтни бирлаштириш O (N) вақтда бажарилади. Бирлаштириш оператори O(N) ўтишда бажарилишини ҳисобга олсак, O (M log N + N²) келиб чикади.
Дастур кўриниши қуйидагича булади:
int n, m;
cin >> n >> m;
vector > edges(m, vector(3));
for (int i = 0; i < m; ++i)
cin >> edges[i][1] >> edges[i][2] >> edges[i][0];
sort(edges.begin(), edges.end());
vector comp(n);
for (int i = 0; i < n; ++i)
comp[i] = i;
int ans = 0;
for (auto & edge: edges)
{
int weight = edge[0];
int start = edge[1];
int end = edge[2];
if (comp[start] != comp[end])
{
ans += weight;
int a = comp[start];
int b = comp[end];
for (int i = 0; i < n; ++i)
if (comp[i] == b)
comp[i] = a;
}
}

// Dijkstra algoritmi.
#include
using namespace std;
// Graf uchlari soni
#define V 9

int shortest_path(int dist[], int n)

{
cout<<"Uchlar "<<"\t"<<"Masofa\n";
for (int i = 0; i < V; i++)
cout<<" \t\t \n"<< i<<" \t\t "<}
// minimal masofani hisoblash
int minDist(int dist[], bool Set[])
{
int min = INT_MAX, min_index;
for (int i = 0; i < V; i++)
if (Set[i] == false && dist[i] <= min)
min = dist[i], min_index = i;
return min_index;
}
// Boshqa uchlargacha eng qisqa yo'llarni aniqlash
void Dijkstra(int g[V][V], int src)
{
int dist[V];
bool Set[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, Set[i] = false;
dist[src] = 0;
for (int c = 0; c < V- 1; c++)
{
int u = minDist(dist, Set);
Set[u] = true;
for (int j = 0; j < V; j++)
if (!Set[j] && g[u][j] && dist[u] != INT_MAX && dist[u]+ g[u][j] < dist[j])
{
dist[j] = dist[u] + g[u][j];
}
}
shortest_path(dist, V);
}
// asosiy funksiya
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int G[V][V] = {
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }};
Dijkstra(G, 0);
return 0;
}