Grafas (duomenų struktūra)

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

RealizacijaKeisti

Kaimynystės matricaKeisti

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šaiKeisti

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ėjimasKeisti

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.