Algoritmu teorija "Grafu algoritmi – dziļummeklēšana un plašummeklēšana, bināro koku apiešana"

Attieksmju grafu plašā pielietošana praktiski visās zinātnēs un inženierpielietojumos ir radījusi nepieciešamību sistematizēt un attīstīt to algoritmu teorijas daļu, kas apkalpo grafu teorijas uzdevumus. Šajā nodaļā mēs īsi apskatīsim plašāk pielietotos grafu uzdevumus un algoritmus to risināšanai.

Bieži risinot teorētiskus vai praktiskus uzdevumus, ir nepieciešams apiet (pārmeklēt, pārlasīt, iezīmēt) grafa virsotnes noteiktā, algoritmiskā kārtībā, izmantojot grafa šķautnes. Ir skaidrs, ka algoritms ir vajadzīgs, lai apiešanu varētu realizēt ar datora palīdzību. Šāda algoritma efektivitātes dēļ ir lietderīgi minimizēt katras virsotnes iezīmēšanas reižu skaitu, piemēram, pieprasīt, ka katra virsotne tiek iezīmēta ne vairāk kā vienu reizi. Kāda varētu būt grafu virsotņu apiešanas dabiska kārtība? Šo uzdevumu var viegli atrisināt, ja grafs ir, piemēram, ķēde vai cikls, tad ir skaidrs, kā tas ir jāapiet:

Ko darīt patvaļīga sakarīga grafa gadījumā? Ir vismaz divi dabiski grafu apiešanas veidi – plašummeklēšana un dziļummeklēšana. Abos algoritmos tiek pakāpeniski konstruēts orientēts koks, kuram atbilstošais neorientētais koks ir dotā grafa skelets.

Plašuma meklēšana (pārlase plašumā, breadth first search): sākam ar fiksētu virsotni , atzīmējam visas ar to saistītās virsotnes , pilnīgi sakārtojam tās veidā , konstruējam sakārtotu koku :

Nākošajā solī konstruējam sakārtotu koku šādā veidā: apejam pilnīgi sakārtoto virkni tās pieaugošajā kārtībā un katrai virsotnei atzīmējam un piekārtojam kā dēlu kopu visas virsotnes , kas ir saistītas ar un vēl nav atzīmētas:

Turpinām šo procesu konstruējot sakārtotu koku virkni , kuras pēdējais loceklis tiek saukts par plašuma meklēšanas koku. Atzīmēsim, ka šis koks nav noteikts viennozīmīgi, tas ir atkarīgs no tā pirmās virsotnes un no katras iekšējās virsotnes dēlu sakārtojumu.

Novērtēsim operāciju skaitu, kas ir nepieciešams plašuma meklēšanai. Pieņemsim, ka ir dots grafs ar V virsotnēm un E šķautnēm, kas ir uzdots ar saistības sarakstu. Plašuma meklēšanas procesā katra virsotne tiek ievietota kokā vienu reizi, tātad summārais operāciju skaits ir . Katras virsotnes saistības saraksts tiek apskatīts vienu reizi, tātad summārais operāciju skaits šajā algoritma daļā ir . Papildus operāciju skaits grafa inicializācijai ir . Var redzēt, ka kopējais algoritma darba laiks ir .

a) noteikt, vai grafs ir saistīts un atrast grafa komponenšu skaitu to var izdarīt, veicot meklēšanu plašumā no jebkuras virsotnes, grafs ir saistīts tad un tikai tad, ja tiek apietas visas grafa virsotnes, komponenšu skaits ir vienāds ar nepieciešamo meklēšanu skaitu, kas ir nepieciešamas, lai apietu visas virsotnes,