Introduksjon til søking i grafer

I denne posten vil vi ta for oss noen grunnleggende algoritmer for å søke i grafer. Vi begynner med å introdusere noen problemer for å motivere algoritmene, deretter vil vi dekke to datastrukturer kalt queue og stack, før vi ser nærmere på bredde-først søk og dybde-først søk.

Penger på tur

En vennegjeng har vært på interrail; Og som man ofte gjør på tur for enkelhetens skyld har de lagt ut for hverandre i forbindelse med diverse felles utgifter. Nå er de kommet hjem igjen og tiden er inne for å gjøre opp. Problemet er at det ikke bare er fryd og gammen å være på tur, så en del vennskap har gått dunken grunnet trange togkupèer og løse mager. De som er blitt uvenner nekter å snakke med hverandre, og det er enda mindre tenkelig at de vil utveksle penger seg i mellom. Gitt hvor mye penger hver enkelt har lagt ut og hvilke personer som forsatt er venner er din oppgave å finne ut om det er mulig å gjøre opp for turen slik at alle har betalt like mye.

Epler og pærer

Som nyansatt barnehagearbeider tok du med deg en pose epler og en pose pærer første dag på jobb i håp om å oppnå litt godvilje. Til din forferdelse når du ankommer jobb oppdager du at det er en skålvekt midt på uteplassen. Alle voksne vet jo at ingen epler eller pærer veier like mye, dette gjør desverre ikke barn. Du ser allerede for deg bråket som oppstår når to venner som har fått samme frukt sammenligner dem på vekten og innser at den ene har fått mer enn den andre. På den andre siden er også barn klar over at epler og pærer ikke kan sammenlignes, så dette kommer ikke til å bli et problem. Du haster bort til nærmeste barnehageansatt og ber om en raskt introduksjon angående hvem som er venner i barnehagen. Gitt alle vennskapene blant barna er din oppgave å gi en utdeling av epler og pærer slik at dersom to barn er venner så får de forskjellig type frukt eller si at en slik fordeling ikke eksisterer. Du kan anta at du har tilstrekkelig med epler og pærer til å realisere en hver løsning.

Utrykningstid

Brannsjefen i byen er bekymret for utrykningstiden deres på tross av at brannstasjonen er plassert midt i sentrum. Grunnen er at de i det siste har fått mange falske alarmer om brann. Han vil derfor at du skal vurdere følgende senario: de får en alarm og rykker ut til denne, den viser seg å være falsk, men på veien har de mottatt en ny alarm. Hvor mange kryss må brannbilen maksimalt kjøre gjennom før han kommer frem til neste potensielle brann? Grunnen til at kryssene er interessant er at på veiene slipper bilene stort sett frem brannbilen, mens det i kryssene fort kan bli kaos. Gitt en oversikt over alle kryssene i byen og hvordan de er koblet sammen er din oppgave å returnere hvor mange kryss brannbilen må gjennom i verste tilfellet fra den ene utrykningen til den neste.

Queue

I C++ er det en datastruktur som heter queue (kø). Denne fungerer nettopp slik en kø bør, først inn resulterer i først ut også. La oss ta en titt på et eksempel.

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    queue<int> numbers;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        numbers.push(x);
    }
    
    while(!numbers.empty()) {
        int x = numbers.front();
        numbers.pop();
        cout << x << endl;
    }

    return 0;
}

Her ser du de fire viktigste tingene du bør kunne om en kø:
- Hvordan du lager en kø,
- hvordan du legger til elementer i en kø (push),
- hvordan du henter det neste elementet i en kø (front) og
- hvordan du fjerner det fremste elementet i køen (pop).

Om du hadde gitt denne koden inputen:

4
1 2 3 4

Hadde output vært følgende:

1
2
3
4

Stack

Om du derimot hadde valgt å bruke en stack som køsystem ville du endt opp med verdens mest urettferdige kø. Den vil nemlig hele tiden gi ut den som sist ble puttet på stacken.

#include<iostream>
#include<stack>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    stack<int> numbers;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        numbers.push(x);
    }
    
    while(!numbers.empty()) {
        int x = numbers.front();
        numbers.pop();
        cout << x << endl;
    }

    return 0;
}

