14. Grafen

Een graaf bestaat uit knopen (in het Engels: vertices, enkelvoud vertex) en kanten (edges). De kanten vormen verbindingen tussen de knopen. Een netwerk van wegen tussen steden kun je zien als een graaf. De steden zijn dan de knopen, de wegen zijn de kanten.

Bovenstaande graaf bestaat uit 5 knopen, hier genummerd van 0 tot en met 5. De verzameling knopen is dus {0, 1, 2, 3, 4}. De graaf bevat 7 kanten, {01, 04, 12, 13, 14, 23, 34}. De kant 01 is hierin de kant die de knopen 0 en 1 verbindt. Tussen knoop 0 en 2 is geen directe verbinding: de verzameling kanten bevat dus geen kant met label 02. Deze graaf is ongericht (undirected). Dat betekent dat als er een verbinding is tussen knoop 0 en 4, er automatisch ook een verbinding is tussen knoop 4 en 0. In het voorbeeld van het wegennetwerk tussen steden kun je dit interpreteren als: over alle wegen tussen de steden is verkeer in twee richtingen mogelijk. Ook is deze graaf ongewogen (unweighted) omdat elke edge een gelijk gewicht heeft. In het voorbeeld zou je dit, een beetje gekunsteld, kunnen zien alsof de wegen geen lengte hebben.

Er zijn verschillende manieren om een graaf op te slaan. Hieronder staan de "adjacency list" en "adjacency matrix" uitgelegd.

Adjacency List

De adjacency list is de meest standaard manier om grafen op te slaan. Het is een array of lists. Elke list slaat de buren van een knoop op.

De adjacency list van bovenstaande graaf is:

Adj[0] (1) (4) Adj[1] (0) (2) (3) (3) Adj[2] (1) (3) Adj[3] (1) (2) (4) Adj[4] (0) (1) (3)

De c++ code voor een adjacency list is:

vector<int> adj[MAXN];
int main(){ 
cin >> n; // Het aantal knopen 
cin >> m; // Het aantal kanten 
for(int i = 0; i < m; i++){ 
    int a, b; 
    cin >> a >> b; 
    adj[a].push_back(b); 
    adj[b].push_back(a);
    } 
return 0; 
}

Adjacency matrix

Een andere manier om de graaf op te slaan is met een adjacency matrix van size V x V. Een adjacency matrix is een 2D array met op positie (i,j) een 1 als de graaf een kant bevat die knoop i met knoop je verbindt, en een 0 als er niet zo'n kant is.

De adjacency matrix van bovenstaande graaf is:

Zie je dat de adjacency matrix symmetrisch is?

De c++ code voor een adjacency matrix is:

int adj[MAXN][MAXN]; 
 
int main(){
  cin >> n; // Het aantal knopen 
  cin >> m; // Het aantal kanten 
  for(int i = 0; i < m; i++){ 
    int a, b;
    cin >> a >> b;
    adj[a][b] = 1; 
    adj[b][a] = 1; 
  }
  return 0;
}

Gerichte graaf

Bij een gerichte graaf hebben de kanten een richting. In bovenstaande graaf is er in de ongerichte graaf een kant van knoop 0 naar 1 en ook van knoop 1 naar 0. In de gerichte graaf is er alleen maar een kant van knoop 0 naar 1.

Opdrachten adjacency list/matrix

1. Schrijf een programma dat een adjacency list kan opslaan. Voeg de volgende 2 functies toe: - void addEdge(int i, int j): addEdge voegt een kant die knoop i met knoop j verbindt toe aan de graaf - boolean isEdge(int i, int j): isEdge bepaalt of er een kant is die knoop i met knoop j verbindt. In een ongerichte graaf moet je elke edge twee keer toevoegen: bijvoorbeeld als je de functie addEdge(0,2) aanroept dan moet je ook addEgde(2,0) aanroepen. Als je een graaf hebt opgeslagen, geef dan als output het aantal edges/kanten dat de opgeslagen graaf heeft.

2. In deze opdracht kijken we naar de graad van een knoop. De graad van een knoop is het aantal knopen waarmee de knoop verbonden is. Bijvoorbeeld: de graad van knoop 0 in bovenstaande graaf is 2. Schrijf een programma dat de som van de graad van alle knopen bepaalt van bovenstaande graaf.

Breadth first search

Stel dat we in het voorbeeld aan het begin van dit hoofdstuk alle knopen willen bezoeken die, startend vanuit knoop 0, bereikbaar zijn via 1 of meer kanten. We bekijken twee manieren om dit te doen: eerst de zogenaamde breadth first search, daarna depth first search.

Breadth first search is een manier om een graaf te doorzoeken, waarbij je eerst alle knopen bezoekt die direct met het startpunt verbonden zijn, dan de knopen die in twee stappen bereikbaar zijn, etcetera.

Je houdt bij welke knopen al bezocht zijn in een array Bezocht. Ook is er een zogeheten queue om bij te houden welke knopen we gaan bezoeken. Een queue is een speciaal soort array. Een queue werkt volgens het FIFO (first in, first out) principe, waarbij geldt dat het element dat het eerst werd toegevoegd het eerst wordt verwijderd. Een rij in de supermarkt werkt volgens het FIFO principe. De klant die als eerste in de rij is gaan staan, wordt als eerste geholpen.

