# 15. 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.

<figure><img src="https://155810540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fag1wUPh8M2n58lYXKcOY%2Fuploads%2FaWBJFe81JdIGLhbdG8BR%2Fimage.png?alt=media&#x26;token=a94a2dff-2c2a-483c-8245-6698df408808" alt="" width="563"><figcaption></figcaption></figure>

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.&#x20;

Graafstructuren zijn heel handig voor het modelleren van relaties en interacties. Een wegennetwerk is de meest voor de hand liggende toepassing. Maar grafen kunnen voor heel veel toepassingen gebruikt worden. Bijvoorbeeld ook voor spellen om strategieën of oplossingsmethoden te ontwikkelen.

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) (4)\
Adj\[2] (1) (3)\
Adj\[3] (1) (2) (4)\
Adj\[4] (0) (1) (3)

De c++ code voor een adjacency list is:

```cpp
int main(){ 
    int n, m, a, b;
    cin >> n; // Het aantal knopen 
    cin >> m; // Het aantal kanten 
    vector<int> adj[n];
    for(int i = 0; i < m; i++){ 
        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:

<figure><img src="https://155810540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fag1wUPh8M2n58lYXKcOY%2Fuploads%2FL8uMkaLs9TXHR047n4aW%2Fimage.png?alt=media&#x26;token=6669a5c9-6634-4dbd-bbc6-655aba480aef" alt="" width="136"><figcaption></figcaption></figure>

De c++ code voor een adjacency matrix is:

```cpp
int main(){
  int n, m, a, b;
  cin >> n; // Het aantal knopen 
  cin >> m; // Het aantal kanten 
  int adj[n][n]; 
  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**\


<figure><img src="https://155810540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fag1wUPh8M2n58lYXKcOY%2Fuploads%2FVHQCGyVBXpimgDvtifhT%2Fimage.png?alt=media&#x26;token=56aec7a8-bbcb-4ab2-bb53-22e949228166" alt="" width="375"><figcaption></figcaption></figure>

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.&#x20;

**Opdracht 15.1**\
Maak de opdracht: [Adjacency list to matrix](https://informatica.cuttle.org/?action=question_standalone\&que_id=218\&t=91fedf3e40a0f6d2).

**Opdracht 15.2**\
Maak de opdracht: [Som van de knopen](https://informatica.cuttle.org/?action=question_standalone\&que_id=219\&t=57ec871228450633).

#### **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.&#x20;

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.

<figure><img src="https://155810540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fag1wUPh8M2n58lYXKcOY%2Fuploads%2Fd34yzSdH7c50vVLZhRHZ%2Fplaatje_BFS.gif?alt=media&#x26;token=c61f3a80-df42-4f70-a595-6f239eddc04b" alt="" width="440"><figcaption></figcaption></figure>

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.

```cpp
#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;
}
```

**Opdracht 15.3**\
Maak de opdracht: [graaf BFS](https://informatica.cuttle.org/?action=question_standalone\&que_id=220\&t=995b5bb4125eb3e4).

**Opdracht 15.4**\
Maak de opdracht: [doolhof](https://informatica.cuttle.org/?action=question_standalone\&que_id=222\&t=c8db3f6930383e87). Gebruik BFS.

#### **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:

```cpp
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:

<figure><img src="https://155810540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fag1wUPh8M2n58lYXKcOY%2Fuploads%2FOwoBu6yBcZRX0ytDTACc%2Fanimated_DFS.gif?alt=media&#x26;token=eb01ea34-d713-4509-994a-77257ea9b40d" alt="" width="563"><figcaption></figcaption></figure>



**Opdracht 15.5**\
Maak de opdracht: [Graaf DFS](https://informatica.cuttle.org/?action=question_standalone\&que_id=221\&t=3f05e68efd3c15df).

**Opdracht 15.6**\
Maak de opdracht: [doolhof](https://informatica.cuttle.org/?action=question_standalone\&que_id=222\&t=c8db3f6930383e87) nog een keer. Gebruik nu DFS.\
Wat zijn de voor- en nadelen van DFS en BFS voor dit doolhof probleem?

**Opdracht 15.7**\
Maak de opdrach&#x74;**:** [bipartiet](https://informatica.cuttle.org/?action=question_standalone\&que_id=223\&t=3a27aaffd023e4bf)

**Opdracht 15.8**\
Maak de opdracht [netwerk](https://informatica.cuttle.org/?action=question_standalone\&que_id=224\&t=a0c94f34d08b7b43).

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

<figure><img src="https://155810540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fag1wUPh8M2n58lYXKcOY%2Fuploads%2F6NyVhcovg3hpnPACmGgg%2Fimage.png?alt=media&#x26;token=7069da6b-c65d-4bc4-9292-3dc73fc503b4" alt="" width="499"><figcaption></figcaption></figure>

**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.&#x20;

<figure><img src="https://155810540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fag1wUPh8M2n58lYXKcOY%2Fuploads%2FvXiESeBprYAqQqOaETPh%2Fimage.png?alt=media&#x26;token=e07ae4d8-a0d3-427b-90a4-52fce5f45eed" alt="" width="375"><figcaption></figcaption></figure>

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. Maak de opdracht [kortste pad](https://informatica.cuttle.org/?action=question_standalone\&que_id=225\&t=a82c9e42d2254a84). Voor dit programma kun je het Dijkstra algoritme gebruiken. Zoek zelf op op internet hoe dit algoritme werkt. \
   Een goede uitleg staat op de pagina: [https://timjs.notion.site/3-3-Kortste-afstand-fb301df0130e413c8e1f71016248b050](https://timjs.notion.site/3-3-Kortste-afstand-fb301df0130e413c8e1f71016248b050)\

2. Maak de opdracht [netwerk](https://informatica.cuttle.org/?action=question_standalone\&que_id=85\&t=1db917878013bddf).&#x20;