Eneste forandringen er at vi nå bruker en stack i stedet for queue. Om vi hadde gitt programmet samme input nå, ville output blitt

4
3
2
1

Bredde-først søk

Et bredde-først søk er et søk som starter i en node og undersøker grafen på følgende måte: Først undersøker den noden selv, deretter alle nodene som har avstand 1 til start, deretter alle som har avstand 2 osv.

Under et søk deler vi nodene i grafen inn i uoppdaget, oppdaget og utforsket (henholdsvis hvit, grå og svart på figuren over). Når vi utforsker en node vil alle dens naboer som er uoppdaget bli oppdaget. Hvordan vi velger neste node vi skal utforske avgjøres av typen søk, og for bfs (bredde-først søk) er det den noden som er ble oppdaget først av de ikke-utforskede nodene. En kø er perfekt for denne oppgaven. Ved å alltid utforske noden fremst i køen og ved å legge uoppdagede naboer inn i køen når vi utforsker en node vil vi oppnå akkurat denne lagvise oppførselen som et bfs skal ha. Under finner du en oversikt over hvordan oppdaget-listen og køen ville sett ut under animasjonen over, det kan være en god øvelse å verifisere dette.

     Oppdaget                Kø
(a)                       (a)
(a, b, c)                 (b, c)
(a, b, c, d, e)           (c, d, e)
(a, b, c, d, e, f, g)     (d, e, f, g)
(a, b, c, d, e, f, g)     (e, f, g)
(a, b, c, d, e, f, g, h)  (f, g, h)
(a, b, c, d, e, f, g, h)  (g, h)
(a, b, c, d, e, f, g, h)  (h)
(a, b, c, d, e, f, g, h)  ()

Både bfs og dfs (dybde-først søk, som vi skal se på i neste avsnitt) kan løse mange forskjellige problemer på grafer. De kan blant annet sjekke om det finnes en sti mellom to noder, finne sammenhengende komponenter, sjekke om nodene i en graf kan fargelegges slik at for hver kant har de to endepunktene ulik farge, finne sykler osv. Men en av de egenskapene som gjør bfs veldig anvendelig er at den undersøker nodene i grafen ut i fra distansen fra start, noe som gjør at et bfs ikke bare finner en vilkårlig sti mellom to noder, men en korteste sti. Under ser du et program som tar en graf, start og slutt som input og verifiserer om det finnes en sti mellom disse eller ikke.

#include<iostream>
#include<vector>
#include<queue>

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);
    }

    int start, stop;
    cin >> start >> stop;
    
    vector<bool> visited(n, false);
    queue<int> next;

    next.push(start);
    visited[start] = true;

    while(!next.empty()) {
        int pos = next.front();
        next.pop();
        
        for(int i = 0; i < graph[pos].size(); ++i) {
            int nghbr = graph[pos][i];
            if(!visited[nghbr]) {
                next.push(nghbr);
                visited[nghbr] = true;
            }
        }
    }

    if(visited[end])
        cout << "Det er en sti mellom " << start <<
            " og " << stop << endl;
    else
        cout << "Det er ikke en sti mellom " << start <<
            " og " << stop << endl;

    return 0;
}

Dybde-først søk

Vi også kjapt nevne dybde-først søk. I denne posten vil vi ikke utforske de egenskapene et dfs har som et bfs ikke har, annet at det grunnet sin rekursive natur kan ha en litt penere implementasjon. Den virkelige kraften til dfs vil vi komme innom på et senere tidspunkt i en ny post. Forskjellen fra bfs er at et dfs utforsker den noden den oppdaget sist først i stedet for den noden den oppdaget først. Dette gjør at ved kun å bytte fra queue til stack vil bfs implementasjonen vår bli en dfs implementasjon. Det finnes dog en vanligere (og kanskje lettere om du er komfortabel med rekursjon) måte å implementere et dfs på, nemlig ved hjelp av rekursjon.

#include<iostream>
#include<vector>

using namespace std;

void dfs(int pos, vector<bool>& visited, const vector< vector<int> >& graph)
{
    if(visited[pos])
        return;
    visited[pos] = true;
    
    for(int i = 0; i < graph[pos].size(); ++i)
        dfs(graph[pos][i], visited, graph);
}