De stappen voor breadth first search zijn:

1. Voeg de knoop waar je wil beginnen toe aan de queue.

2. Verwijder de eerste knoop uit de queue, markeer deze als bezocht.

3. Als deze knoop buren heeft, voeg dan alle buren die nog niet bezocht zijn toe aan het einde van de queue.

4. Herhaal stap 2 en 3 tot de queue leeg is. Alle knopen die vanuit het startpunt bereikbaar zijn, zijn nu bezocht.

Hieronder de code voor een queue in C++. De queue voegt elementen aan het eind van de array toe en verwijdert elementen aan het begin van de array.

#include <iostream>
using namespace std;
#include <queue>
 
int main()
{
  queue<int> q;
  q.push(1); //voegt element 1 toe
  q.push(10); //voegt element 10 toe
  q.push(2); //voegt element 2 toe
  q.pop(); //verwijdert element 1
  return 0;
}

Opdrachten Breadth First Search:

1. Schrijf een programma dat als invoer een graaf krijgt en als uitvoer geeft in welke volgorde de knopen in de graaf bezocht worden met een breadth first search. Invoer: Op de eerste regel van de uitvoer staat het aantal knopen v en aantal kanten e dat de graaf heeft. Op de volgende e regels staan de kanten gedefinieerd. De graaf is ongericht en ongewogen. Uitvoer: Een regel met daarop de volgorde waarin de knopen bezocht worden met een breadth first search. Het beginpunt is altijd vertex 0. Als er knoop meerdere buren heeft, bezoek de buren dan in numerieke volgorde, de knoop met het laagste nummer eerst. Voorbeeld: Invoer: 5 7 0 1 0 4 1 2 1 3 1 4 2 3 3 4 Uitvoer: 0 1 4 2 3

2. Gegeven een doolhof, schrijf een programma dat bepaalt of er een pad is van Begin (B) naar Eind(E) met behulp van Breadth First Search. Muren worden met X aangegeven, gangen met 0. Voorbeeld invoer: 6 7 -> 6 is het aantal kolommen en 7 is het aantal rijen XXXB0X X0XX0X X0000X XXXX0X E00X0X XX000X XXXXXX De uitvoer is ja als er een pad is van Begin naar Eind en nee als er geen pad is.

Depth first search

Depth first search (DFS) is ook een methode om een graaf te doorlopen. Depth first search werkt recursief met backtracken. Bij breadth first search doorloop je de graaf level bij level. Je begint bij de knopen die het dichtst bij het beginpunt liggen en gaat daarna naar de knopen die een stap verder liggen. Bij depth first search zoek je gelijk een pad van begin tot eind, daarna backtrack je op zoek naar een pad waar je nog niet geweest bent. Ook bij depth first search is het belangrijk dat je bij houdt welke knopen al bezocht zijn, om te voorkomen dat je in een eindeloze lus terechtkomt.

De pseusocode voor depth first search is:

void DFS(int k){
   markeer de knoop k als bezocht
   
   voor alle buren b van knoop k
      als de buur b nog niet is bezocht   
         DFS (b) 
}

int main()
{
    DFS(0);
    return 0;
}

Voorbeeld:

Opdrachten Depth First Search

1. Maak de 2 opgaves in de sectie breadth first search nu met depth first search. Wat zijn de voor- en nadelen van DFS en BFS voor het doolhof probleem?

2. Een bipartiete graaf is een graaf waar je de knopen in twee kleuren kunt kleuren, zo dat er geen verbinding is tussen 2 knopen met dezelfde kleur. Schrijf een programma dat bepaalt of een graaf bipartiet is. Met de volgende link kan je testen of je programma werkt: bipartiet

3. Maak de opgave kleuren.

Hieronder nog een mooi plaatje met hoe een boom doorlopen wordt voor BFS en DFS:

Gewogen graaf

Bij een gewogen graaf hebben de kanten een gewicht. In het eerdere voorbeeld van een netwerk van wegen tussen steden kun je aan de lengtes van de wegen denken als hun gewicht. Een gewogen graaf kan zowel gericht als ongericht zijn.

In de adjacency list van een gewogen graaf sla je niet alleen de labels van de knopen waar een gegeven knoop mee is verbonden op, maar ook het gewicht van de kant die de knopen verbindt. De adjacency list van bovenstaande gewogen graaf is:

Adj[0] (1, 5) Adj[1] (2,1) Adj[2] (0,3) (3,5) Adj[3] (1,2)

In een adjacency matrix sla je bij een gewogen graaf op positie (i,j) het gewicht op van de kant die knoop i met knoop j verbindt.

Opdrachten grafen

1. Schrijf een programma dat het kortste pad berekent tussen 2 knopen in een gewogen graaf. Voor dit programma kun je het Dijkstra algoritme gebruiken. Zoek zelf op hoe dit algoritme werkt.

2. Maak de opdracht netwerk.