Grafas (duomenų struktūra)
-
Kitos reikšmės – grafas.
Grafas informatikoje tai duomenų struktūra, matematinio grafo realizacija.
Turinys |
Realizacija [taisyti]
Kaimynystės matrica [taisyti]
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.
Kaimynystės sąrašai [taisyti]
Kiekvienai Grafo viršūnei susikuriama po tiesinį sąrašą. Juose saugomos kiekvienos viršūnės kaimynės (viršūnės su kuriomis ši viršūnė yra susieta briauna).
Jei grafas nėra pilnas, taupant vietą, efektyviau jį realizuoti Kaimynystės sąrašais.
Grafo apėjimas [taisyti]
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) | |
| BFS | O (n) |
.png){kind=small} |
Šis straipsnis apie programavimą yra nebaigtas. Jūs galite prisidėti prie Vikipedijos papildydamas šį straipsnį. |
