Grafas (duomenų struktūra)

Grafas informatikoje tai duomenų struktūra, matematinio grafo realizacija.

 Realizacija 

 Kaimynystės matrica 
Matricos elementas i-ojoje eilutėje ir j-ajame stulpelyje įgauna reikšmę (pavyzdžiui, 0 arba 1) priklausomai nuo to ar i-oji ir j-oji grafo viršūnės susietos briauna. Neorientuoto grafo kaimynystės matrica visda yra simetriška.

Tokia matrica paprasčiausiai realizuojama dvimačiu masyvu.

 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 kuriomis ši viršūnė yra susieta briauna).

Retiems grafams realizacija kaimynystės sąrašais naudoja mažiau vietos nei realizacija kaimynystės matrica. Tačiau pastaroji duomenų struktūra leidžia efektyviau atsakyti į klausimą "ar i-oji ir j-oji grafo viršūnės sujungtos?".

 Grafo apėjimas 
Egzistuoja du apibendrinti apėjimo algoritmai: į gylį (DFS – Depth First Search) ir į plotį (BFS – Breadth First Search). Abu algoritmai efektyvūs - jų sudėtingumas tiesinis.

Kategorija:Duomenų struktūros