Grafas (duomenų struktūra)
![]() |
Šiam straipsniui ar jo daliai trūksta išnašų į š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.
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.