---
title: "Les B-arbres et graphes"
date: "2024-05-14"
---

# Les B-arbres (rappel)

## Définition: B-arbre d'ordre $n$

. . .

* Chaque page d'un arbre contient au plus $2\cdot n$ *clés*;
* Chaque page (excepté la racine) contient au moins $n$ clés;
* Chaque page qui contient $m$ clés contient soit:
    * $0$ descendants;
    * $m+1$ descendants.
* Toutes les pages terminales apparaissent au même niveau.

# Les B-arbres (rappel)

## Est-ce un B-arbre?

![B-arbre d'ordre 2.](figs/barbres_exemple.png)

. . .

### Bien sûr!

# Les B-arbres (rappel)

## L'algorithme d'insertion

. . .

0. Rechercher la feuille (la page a aucun enfant) où insérer;
1. Si la page n'est pas pleine insérer dans l'ordre croissant.
2. Si la page est pleine, on sépare la page en son milieu :
    1. On trouve la médiane, `M`, de la page;
    2. On met les éléments `< M` dans la page de gauche de `M` et les `> M` dans la page de droite de `M`;
    3. `M` est insérée récursivement dans la page parent.

# Les B-arbres (rappel)

## L'insertion cas nœud pas plein, insertion `4`?

![](figs/barbres_insert_easy.svg){width=50%}

. . .

## Solution

![](figs/barbres_insert_easy_after.svg){width=50%}

# Les B-arbres (rappel)

## L'insertion cas nœud pas plein, insertion `N`

* On décale les éléments plus grand que `N`;
* On insère `N` dans la place "vide";
* Si la page n'est pas pleine, on a terminé.

# Les B-arbres (rappel)

## L'insertion cas nœud plein, insertion `2`?

![](figs/barbres_insert_hard_before.svg){width=50%}

. . .

## Solution

![](figs/barbres_insert_hard_during.svg){width=50%}

# Les B-arbres (rappel)

## L'insertion cas nœud plein, promotion `3`?

![](figs/barbres_insert_hard_during.svg){width=50%}

. . .

## Solution

![](figs/barbres_insert_hard_after.svg)

# Les B-arbres (rappel)

## L'insertion cas nœud plein, insertion `N`

* On décale les éléments plus grand que `N`;
* On insère `N` dans la place "vide";
* Si la page est pleine:
    * On trouve la valeur médiane `M` de la page (quel indice?);
    * On crée une nouvelle page de droite;
    * On copie les valeur à droite de `M` dans la nouvelle page;
    * On promeut `M` dans la page du dessus;
    * On connecte le pointeur de gauche de `M` et de droite de `M` avec l'ancienne et la nouvelle page respectivement.

# Les B-arbres (rappel)

## Pseudo-code structure de données

. . .

```C
struct page
    entier ordre, nb
    element tab[2*ordre + 2]
```

```C
struct element
    entier clé
    page pg
```

# Les B-arbres (rappel)

\footnotesize

## Les fonctions utilitaires (5min matrix)

```C
booléen est_feuille(page)     // la page est elle une feuille?
entier position(page, valeur) // à quelle indice on insère?
booléen est_dans_page(page, valeur) // la valeur est dans la page
```

. . .

```C
booléen est_feuille(page) 
    retourne (page.tab[0].pg == vide)

entier position(page, valeur)
    i = 0
    tant que i < page.nb && valeur >= page.tab[i+1].clef
        i += 1
    retourne i

booléen est_dans_page(page, valeur)
    i = position(page, valeur)
    retourne (page.nb > 0 && page.tab[i].val == valeur)
```

# Les B-arbres (rappel)

\footnotesize

## Les fonctions utilitaires 

```C
page nouvelle_page(ordre)  // créer une page
```
. . .

```C
page nouvelle_page(ordre)
    page = allouer(page)
    page.ordre = ordre
    page.nb = 0
    page.tab = allouer(2*ordre+2)
    retourner page
```

# Les B-arbres (rappel)

## Recherche de page

```C
page recherche(page, valeur) // retourner la page contenant
                             // la valeur ou vide 
```

. . .

```C
page recherche(page, valeur)
    si est_dans_page(page, valeur)
        retourne page
    sinon si est_feuille(page) 
        retourne vide
    sinon
        recherche(page.tab[position(page, valeur) - 1], valeur)
```

# Les B-arbres (nouveautés)

## Les fonctions

```C
page inserer_valeur(page, valeur) // insérer une valeur
```

. . .

```C
page inserer_valeur(page, valeur)
    element = nouvel_element(valeur)
    // ici élément est modifié pour savoir 
    // s'il faut le remonter
    inserer_element(page, element) 
    si element.page != vide && page.nb > 2*page.ordre
        // si on atteint le sommet!
        page = ajouter_niveau(page, element) 
    retourne page
```

# Les B-arbres

## Les fonctions

```C
rien inserer_element(page, element) // insérer un element 
                                    // et voir s'il remonte
```

. . .

```C
rien inserer_element(page, element)
    si est_feuille(page)
        placer(page, element)
    sinon
        sous_page = page.tab[position(page, element.clé) - 1].page
        inserer_element(sous_page, element)
        // un element a été promu
        si element.page != vide
            placer(page, element)
```

# Les B-arbres

## Les fonctions (5min matrix)

```C
rien placer(page, element) // inserer un élément
```

. . .

```C
rien placer(page, element)
    pos = position(page, element.clé)
    pour i de 2*page.ordre à pos+1
        page.tab[i+1] = page.tab[i]
    page.tab[pos+1] = element
    page.nb += 1
    si page.nb > 2*page.ordre
        scinder(page, element)
```

# Les B-arbres

## Les fonctions (5min matrix)

```C
rien scinder(page, element) // casser une page et remonter
```

. . .

```C
rien scinder(page, element)
    nouvelle_page = nouvelle_page(page.ordre)
    nouvelle_page.nb = page.ordre
    pour i de 0 à ordre inclu
        nouvelle_page.tab[i] = page.tab[i+ordre+1]
    element.clé = page.tab[ordre+1].clé
    element.page = nouvelle_page
```

# Les B-arbres

## Les fonctions (5min matrix)

```C
page ajouter_niveau(page, element) // si on remonte à la 
                                   // racine, on doit créer
                                   // une nouvelle racine
```

. . .

```C
page ajouter_niveau(page, element) 
    tmp = nouvelle_page(page.ordre)
    tmp.tab[0].page = page
    tmp.tab[1].clé = element.clé
    tmp.tab[1].page = element.page
    retourne tmp
```





<!-- # Les B-arbres -->

<!-- ## Structure de données en C (3min, matrix) -->

<!-- . . . -->

<!-- ```C -->
<!-- typedef struct _page { -->
<!--     int order, nb; -->
<!--     struct _element *tab; -->
<!-- } page; -->
<!-- ``` -->

<!-- ```C -->
<!-- typedef struct element { -->
<!--     int key; -->
<!--     struct _page *pg; -->
<!-- } element; -->
<!-- ``` -->


# Les B-arbres: suppression

## Cas simplissime

![Suppression de 25.](figs/barbres_ordre2_supp1.svg){width=80%}

. . .

![25 supprimé, on décale juste 27.](figs/barbres_ordre2_supp2.svg){width=80%}

# Les B-arbres: suppression

\footnotesize

## Cas simple


![Suppression de 27.](figs/barbres_ordre2_supp2.svg){width=60%}

. . .

* On retire 27, mais....
    * Chaque page doit avoir au moins 2 éléments.
    * On doit déplacer des éléments dans une autre feuille! Mais comment?

. . .

![La médiane de la racine descend, fusion de 20 à gauche, et suppression à droite.](figs/barbres_ordre2_supp3.svg){width=60%}

# Les B-arbres: suppression

## Cas moins simple

![Suppression de 5.](figs/barbres_ordre2_supp4.svg){width=60%}

. . .

* Un élément à droite, comment on fait?
    * Remonter `7`, serait ok si racine, mais... c'est pas forcément.
    * On redistribue les feuilles.

. . .

![Descente de `3`, remontée médiane des feuilles `2`.](figs/barbres_ordre2_supp5.svg){width=60%}

# Les B-arbres: suppression

\footnotesize

## Cas ultra moins simple

![Suppression de 3.](figs/barbres_ordre2_supp6.svg){width=60%}

. . .

* `7` seul:
    * Fusionner les feuilles et redistribuer, comment?

. . .

![Descendre `-1`, déplacer `7` à gauche, et décaler les éléments de droite au milieu.](figs/barbres_ordre2_supp7.svg){width=60%}

# Les B-arbres: suppression

## Cas ultra moins simple

![On a pas fini...](figs/barbres_ordre2_supp7.svg){width=60%}

. . .

* `8` est seul, c'est plus un B-arbre :
    * Fusionner le niveau 2 et redistribuer, comment?

. . .

![Fusionner `8`, `17`, `22` et descendre `12`.](figs/barbres_ordre2_supp8.svg){width=40%}

. . .

* La profondeur a diminué de 1.

# Les B-arbres: suppression

## Algorithme pour les feuilles!

* Si la clé est supprimée d'une feuille:
    * Si on a toujours `n` (ordre de l'arbre) clés dans la feuille on décale simplement les clés.
    * Sinon on combine (récursivement) avec le nœud voisin et on descend la clé médiane.

# Les B-arbres: suppression

## Cas non-feuille!

![Suppression de 8.](figs/barbres_ordre2_supp9.svg){width=60%}

. . .

* On sait comment effacer une valeur d'une feuille, donc?

. . .

![Échanger le `8` avec le plus grand du sous-arbre de gauche.](figs/barbres_ordre2_supp10.svg){width=60%}

* Ensuite?

# Les B-arbres: suppression

## Cas non-feuille!

![Suppression de 8.](figs/barbres_ordre2_supp10.svg){width=60%}

. . .

* On sait comment effacer une valeur d'une feuille!

. . .

![Yaka enlever le 8 de la feuille comme avant!](figs/barbres_ordre2_supp11.svg){width=60%}

# Les B-arbres: suppression

## Algorithme pour les non-feuilles!

* Si la clé est supprimée d'une page qui n'est pas une feuille:
    * On échange la valeur avec la valeur de droite de la page de gauche
    * On supprime comme pour une feuille!

## Et maintenant des exercices par millions!

# Les graphes

\Huge

Les graphes

# Les graphes! Historique

**Un mini-peu d'histoire...**

## L. Euler et les 7 ponts de Koenigsberg:

* Existe-t-il une promenade sympa, passant **une seule fois** par les 7 ponts et revenant au point de départ?

![Les ponts c'est beau. Source: Wikipédia, <https://bit.ly/37h0yOG>](figs/Konigsberg_bridges.png){width=50%}

. . .

* Réponse: ben non!

# Utilisation quotidienne

## Réseau social

![Source, Wikipedia: <https://bit.ly/3kG6cgo>](figs/Social_Network.svg){width=40%}

* Chaque sommet est un individu.
* Chaque trait une relation d'amitié.
* Miam, Miam, Facebook.

# Utilisation quotidienne

## Moteurs de recherche

![Source, Wikipedia: <https://bit.ly/3kG6cgo>](figs/PageRanks-Example.svg){width=40%}

* Sommet est un site.
* Liens sortants;
* Liens entrants;
* Notion d'importance d'un site: combien de liens entrants, pondérés par l'importance du site.
* Miam, Miam, Google (PageRank).

# Introduction

## Définition, plus ou moins

* Un graphe est un ensemble de sommets, reliés par des lignes ou des flèches.

![Deux exemples de graphes.](figs/ex_graphes.png)

* Des sommets (numérotés 1 à 6);
* Connectés ou pas par des traits ou des flèches!

# Généralités

## Définitions

* Un **graphe** $G(V, E)$ est constitué
    * $V$: un ensemble de sommets;
    * $E$: un ensemble d'arêtes.
* Une **arête** relie une **paire** de sommets de $V$.

## Remarques

* Il y a **au plus** une arête $E$ par paire de sommets de $V$.
* La **complexité** d'un algorithme dans un graphe se mesure en terme de $|E|$ et $|V|$, le nombre d'éléments de $E$ et $V$ respectivement.

# Généralités

## Notations

* Une arête d'un graphe **non-orienté** est représentée par une paire **non-ordonnée** $(u,v)=(v,u)$, avec $u,v\in V$.
* Les arêtes ne sont pas orientées dans un graphe non-orienté (elles sont bi-directionnelles, peuvent être parcourues dans n'importe quel ordre).

## Exemple


::: columns

:::: column

![Un graphe non-orienté.](figs/ex_graphe_non_oriente.svg)


::::

:::: column

## Que valent $V$, $|V|$, $E$, et $|E|$?

. . .

\begin{align*}
V&=\{1, 2, 3, 4\},\\
|V|&=4,\\
E&=\{(1,2),(2,3),(2,4),(4,1)\},\\
|E|&=4.
\end{align*}

::::

:::

# Généralités

## Notations

* Une arête d'un graphe **orienté** est représentée par une paire **ordonnée** $(u,v)\neq(v,u)$, avec $u,v\in V$.
* Les arêtes sont orientées dans un graphe orienté (étonnant non?).

## Exemple


::: columns

:::: column

![Un graphe orienté.](figs/ex_graphe_oriente.svg)


::::

:::: column

## Que valent $V$, $|V|$, $E$, et $|E|$?

. . .

\begin{align*}
V&=\{1, 2, 3, 4\},\\
|V|&=4,\\
E&=\{(1,2),(2,3),(2,4),(4,1),(4,2)\},\\
|E|&=5.
\end{align*}

::::

:::

# Généralités

## Définition

* Le somme $v$ est **adjacent** au sommet $u$, si et seulement si $(u,v)\in E$;
* Si un graphe non-orienté contient une arête $(u,v)$, $v$ est adjacent à $u$ et $u$ et adjacent à $v$.

## Exemple

::: columns

:::: column

![Sommet $a$  adjacent à $c$, $c$ adjacent à $a$.](figs/ex_adj_non_or.svg){width=80%}

::::

:::: column

![Sommet $a$  adjacent à $c$.](figs/ex_adj_or.svg){width=80%}

::::

:::

# Généralités

## Définition

* Un **graphe pondéré** ou **valué** est un graphe dont chaque arête a un
  poids associé, habituellement donné par une fonction de pondération $w:E\rightarrow\mathbb{R}$.

## Exemples

![Graphe pondéré orienté (gauche) et non-orienté (droite).](figs/ex_graph_pond.pdf){width=80%}


# Généralités

## Définition

* Dans un graphe $G(V,E)$, une **chaîne** reliant un sommet $u$ à un sommet $v$ est une suite d'arêtes entre les sommets, $w_0$, $w_1$, ..., $w_k$, telles que 
$$
(w_i, w_{i+1})\in E,\quad u=w_0,\quad v=w_k,\quad \mbox{pour }0\leq i< k,
$$
avec $k$ la longueur de la chaîne (le nombre d'arêtes du chemin).

## Exemples

![Illustration d'une chaîne, ou pas chaîne dans un graphe.](figs/ex_graphe_chaine.pdf){width=80%}

# Généralités

## Définition

* Une **chaîne élémentaire** est une chaîne dont tous les sommets sont distincts, sauf les extrémités qui peuvent être égales

## Exemples

![Illustration d'une chaîne élémentaire.](figs/ex_graphe_chaine_elem.pdf){width=80%}

# Généralités

## Définition

* Une **boucle** est une arête $(v,v)$ d'un sommet vers lui-même.

## Exemples

![Illustration d'une boucle.](figs/ex_graphe_boucle.pdf){width=40%}

# Généralités

## Définition

* Un graphe non-orienté est dit **connexe**, s'il existe un chemin reliant n'importe quelle paire de sommets distincts.

## Exemples

\

::: columns

:::: column

![Graphe connexe. Source, Wikipédia: <https://bit.ly/3yiUzUv>](figs/graphe_connexe.svg){width=80%}

::::

:::: column
![Graphe non-connexe avec composantes connexes. Source, Wikipédia: <https://bit.ly/3KJB76d>](figs/composantes_connexes.svg){width=60%}

::::

:::

# Généralités

## Définition

* Un graphe orienté est dit **fortement connexe**, s'il existe un chemin reliant n'importe quelle paire de sommets distincts.

## Exemples

\

::: columns

:::: column

![Graphe fortement connexe.](figs/ex_graph_fort_connexe.pdf){width=60%}

::::

:::: column

![Composantes fortement connexes. Source, Wikipédia: <https://bit.ly/3w5PL2l>](figs/composantes_fortement_connexes.svg){width=100%}

::::

:::

# Généralités

## Définition

* Un **cycle** dans un graphe *non-orienté* est une chaîne de longueur $\geq 3$ telle que le 1er sommet de la chaîne est le même que le dernier, et dont les arêtes sont distinctes.
* Pour un graphe *orienté* on parle de **circuit**.
* Un graphe sans cycles est dit **acyclique**.

## Exemples

![Illustration de cycles, ou pas.](figs/ex_graphe_cycle.pdf){width=100%}

# Question de la mort

* Qu'est-ce qu'un graphe connexe acyclique?

. . .

* Un arbre!

# Représentations

* La complexité des algorithmes sur les graphes s'expriment en fonction du nombre de sommets $V$, et du nombre d'arêtes $E$:
    * Si $|E|\sim |V|^2$, on dit que le graphe est **dense**.
    * Si $|E|\sim |V|$, on dit que le graphe est **peu dense**.
* Selon qu'on considère des graphes denses ou peu denses, différentes structure de données peuvent être envisagées.

## Question

* Comment peut-on représenter un graphe informatiquement? Des idées (réflexion de quelques minutes)?

. . .

* Matrice/liste d'adjacence.

# Matrice d'adjacence

* Soit le graphe $G(V,E)$, avec $V=\{1, 2, 3, ..., n\}$;
* On peut représenter un graphe par une **matrice d'adjacence**, $A$, de dimension $n\times n$ définie par
$$
A_{ij}=\left\{ \begin{array}{ll}
         1 & \mbox{si } i,j\in E,\\
         0 & \mbox{sinon}.
         \end{array} \right.
$$


::: columns

:::: column

## Exemple

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---4;
    2---5;
    4---5;
    5---3;
```

::::

:::: column

\footnotesize

## Quelle matrice d'adjacence? 

. . .

```
   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 1 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 4 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 1 | 0
```

::::

:::

# Matrice d'adjacence

## Remarques

* Zéro sur la diagonale.
* La matrice d'un graphe non-orienté est symétrique

$$
A_{ij}=A_{ji}, \forall i,j\in[1,n]
$$.

::: columns

:::: column

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---4;
    2---5;
    4---5;
    5---3;
```

::::

:::: column

\footnotesize

```
   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 1 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 4 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 1 | 0
```

::::

:::

# Matrice d'adjacence

* Pour un graphe orienté (digraphe)

::: columns

:::: column

## Exemple

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    2-->1;
    1-->4;
    2-->5;
    5-->2;
    4-->5;
    5-->3;
```

::::

:::: column

\footnotesize

## Quelle matrice d'adjacence? 

. . .

```
   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 0 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 0
---||---|---|---|---|---
 4 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 0 | 0
```

::::

:::

* La matrice d'adjacence n'est plus forcément symétrique
$$
A_{ij}\neq A_{ji}.
$$

# Stockage

* Quel est l'espace nécessaire pour stocker une matrice d'adjacence pour un graphe orienté?

. . .

* $\mathcal{O}(|V|^2)$.
* Quel est l'espace nécessaire pour stocker une matrice d'adjacence pour un graphe non-orienté?

. . .

* $\mathcal{O}(|V|-1)|V|/2$.

# Considérations d'efficacité

* Dans quel type de graphes la matrice d'adjacence est utile?

. . .

* Dans les graphes denses.
* Pourquoi?

. . .

* Dans les graphes peu denses, la matrice d'adjacence est essentiellement composée de `0`.

## Remarque

* Dans la majorité des cas, les grands graphes sont peu denses.
* Comment représenter un graphe autrement?

# La liste d'adjacence (non-orienté)

* Pour chaque sommet $v\in V$, stocker les sommets adjacents à $v$-
* Quelle structure de données pour la liste d'adjacence?

. . .

* Tableau de liste chaînée, vecteur (tableau dynamique), etc.


::: columns

:::: column

## Exemple

![Un graphe non-orienté.](figs/ex_graph_adj.pdf){width=80%}

::::

:::: column


## Quelle liste d'adjacence? 

. . .

![La liste d'adjacence.](figs/ex_graph_list_adj.pdf)


::::

:::

# La liste d'adjacence (orienté)


::: columns

:::: column

## Quelle liste d'adjacence pour...

* Matrix (2min)

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    0-->1;
    0-->2;
    1-->2;
    3-->0;
    3-->1;
    3-->2;
```

::::

:::: column

```











```


::::

:::

# Complexité

## Stockage

* Quelle espace est nécessaire pour stocker une liste d'adjacence (en fonction de $|E|$ et $|V|$)?

. . .

$$
\mathcal{O}(|E|)
$$

* Pour les graphes *non-orientés*: $\mathcal{O}(2|E|)$.
* Pour les graphes *orientés*: $\mathcal{O}(|E|)$.

## Définition

* Le **degré** d'un sommet $v$, est le nombre d'arêtes incidentes du sommet (pour les graphes orientés on a un degré entrant ou sortant).
* Comment on retrouve le degré de chaque sommet avec la liste d'adjacence?

. . .

* C'est la longueur de la liste chaînée.


# Parcours

* Beaucoup d'applications nécessitent de parcourir des graphes:
    * Trouver un chemin d'un sommet à un autre;
    * Trouver si le graphe est connexe;
* Il existe *deux* parcours principaux:
    * en largeur (Breadth-First Search);
    * en profondeur (Depth-First Search).
* Ces parcours créent *un arbre* au fil de l'exploration (si le graphe est non-connexe cela crée une *forêt*, un ensemble d'arbres).

# Illustration: parcours en largeur

![Le parcours en largeur.](figs/parcours_larg.pdf){width=80%}

# Exemple

## Étape par étape (blanc non-visité)

![Initialisation.](figs/parcours_larg_0.pdf){width=50%}

## Étape par étape (gris visité)

![On commence en `x`.](figs/parcours_larg_1.pdf){width=50%}

# Exemple

## Étape par étape

![On commence en `x`.](figs/parcours_larg_1.pdf){width=50%}

## Étape par étape (vert à visiter)

![Vister `w`, `t`, `y`.](figs/parcours_larg_2.pdf){width=50%}

# Exemple

## Étape par étape

![Vister `w`, `t`, `y`.](figs/parcours_larg_2.pdf){width=50%}

## Étape par étape

![`w`, `t`, `y` visités. `u`, `s` à visiter.](figs/parcours_larg_3.pdf){width=50%}

# Exemple

## Étape par étape

![`w`, `t`, `y` visités. `u`, `s` à visiter.](figs/parcours_larg_3.pdf){width=50%}

## Étape par étape

![`u`, `s`, visités. `r` à visiter.](figs/parcours_larg_4.pdf){width=50%}

# Exemple

## Étape par étape

![`u`, `s`, visités. `r` à visiter.](figs/parcours_larg_4.pdf){width=50%}

## Étape par étape

![`r` visité. `v` à visiter.](figs/parcours_larg_5.pdf){width=50%}

# Exemple

## Étape par étape

![`r` visité. `v` à visiter.](figs/parcours_larg_5.pdf){width=50%}

## Étape par étape

![The end. Plus rien à visiter!](figs/parcours_larg_6.pdf){width=50%}

# En faisant ce parcours...


::: columns

:::: column

## Du parcours de l'arbre

![](figs/parcours_larg_6.pdf){width=100%}

::::

:::: column

## Quel arbre est créé par le parcours (2min)?

. . .

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    0[x]-->1[w];
    0-->2[t];
    0-->3[y];
    2-->9[u];
    1-->4[s];
    4-->5[r];
    5-->6[v];
```

::::

:::

## Remarques

* Le parcours dépend du point de départ dans le graphe.
* L'arbre sera différent en fonction du noeud de départ, et de l'ordre de parcours des voisins d'un noeud.

# Le parcours en largeur

## L'algorithme, idée générale (3min, matrix)?

. . .

```C
v = un sommet du graphe
i = 1
pour sommet dans graphe et sommet non-visité
    visiter(v, sommet, i) // marquer sommet à distance i visité 
    i += 1
```

## Remarque

* `i` est la distance de plus cours chemin entre `v` et les sommets en cours de visite.


# Le parcours en largeur

## L'algorithme, pseudo-code (3min, matrix)?

* Comment garder la trace de la distance?

. . .

* Utilisation d'une **file**

. . .

```C
initialiser(graphe) // tous sommets sont non-visités
file = visiter(sommet, vide) // sommet est un sommet du graphe au hasard
tant que !est_vide(file)
    v = défiler(file)
    file = visiter(v, file)
```

## Que fait visiter?

```
file visiter(sommet, file)
    sommet = visité
    pour w = chaque arête de sommet
        si w != visité
            file = enfiler(file, w)
    retourne file
```

# Exercice (5min)

## Appliquer l'algorithme sur le graphe

![](figs/parcours_larg_0.pdf){width=50%}

* En partant de `v`, `s`, ou `u` (par colonne de classe).
* Bien mettre à chaque étape l'état de la file.

# Complexité du parcours en largeur

## Étape 1

* Extraire un sommet de la file;

## Étape 2

* Traîter tous les sommets adjacents.

## Quelle est la complexité?

. . .

* Étape 1: $\mathcal{O}(|V|)$,
* Étape 2: $\mathcal{O}(2|E|)$,
* Total: $\mathcal{O}(|V| + |2|E|)$.

# Exercice

* Établir la liste d'adjacence et appliquer l'algorithme de parcours en largeur au graphe

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;
```


# Illustration: parcours en profondeur

![Le parcours en profondeur. À quel parcours d'arbre cela ressemble-t-il?](figs/parcours_prof.pdf){width=80%}

# Parcours en profondeur

## Idée générale

* Initialiser les sommets comme non-lus
* Visiter un sommet
* Pour chaque sommet visité, on visite un sommet adjacent s'il est pas encore visité récursivement.

## Remarque

* La récursivité est équivalent à l'utilisation d'une **pile**.

# Parcours en profondeur

## Pseudo-code (5min)

. . .

```C
initialiser(graphe) // tous sommets sont non-visités
pile = visiter(sommet, vide) // sommet est un sommet du graphe au hasard
tant que !est_vide(pile)
    v = dépiler(pile)
    pile = visiter(v, pile)
```

## Que fait visiter?

. . .

```C
pile visiter(sommet, pile)
    sommet = visité
    pour w = chaque arête de sommet
        si w != visité
            pile = empiler(pile, w)
    retourne pile
```


# Exercice

* Établir la liste d'adjacence et appliquer l'algorithme de parcours en profondeur au graphe

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;
```

# Interprétation des parcours

* Un graphe vu comme espace d'états (sommet: état, arête: action);
    * Labyrinthe;
    * Arbre des coups d'un jeu.

. . .

* BFS (Breadth-First) ou DFS (Depth-First) parcourent l'espace des états à la recherche du meilleur mouvement.
    * Les deux parcourent *tout* l'espace;
    * Mais si l'arbre est grand, l'espace est gigantesque!

. . .

* Quand on a un temps limité
    * BFS explore beaucoup de coups dans un futur proche;
    * DFS explore peu de coups dans un futur lointain.