Grafas (duomenų struktūra)

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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

Realizacija[taisyti | redaguoti kodą]

Kaimynystės matrica[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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.