Grafas (duomenų struktūra)

Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

Kitos reikšmės – grafas.

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.