Graaf

Definitsioon

Graaf (ingl. k. graph) on andmestruktuur, mis on oma olemuselt ning esituselt sarnane graafiteoorias uuritavale matemaatilisele objektile graaf.

Graaf on objekt, millel on minimaalselt:

mittetühi hulk tippe (ingl. k. vertex või node)
hulk servasid (ingl. k. edge), mis on 2-ennikud graafis olevatest tippudest

Ülevaatlikult võib öelda, et graaf on üks üldisemaid struktuure, mis võimaldab väljendada elemetide hulka ning nendevaheliseid suhteid.

Näiteks:

Autoteesid, ning kuidas need omavahel on ühendatud
Inimesi, ning nende sõprussuhteid (nt. sotsiaalvõrgustikus)
Faile, ning nende asukohta failisüsteemi kaustades
Programmi loogilist struktuuri abstraktse süntaksipuu näol

Graafi definitsiooni sageli täiendatakse, et olla spetsiifilistes kontekstides kasulikum. Mõni sellistest täiendustest on väga levinud ning hästi tuntud (vt. servade suunatus, tipude väärtustamine).

Näide

Siin on tekstiline esitus graafile DOT keeles:

graph G {
    v1 -- v2;
    v2 -- v3;
    v3 -- v4;
}

Ülaltoodud tekstist saab välja lugeda definitsioonile vastava graafi:

Tippude hulk: {v1, v2, v3, v4}
Servade (tippude 2-ennikute) hulk: {(v1, v2), (v2, v3), (v2, v4)}

Ning visuaalselt võib seda selliselt kujutada:

Servade suunatus

Eelnevalt eeldasime, et servades sisalduvate tippude järjekord on ebaoluline - sellises kontekstis on graafid **suunamata graafid.

Kui ütleme, et servades sisalduvate tippude järjekord on oluline, siis vaatleme suunatud graafe.

Võimalikud kasutusjuhud:

Jälgib suhted sotsiaalvõrgustikus (kasutaja A jälgib kasutajat B, aga mitte vastupidi)
Autoteede puhul ühe- või kahesuunalisuse tähistamiseks

Näide

digraph G {
    v1 -> v2;
    v2 -> v3;
    v3 -> v2;
}

Erinevalt eelmisest suunamata graafi näitest, ei ole siin võimalik "liikuda" tipust v2 tippu v1.

Servade väärtustamine

Servade väärtustamise puhul omistame igale servale mingi (tüüpiliselt skalaarse) väärtuse.

Need väärtused võivad kujutada:

Teede pikkust
Teede läbimisaega
Autoteede "mugavust" (laius, teekate)

Servade väärtustamine võimaldab lahendada probleeme nagu "leia lühim tee ühest punktist teise teede võrgustikus".

Näide

digraph Eesti {
    Tallinn -> Tartu [weight=179; label=179]
    Tartu -> Tallinn [weight=179; label=179]
    Tartu -> Pärnu [weight=176; label=176]
    Pärnu -> Tartu [weight=176; label=176]
    Tallinn -> Pärnu [weight=127; label=127]
    Pärnu -> Tallinn [weight=127; label=127]
}

Esitamine mälus

Graafi võib mälus esitada mitmeti. Vaatleme kõige lihtsamat varianti, kus:

Graaf on hulk tippe
Igal tipul on hulk naabreid

Javas võib seda esitada niiviisi:

public class Vertex {
    private final List<Vertex> neighbours;

    public Vertex() {
        this.neighbours = new ArrayList<>();
    }

    public Vertex(List<Vertex> neighbours) {
        this.neighbours = neighbours;
    }

    public List<Vertex> getNeighbours() {
        return neighbours;
    }
}

public class Graph {
    private final List<Vertex> vertices;

    public Graph() {
        this.vertices = new ArrayList<>();
    }

    public Graph(List<Vertex> vertices) {
        this.vertices = vertices;
    }

    public void add(Vertex vertex) {
        this.vertices.add(vertex);
    }

    public List<Vertex> getVertices() {
        return vertices;
    }
}

Warning

Kui on vajadus programmis graafidega ümber käia, on tõenäoliselt mõistlikum kasutada mõnda selleks mõeldud teeki, milles on juba graafid ning otsingualgoritmid tõhusalt implementeeritud.

Ning kasutamine võib välja näha selline:

var graph = new Graph();
var v1 = new Vertex();
var v2 = new Vertex(List.of(v1));
var v3 = new Vertex(List.of(v2));

digraph G {
    v2 -> v1
    v3 -> v2
}

Eeltoodud esitused on samaväärsed.