Grafas (duomenų struktūra)
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Grafas informatikoje tai duomenų struktūra, matematinio grafo realizacija.
Turinys |
[taisyti] Realizacija
[taisyti] Kaimynystės matrica
Grafo viršūnės įrašomi kaip stulpelių ir eilučių pavadinimai, o matricos elementai įgauna teigiamą ar klaidingą reikšmę priklausomai nuo to ar viršūnės (eilutės ir stulpelio pavadinimuose) susietos briauna. Pagal susitarimą tariama jog pati su savimi viršūnė briaunos neturi, todėl tokios lentelės diagonalė užpildyta klaidingomis reikšmėmis. Reikia pastebėti, jog neorientuoto grafo kaimynystės matrica yra simetriška.
Tokia matrica paprasčiausiai realizuojama dvimačiu masyvu.
[taisyti] Kaimynystės sąrašai
Kiekvienai Grafo viršūnei susikuriama po tiesinį sąrašą. Juose saugomos kiekvienos viršūnės kaimynės (viršūnės su kuriuomis ši viršūnė yra susieta briauna).
Jei grafas nėra pilnas, taupant vietą, efektyviau jį realizuoti Kaimynystės sąrašais.
[taisyti] Grafo apėjimas
Egzistuoja du apibendrinti apėjimo algoritmai: į gylį (DFS – Depth First Search) ir į plotį (BFS – Breadth First Search).
Pavadinimas | Atmintis (sudėtingumai) | Laikas (sudėtingumai) | Komentarai |
---|---|---|---|
DFS | O (n) | O (nc ) | |
BDS | O (n) |