Grafer

I den här texten introducerar vi de vanligaste begreppen inom grafteori samt presenterar två datastrukturer för att representera grafer och visar några grundläggande algoritmer som söker igenom en graf på ett systematiskt sätt.

Ta också gärna en titt på github.com/yourbasic/graph. Det är ett Go-bibliotek med generella implementationer av många grundläggande grafalgoritmer, flera med tillhörande exempel.

Grundbegrepp

En graf (graph) G består av två typer av element: hörn (vertices) och kanter (edges). Varje kant har två ändpunkter (endpoints) som båda ligger i mängden av hörn och som förbinder (connects or joins) de två ändpunkterna.

Hörnmängden (vertex set) för G skrivs ofta som V(G) eller bara V om det inte finns risk för missförstånd.

En kant mellan punkerna x och y skrivs som {xy}. Kantmängden (edge set) för G skrivs ofta som E(G) eller bara E om det inte finns risk för missförstånd.

Figuren visar en enkel graf med hörnmängd V = {1, 2, 3, 4, 5, 6} och kantmängd E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}.

6n-graf

En loop är en kant vars ändpunkter är samma hörn. En kant är multipel om det finns en annan kant med samma ändpunkter; annars är den enkel. En graf är enkel om den inte har några loopar eller några multipla kanter och en multigraf om den har multipla kanter.

Gradtalet för ett hörn v är antalet kanter som har v som ändpunkt.

En väg i en graf G = (V, E) är en följd av hörn v1, v2, ..., vk, med egenskapen att det finns kanter mellan vi och vi+1. Vi säger att vägen går från v1 till vk. Talföljden 6, 4, 5, 1, 2 är till exempel en väg från 6 till 2 i grafen ovan. En väg är enkel om alla ingående hörn är olika.

En cykel är en väg v1, v2, ..., vk för vilken k > 2, de första k - 1 hörnen är olika och v1 = vk. Talföljden 4, 5, 2, 3, 4 är ett exempel på en cykel i grafen ovan.

En graf är sammanhängande om det för varje par av hörn u och v finns en väg från u till v.

Om det finns en väg mellan hörn u och v så är avståndet mellan hörnen det minimala antalet kanter på vägen från u till v.

En sammanhängande komponent (connected component) är en subgraf av maximal storlek i vilken varje par av hörn är förbundna med varandra av en väg. Figuren visar en graf med tre sammanhängande komponenter

forest

Träd

Ett träd är en sammanhängande enkel acyklisk graf. Ett hörn av gradtal 1 kallas ett löv.

Riktade grafer

En riktad graf (directed graph) eller digraf (digraph) G = (V, E) består av en hörnmängd V och en kantmängd av ordnade par E av element i hörnmängden.

Figuren visar en enkel acyklisk digraf (ibland kallad DAG, "directed acyclic graph") med åtta hörn och nio kanter.

6n-graf

Närhetsmatriser

En närhetsmatris är en enkel datastruktur för att representera en graf G = (V, E). Grafen representeras som en |V|x|V|-matris av heltal. Hörnen numreras från 1 till |V| och position (ij) i matrisen innehåller en etta om det finns en kant mellan i och j, annars en nolla. Här är en graf med tillhörande närhetsmatris.

graph2 graph2-matrix

Närhetslistor

Närhetslistor är en alternativ datastruktur, med delvis annorlunda prestanda, för grafer. Datastrukturen består av en vektor av storlek |V|. Position k i vektorn består av en lista som innehåller alla grannar till k.

Djupetförstsökning

Djupetförstsökning DFS(gv) är en algoritm som besöker alla hörn i grafen g som ligger i samma komponent som hörnet v.

// Input: graph g and vertex v.
Mark all vertices of g as not visited.
DFS(g, v)
    if v is visited
        return        
    Mark v as visited.
    // Here you may perform some operation on v.
    for all neighbors x of v
        DFS(g, x)

Breddenförstsökning

Breddenförstsökning BFS(gv) är en algoritm som också besöker alla hörn i grafen g som ligger i samma komponent som hörnet v. Hörnen besöks i avståndsordning: först besöks hörnet v, sedan alla grannar till v, sedan deras grannar, etc.

// Input: graph g and vertex v.
BFS(g, v)
    Q = new empty queue
    Mark v as visited.
    Q.enqueue(v) // Add v to end of queue
    while Q is not empty
        a = Q.dequeue() // Remove a from top of queue.
        // Here you may perform some operation on a.
        for all unvisited neighbors x of a
            Mark x as visited.
            Q.enqueue(x)

Dijkstras algoritm

Dijkstras algoritm Dijkstra(gsource) är en algoritm som beräknar den kortaste vägen från hörnet source till alla andra hörn i en graf med icke-negativa kantavstånd. Algoritmen returnerar två vektorer:

// Input: graph g and vertex source.
Dijkstra(g, source)
    for each vertex v in g
        dist[v] = infinity
        prev[v] = undefined
    dist[source] = 0

    Q = the set of all nodes in g
    while Q is not empty
        u = vertex in Q with smallest distance in dist[]
        Remove u from Q.
        if dist[u] = infinity
            break
        for each neighbor v of u
            alt = dist[u] + dist_between(u, v)
            if alt < dist[v]
                dist[v] = alt
                prev[v] = u

    return dist[], prev[]

Stefan Nilsson