-
Grafu algoritmu klasifikācija, algoritmu piemēri
| Nr. | Sadaļas nosaukums | Lpp. |
| ANOTĀCIJA | 2 | |
| SATURS | 3 | |
| IEVADS | 4 | |
| 1. | NEVĒRSTIE GRAFI | 5 |
| 1.1. | Nevērsta grafa attēlojums | 5 |
| 1.2. | Nevērsta grafa “depth-first” meklēšana | 6 |
| 2. | VĒRSTIE GRAFI | 8 |
| 2.1. | Vērsta grafa attēlojums | 8 |
| 2.2. | Vērsto grafu topoloģiskā šķirošana | 9 |
| 2.3. | “Breadth-first” meklēšana | 9 |
| 3. | MINIMĀLI APTVEROŠS KOKS (MINIMUM SPANNING TREE) | 11 |
| SECINĀJUMI | 13 | |
| LITERATŪRAS SARAKSTS | 14 |
SECINĀJUMI
Grafs ir komplicēta nelineāra datu struktūra, kas pēc struktūras ir līdzīga kokam. Tie var tikt implementēti līdzīgi vektoram vai arī sarakstam. Grafs satur divus galvenos elementus: virsotnes un šķautnes, kas veido visu grafa saturu. Visas grafa virsotnes parasti tiek glabātas masīvos. Grafi no citiem datu struktūras veidiem atšķiras ar to, ka katrai no grafa virsotnēm ir saistība vai savienojamība ar citām virsotnēm, izņemot, ja grafā pastāv minimāli aptverošs koks, kuram kāda no šķautnēm tika noņemta.
Jebkuram grafam arī ir iespējams uzrakstīt programmu / algoritmu konkrētu virsotņu meklēšanai, kuru vispārējus piemērus es ietvēru šī referāta saturā. Ir divu veidu meklēšanas metodes: meklēšana dziļumā jeb “depth-first” search un meklēšana plašumā jeb “breadth-first” search. Abi nosauktie meklēšanas veidi parasti tiek izmantoti tieši nevērstajiem grafiem, bet var tikt implementēti arī vērstajos grafos.
Vērstu grafu unikalitāte izpaužas topoloģiskajā šķirošanā. Lai veiktu topoloģisko šķirošanu vērstam grafam, virsotnes ir jāsaliek tādā secīgā rindā, ka visas vērstās šķautnes norāda no virsotnes, kas secībā ir agrāk, uz virsotni, kas secībā ir vēlāk ( vai arī ir iespējams ziņot, ka šo darbību nav iespējams izdarīt ). …
Referāta galvenais mērķis ir izpētīt grafu algoritmu klasifikāciju, kā arī sniegt dažādus piemērus. Darbā arī tiks ietverta grafa vispārējā definīcija, vairāki attēli, kas raksturo un atspoguļo attiecīgo grafa algoritmu, algoritmu kodu daļas un arī sarakstu attēlojumi. Darba rezultātā tika izpētīti trīs grafu algoritmu veidi: nevērstie grafi, vērstie grafi un minimāli aptveroši koki ( Minimum Spanning Tree ).