int main()
{
    // les inn grafen
    
    vector<bool> visited(n, false);
    dfs(start, visited, graph);
    
    // visited[stop] er nå true hvis og bare hvis
    // det eksisterer en sti fra start til stop
}

Kjøretid

Både bfs og dfs har kjøretid lineær i antall noder og kanter, nemlig O(n+m). Vi kan derfor anvende algoritmene på grafer med en million noder på under et sekund om vi har en datamaskin fra dette årtusenet. Det som ofte er mest tidkrevende er å lese grafen, dette gjør at man ofte holder seg til grafer rundt 100 000 noder og kanter når det kommer til konkurranser.

Vi retter nå oppmerksomheten vår mot problemene vi introduserte i begynnelsen og hvordan vi kan bruke bfs og dfs til å løse dem. Prøv deg gjerne selv før du forsetter.

Penger på tur

Observer at dersom grafen er sammenhengende (det finnes en sti mellom alle par av personer) så er svaret alltid ja. Dersom grafen ikke er sammenhengende, la oss se på en sammenhengende komponent i grafen. Ettersom det ikke er mulig å flytte penger mellom denne komponenten og resten av grafen er man avhengig av at komponenten kan gjøre opp internt for at svaret skal være ja. Og når kan en komponent gjøre opp internt, jo når gjennomsnittsforbruket i denne komponenten er likt gjennomsnittsforbruket i hele grafen. Vi må derfor sjekke at hver komponent kan gjøre opp internt og dersom dette er tilfelle er svaret ja. Input er på følgende form:

n (antall personer)
<n heltall hvor det ite tallet sier hvor mye person i la ut på turen>
m (antall vennskap)
<m linjer med par av tall som beskriver vennskapene>

Under finner du et løsningsforslag til problemet. Merk at vi bruker dfs til å finne både størrelsen (size) og summen av alle pengene som ble brukt (u) i komponenten, og dermed kan vi finne gjennomsnittsforbruket i komponenten (u/size). Om vi lar tot være det totale forbruket og n antall personer så er gjennomsnittsforbruket for hele turen tot/n, og dermed er det bare å teste at for komponent er u/size == tot/n. Merk at dette kan føre til skumle flyttallsfeil (moral: unngå alltid flyttall om du kan) og derfor tester vi heller for u*n == tot*size (manipulasjon ved hjelp av enkel algebra).

#include<iostream>
#include<vector>

using namespace std;

int used(int pos, int& size, vector<bool>& visited,
    const vector<int>& money, const vector< vector<int> >& graph)
{
    if(visited[pos])
        return 0;
    
    visted[pos] = true;
    ++size;

    int ret = money[pos];
    for(int i = 0; i < graph[pos].size(); ++i)
        ret += used(graph[pos][i], size, visited, money, graph);

    return ret;
}

int main()
{
    int n;
    cin >> n;
    
    vector<int> money(n);
    for(int i = 0; i < n; ++i)
        cin >> money[i];

    int m;
    cin >> 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);
    }
    
    int tot = 0;
    for(int i = 0; i < n; ++i)
        tot += money[i];

    vector<bool> visited(n, false);
    bool valid = true;
    for(int pos = 0; pos < n; ++pos) {
        if(visited[pos])
            continue;

        int size = 0;
        int u = used(pos, size, visited, money, graph); 

        if(u*n != tot*size)
            valid = false;
    }

    if(valid)
        cout << "Oppgjørets time er kommet" << endl;
    else
        cout << "Pengene er tapt" << endl;

    return 0;
}

Epler og pærer

