Treceți la conținutul principal

kruskal cpp



program kruskal ;

uses crt;

const max =10;

var muchie : array [1..max,1...3] of integer

m.ni,cost : integer
arb1,arb2:integer
tata : array[1..max] of integer

function componenta (varf : integer): integer  {c}
begin
 while tata[varf] > 0 do varf = tata[varf]
 componenta=varf
end

procedure reunete(a,b : integer)    {g}
var suma : integer

begin
 suma = tata[a]+tata[b]
 if tata[a]<tata[b] then
  tata[a]=suma;
  tata[b]=a
 else begin
  tata[b] = suma
  tata[a]=b end
end

begin

clrscr
write('n=');
readln(n)
write('m=');
readln(m);

writeln('dati muchiilke in ordine crescatare a costurilor');  {b}

for i = 1 to m do
 begin
  writeln('muchia nr. ,L)
  write ('u = ');
  readln(muchie[i],1);
  write('v=');
  readln(muchie[i,2]);
  write('cost = ');
  readln(muchie[i,e]);
 end

for i = 1 to n do tata[i]=-a;  {a}
 atta[i] = 0;

cost = 0 ;
for i = 1 to m do
 begin
  arb1 = componenta(muchie[i,1]);    {d}
  arb2 = componenta(muchie[i,2]);
   ifarb1<>arb2 then
    begin
     reuneste(arb1,arb2);  {f}
     cost=cost+muchie[1,3];
     writeln(muchie[i.1],'--',muchie[i,2]) {e}
  end
 end;

writeln('cost = ' ,cost); readln

end


 


algoritmul    
kruskal
 greedy

1.se alege muchia de cost min
2.de n-1 ori se adauga muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu


a.tata[] - root/varf arbore
b.tata[i] - nr de vf din arbore -> nr arbori a cate n noduri cu radcina tata[i]=-a {a}
c.gasime candidat muchie de ordinul i(u,v) in ordinea crescatoare a costurilor (b) 
 se verifica careui arbore (componenta c) apartin u si v

 dac arb 1 = arb 2 - ciclu in A
 daca arb2 != arb 1 - > putem adauga muchia E

d.reunirea arb1 U arb2 in F

cel mai mic arb. se v-a lega cu cel mai mare

e.root pt arb1 si arb2 if ar1>arb2










/////////////////////////////////////////////////////////////////////////////////////////////////////////////////




transpunerea in matematica


harta circuit excurie

colorare fv graf

inchidere tranzitiva a unei relatii binare





 

Comentarii

Postări populare de pe acest blog

WINDOWS 10 COMPUTER FREEZING PROBLEM SOLVED

good news : a BIOS UPDATE can resolve the problem but just for a Windows 7 on 64 bits o.s. and the system is not stable all the time. even after  bios update the system can freeze.
new info : u can try to low the screen brightness and see if this error appear so often after 
news: last info !!! maybe a virus. scann our system now with an antivirus i generate this error using other device ( a tablet pc) connected in the same network and the laptop i have this problem just freeze  http://thehackernews.com/2013/10/backdoor-found-in-chinese-tenda.html

news : if u use a tenda router this make couse all this problems



what i discover so far :
1.the electric company have many failure and affect the main ISP router/switch for building  also the router/switch installed by the ISP may be affected by overheating and will crash after a long utilisation on heat conditions 2.the router/switch of ISP affect any router of the user between this router and pc/laptop of client 3.the router and any other device of t…

program principal cpp

#include "clasa.h" #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <string.h> #define DELAY 9000000 void delay() { for(long i=0;i<DELAY;i++); } //constructor cu initializare de la tastatura BigInt::BigInt() {char x; signed char t[400]; int i; printf("\nNumarul cu semn "); do s=getche(); while((s!='+')&&(s!='-')); n=0; do {x=getche(); t[n]=x-'0'; n++; } while((x>='0')&&(x<='9')); n--; for(i=0;i<n;i++) nr[i]=t[n-i-1]; } //constructor cu initializare prin parametri BigInt::BigInt(char semn,signed char numar[],int dim) {int i; s=semn; n=dim; for(i=0;i<n;i++) nr[i]=numar[n-i-1]; } //transform un int negativ in pozitiv int BigInt::Pozitiv(int x) {int a,vb; a=0; vb=0; while(vb==0) if((x+a)==0) vb=1; else a=a+1; x=a; return x; } //constructor dintr-un nr int obisnuit BigInt::BigInt(int x) {int i; if(x>=0) s='+'…

o aplicatie php localitati romania

//APLICATIA SE REFERA LA BAZA DE DATE SIRUTA

//dragtable.js


/* dragtable v1.0 June 26, 2008 Dan Vanderkam, http://danvk.org/dragtable/ http://code.google.com/p/dragtable/ \Bsortabledraggable\B Instructions: - Download this file - Add <script src="dragtable.js"></script> to your HTML. - Add class="draggable" to any table you might like to reorder. - Drag the headers around to reorder them. This is code was based on: - Stuart Langridge's SortTable (kryogenix.org/code/browser/sorttable) - Mike Hall's draggable class (http://www.brainjar.com/dhtml/drag/) - A discussion of permuting table columns on comp.lang.javascript Licensed under the MIT license. */ // Here's the notice from Mike Hall's draggable script: //***************************************************************************** // Do not remove this notice. // // Copyright 2001 by Mike Hall. // See http…