Lekciya 13. Saytlardı shetlep ótiw algoritmları Joba: Tolıq graftı shetlep ótiw algoritmi

out token to pre
end
end

Hár bir sayt procesi bir retten artıq bolmaǵan hár bir kanal arqalı markerdi tapsırlıǵi sebepli, hár bir process bir retten artıq bolmaǵan hár bir kanal arqalı markerdi aladı. Hár sapar marker ol iniciatori tárepinen qolǵa kiritilgen bolsa, ol procesi onı jiberganidan bir ret kóbirek markerdi alǵan. Sonnan kelip shıǵadıki, ol menen júz bergen kanallar sanı olkáraınan keminde 1 tárepinen isletiletuǵın kanallar sanınan asıp ketedi. Sonday etip, ol processni juwmaqlamaydi, bálki markerdi uzatadı. Sonlıqtan, processtiń juwmaqlanıwı initiator saytında ámelge asıriladı.

Tómende algoritm tawsılǵannan keyin, hár bir process markerdi tapsırlıǵin kórsetedi.
(1) barcha kanallar, intsident iniciator, hár eki jóneliste de bir ret ótti. Markerdi iniciator barlıq kanallar arqalı jo'natdi, keri jaǵdayda algoritm tugamadi. Iniciator onı jiberganidek, markerdi bir neshe ret aldı ; iniciator hár sapar basqa kanal arqalı markerdi alǵanlıǵı sebepli, marker hár bir kanal arqalı bir waqtıniń ózinde jiberilgen.
(2) (2) hár bir kelilgen ol procesi ushın barlıq kanallar, hádiyse ol hár bir jóneliste bir ret ótti. Bul nadurıs dep esaplasak, ol birinshi ret uchrashmagan processni tańlaymiz hám ol (1) elementinen iniciator emesligin aytymiz. Ol tańlawınan baslap, barlıq kanallar, Pre (ol) hádiyseleri hár eki jóneliste de bir ret ótti, bul erda ol markerdi aldınǵısına jo'natdi. Sonday etip, ol markerdi qayta jiberiw ushın barlıq hádiyseler kanalların isletgen; biraq, aqırında marker iniciator bolıp qalǵanlıǵı sebepli, ol markerdi hár bir waqıya kanalı arqalı bir ret markerdi alǵan. Biz qarama-qarsılıqlarǵa keldik.
(3) (3) barlıq processler kelildi hám hár bir kanal hár eki jóneliste de bir ret ótti. Eger nadurıs processler ámeldegi bolsa, ol jaǵdayda ol hám s qońsılasları bar, ol kelgen hám s emes edi. Bul barlıq ol kanalları hár eki jóneliste de ótiwine qarsı keledi. Sonlıqtan, element (2), barlıq processler keldi hám barlıq kanallar hár eki jóneliste de bir ret ótti.
(4) Tarri algoritmınıń hár bir esap -kitapı tiykarǵı terekin anıqlaydı. Terektiń túbirinde iniciator bar hám esap -kitap aqırında hár bir iniciator ol ózgermeytuǵın Pre de terekke ózinden aldınǵısın alıp keldi.