Graf (datastruktur)

En graf är inom datavetenskapen en abstrakt datastruktur. Generellt kan sägas att grafer består av en uppsättning hörn och en samling kanter. Men det förekommer en rad andra namn:

• hörn (eng. vertex, kan även kallas nod eller punkt)
• kant (eng. edge, kan även kallas båge)

Olika typer

De viktigaste typerna av grafmodeller är följande:

• Oriktade grafer (där anslutningarna är enkla).
• riktade grafer (där en kants riktning spelar roll)
• kantvägda grafer (där varje kant har en associerad vikt)
• kantvägda riktade grafer (där varje kant har både en riktning och en vikt) ^[1]

Kortaste vägar

Ett vanligt förekommande problem är att beräkna kortaste vägar från ett hörn till ett annat hörn. ^[2] Det första hörnet kallas i sammanhanget ofta för s (eng. start) och det senare kallas t (eng. target). Vilket angreppssätt som ska användas för att beräkna den kortaste vägen mellan två hörn för de olika graftyperna anges nedan:

• I en oviktad graf kan man säga att kostnaden motsvaras av antalet kanter. En lämplig metod att använda är bredd-först-sökning. Tidskomplexiteten blir då i värsta fall O(V+E) (alltså i värsta fall detsamma som antalet hörn plus kanter).
• I en viktad graf utan cykler (så kallad directed acyclic graph) kan man använda topologisk sortering med relax metoder till hjälp. Tidskomplexiteten blir då O(V+E).
• I en viktad graf med cykler kan Dijkstras algoritm användas. Tidskomplexitet O(E log V).
• I en viktad graf med cykler och negativa vikter: Bellman-Fords algoritm. Tidskomplexitet O(E*V).

Operationer

De grundläggande operationerna på en graf är följande:

• adjacent(G, x, y): testar huruvida det finns en graf från hörn x till hörn y;
• neighbors(G, x): listar alla hörn y där det finns en kant från hörn x till hörn y;
• add_vertex(G, x): lägger till hörn x, om det inte redan existerar;
• remove_vertex(G, x): tar bort hörn x. om det redan existerar;
• add_edge(G, x, y, z): lägger till kant z från hörn x till hörn y;
• remove_edge(G, x, y): tar bort kanten från x till y, om den existerar;
• get_vertex_value(G, x): returnerar värdet associerat med hörn x;
• set_vertex_value(G, x, v): sätter värdet på hörn x till v.

Referenser