Om vi lar noder representere barna og kantene vennskapene dem i mellom, kan oppgaven beskrives som å plassere epler og pærer på nodene slik at for hver kant er det et eple på ene siden og en pære på andre siden. For å abstrahere ytterligere lar vi de nodene som får eple bli røde og de som får pære grønne. Spørsmålet er nå redusert til om vi kan fargelegge grafen med to farger (rød og grønn) slik at for hver kant så har de to endepunktene ulik farge. Dette er noe vi har sagt tidligere at både et bfs og et dfs kan løse. Observasjonen er som følger; La v være en node i grafen og anta at det finnes en gyldig fargelegging som bruker to farger. Da finnes det en gyldig fargelegging som farger v rød, for om v var grønn i den antatte løsningen kan vi bare fargelegge alle nodene motsatt, vi vil forsatt ha en gyldig fargelegging og v vil være rød. Ta derfor en vilkårlig node og farg den rød, nå må alle dens naboer farges grønne, deres naboer må være røde igjen osv. Om du forsetter denne prosessen vil du til slutt ende opp enten med en gyldig fargelegging eller en node som skulle vært fargelagt både rød og grønn og da er svaret nei. Slik kan dette implementeres ved hjelp av et bfs:

#include<iostream>
#include<vector>
#include<queue>

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);
    }

    // -1 betyr ufarget, 0 betyr rød og 1 grønn
    // På denne måten kan vi bruke color til å angi farger,
    // men også hvilke noder som er besøkt.
    vector<int> color(n, -1);
    
    // Denne løkken er nødvendig for å sørge for at hele grafen
    // blir fargelagt også om den ikke er sammenhengende
    boolean valid_coloring = true;
    for(int i = 0; i < n; ++i) {
        if(color[i] >= 0)
            continue;
        
        queue<int> next;
        next.push(i);
        color[i] = 0;
        
        while(!next.empty()) {
            int pos = next.front();
            next.pop();
            int next_color = (color[pos]+1)%2;
        
            for(int i = 0; i < graph[pos].size(); ++i) {
                int nghbr = graph[pos][i];
                if(color[nghbr] == color[pos]) {
                    valid_coloring = false;
                } else if(color[nghbr] == -1) {
                    color[nghbr] = next_color;
                    next.push(nghbr);
                }    
            }
        }    
    }
    
    if(!valid_coloring) {
        cout << "Fjern skålvekten! Det kommer til å bli krangling.." << endl;
    } else {
        for(int i = 0; i < n; ++i)
            cout << i << " får " <<
                (color[i] == 0 ? "eple" : "pære") << endl;
    }
    
    return 0;
}

Utrykningstid

I denne oppgaven var vi interessert i hvor langt det kunne være mellom to utrykningslokasjoner. Altså, om vi representerer kryssene med noder og veier mellom dem med kanter, hvor langt er det mellom de to nodene som ligger lengst fra hverandre i grafen. Dette er også kalt diameteren til grafen. Dette skal vi gjøre på følgende måte, vi implementerer et bfs som gitt en node finner ut hvor langt det er til nodene lengst unna også bruker vi dette søket på samtlige noder i grafen. Ettersom vi gjør dette for hver node er ikke kompleksiteten til algoritmen O(n+m) lenger, men O(n*(n+m)). En god tommelfingerregel er å putte inn grensen for verdiene i kompleksiteten og dele på noe mellom 10^7 og 10^8 ut i fra hvor “tunge” operasjoner du gjør for å finne ut hvor mange sekunder programmet ditt vil bruke. Så om n, m < 5000 gir dette oss 5000*(5000 + 5000) / 10**8 = 0.5 som er på oppunder hva som går.

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

int biggest_dist(int v, const vector< vector<int> >& graph)
{
    int INF = 2*graph.size(); // Større enn noen distanse
    vector<int> dist(n, INF);
    
    dist[v] = 0;
    queue<int> next;
    next.push(v);

    int bdist = 0;
    while(!next.empty()) {
        int pos = next.front();
        next.pop();
        bdist = dist[pos];
        
        for(int i = 0; i < graph[pos].size(); ++i) {
            int nghbr = graph[pos][i];
            if(dist[nghbr] > dist[pos]+1) {
                dist[nghbr] = dist[pos]+1;
                next.push(nghbr);
            }
        }
    }
    
    // Vi trekker fra en ettersom vi ønsker antall kryss
    // og ikke antall kanter (som man vanligvis måler distanse i)
    return max(0, bdist-1);
}

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);
    }
    
    int dist = 0;
    for(int i = 0; i < n; ++i)
        dist = max(dist, biggest_dist(i, graph));
    
    cout << dist << endl;

    return 0;
}

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>