Introduksjon til grafer

Når vi ønsker på løse et problem er et av de viktigste spørsmålene en kan stille seg hvilken informasjon som er relevant for å løse nettopp dette problemet. Ved å fjerne informasjon man ikke trenger er det ofte lettere å komme til kjernen, den informasjonen som er relevant. I denne posten skal vi se nærmere på en modell som er veldig utbredt, nemlig grafer. En graf består av en mendge noder og en mengde kanter. Nodene blir ofte visualisert som prikker og kantene som streker mellom nodene.

Rendered by QuickLaTeX.com

Grafer kan brukes til å representere alt fra veinett til vennskap. Kanskje har du på et tidspunkt fått tegnet vennskapsgrafen din på et sosialt media? Da vil nodene representere personer og kantene vennskap mellom disse. I noen tilfeller ønsker vi å legge mer informasjon på grafen enn bare hvem som er koblet sammen, for eksempel vil en kant som representerer en vei mellom to kryss være mer interessant for en GPS om den også oppgir lengden på veien, fartsgrenser osv. Og hva med enveiskjørte gater? Dette ordner vi med rettede kanter, kanter som har en startende og en sluttende. I denne posten vil vi dog konsentrere oss om urettede og uvektede grafer; Altså de av typen på figuren ovenfor. Dersom to noder har en kant mellom seg sier vi at de er naboer.

Representasjon på datamaskiner

De to mest brukte representasjonene av en graf på en datamaskin er kalt nabomatrise og naboliste. En nabomatrise er en tabell der hvert element forteller om et spesifikt par med noder har en kant mellom seg eller ikke, mens en naboliste lister alle naboene til hver node i grafen. De har begge sine fordeler og ulemper.

Nabomatrise

Om grafen har n noder vil en nabomatriserepresentasjon være en tabell av størrelse n*n der elementet i rad 0 og kolonne 2 forteller om det er en kant mellom node 0 og node 2 i grafen. Om vi tar en ny titt på eksempelgrafen vår, men gir hver node et nummer kan vi prøve å lage tabellen.

Rendered by QuickLaTeX.com

Nabomatrisen for denne grafen er under. Vi har brukt T (True) for å merke at en kant eksisterer og F (False) for at den ikke er der. Sjekk selv at bare dersom node i og j har en kant mellom seg, så er posisjon i, j (og j, i) T i tabellen.

-  0  1  2  3  4  5
0  F  T  T  T  T  T
1  T  F  T  F  T  T
2  T  T  F  T  T  T
3  T  F  T  F  T  F
4  T  T  T  T  F  F
5  T  T  T  F  F  F

Lese grafen og lagre den i en nabomatrise

Dersom input er en graf er den ofte gitt på følgende format:

n m (to heltall hvor n er antall noder i grafen og m er antall kanter)
m linjer på formen i j (som betyr at det er en kant mellom i og j)

Å lese denne typen input og lagre den i en nabomatrise kan gjøres på følgende måte:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector< vector<bool> > graph(n, vector<bool>(n, false));
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = true;
        graph[b][a] = true;
    }

    // Do your stuff

    return 0;
}

Fordeler og ulemper

Fordelen med en nabomatrise er at du på konstant tid (ta en titt på O-notasjon om dette var et ukjent begrep) kan sjekke om to noder er naboer eller ikke. Ufordelen kommer frem om man for eksempel ønsker å liste alle naboene til en node i en graf med “få” kanter. Tenk deg at en node bare har 2 naboer, man må forsatt sjekke hele raden for å finne alle naboene, som tar O(n) tid.

Naboliste

En naboliste er rett og slett en liste over alle nodene, hvor hvert element igjen er en liste med alle naboene til denne noden. På denne måten kan man enkelt iterere over alle naboene til en spesifikk node. Eksempelgrafen vår ville blitt representert på følgende måte:

0: 1, 2, 3, 4, 5
1: 0, 2, 4, 5
2: 0, 1, 3, 4, 5
3: 0, 2, 4
4: 0, 1, 2, 3
5: 0, 1, 2

Lese grafen og lagre den i en naboliste

Gitt input på samme form som for nabomatrisen kan dette gjøres på følgende måte:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector< vector<int> > graph(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // Do your stuff

    return 0;
}

Fordeler og ulemper

Når vi ønsker å se på alle d naboene til en node kan vi gjøre dette i O(d) tid i stedet for O(n). Dette vil spille en stor rolle angående kjøretid når vi skal se på bredde-først-søk og dybde-først-søk. Ufordelen er at vi også bruker O(d) tid på å sjekke om to noder er naboer.

Nå har du lært litt om hvordan man kan lagre en graf på en datamaskin. I de neste postene skal vi ta for oss bredde-først-søk og dybde-først-søk, to algoritmer som du kan anvende på grafer for forskjellige formål.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>