---
title: "Graphes - Arbres couvrants"
date: "2022-05-03"
patat:
    eval:
        tai:
            command: fish
            fragment: false
            replace: true
        ccc:
            command: fish
            fragment: false
            replace: true
    images:
      backend: auto
---

# Questions

* A quoi sert l'algorithme de Floyd--Warshall?

. . .

* A trouver le plus court chemin entre n'importe quelle paire de sommets d'un graphe pondéré.
* Quelle est la limitation de l'algorithme de Dijkstra n'est pas présente pour l'algorithme de Floyd--Warshall?

. . .

* Les poids peuvent être négatifs.
* Qu'est-ce qu'un *arbre couvrant minimal*?

. . .

* Un arbre couvrant minimal d'un graphe non-orienté et connexe est:
    * un arbre inclu dans le graphe qui connecte tous les sommets du graphe et dont le poids total des arêtes est minimal.

# Arbres couvrants minimaux

* Comment générer un arbre couvrant minimal?

![Un graphe, connexe, non-orienté, pondéré, et son arbre couvrant minimal.](figs/arbre_couvrant_minimal_exemple.png)

# Algorithme de Prim

::: columns

:::: column

## Un exemple

![Le graphe de départ.](figs/prim_0.png)

::::

:::: column

## On part de `e` (au hasard)

![Le sommet `e` est couvert.](figs/prim_1.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_1.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `e->d`

![Le sommet `d` est couvert.](figs/prim_2.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_2.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `d->a`

![Le sommet `a` est couvert.](figs/prim_3.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_3.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `d->c`

![Le sommet `c` est couvert.](figs/prim_4.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_4.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `e->b`

![Le sommet `b` est couvert.](figs/prim_5.png)

::::

:::

* Game over!

# Algorithme de Prim

## Structures de données

* Dans quoi allons nous stocker les sommets?

. . .

* File de priorité min.
* Autre chose?

. . .

* Tableau des distances (comme pour Dijkstra).
* Autre chose?

. . .

* Tableau des parents (presque comme pour Dijkstra).
* Autre chose?

. . .

* Non.

# Algorithme de Prim

## Initialisation: Pseudo-code (2min)

. . .

```C
file_priorité, distance, parent initalisation(graphe)
    r = aléatoire(graphe)
    distance[r] = 0
    parent[r] = indéfini
    fp = file_p_vide()
    pour v dans sommets(graphe)
        si v != r
            distance[v] = infini
            parent[v]   = indéfini
        fp = enfiler(fp, v, distance[v])
    retourne fp, distance, parent
```

# Algorithme de Prim

## Algorithme: Pseudo-code (5min)

. . .

```C
sommets, parent prim(file_priorité, distance, parent)
    sommets = vide
    tant que !est_vide(file_priorité)
        u, fp = défiler(file_priorité)
        sommets = insérer(sommets, u)
        pour v dans voisinage de u et pas dans sommets 
        // ou dans file_priorité
            si w(u, v) < distance[v]
                parent[w] = u
                distance[w] = w(u, v)
                fp = changer_priorité(fp, w, w(u, v))
    retourne sommets, parent
```

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 1.](figs/prim_1.png)

::::

:::: column

```
FP |  e  |  d  |  b  |  c  |  a  |
----------------------------------
D  |  0  | inf | inf | inf | inf |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  -  |  -  |  -  |  -  |
```

## Devient?

. . .

```
FP |  d  |  b  |  c  |  a  |
----------------------------
D  |  4  |  5  |  5  | inf |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  e  |  -  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 2.](figs/prim_2.png)

::::

:::: column

```
FP |  d  |  b  |  c  |  a  |
----------------------------
D  |  4  |  5  |  5  | inf |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  e  |  -  |
```

## Devient?

. . .

```
FP |  a  |  c  |  b  |
----------------------
D  |  2  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 3.](figs/prim_3.png)

::::

:::: column

```
FP |  a  |  c  |  b  |
----------------------
D  |  2  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

## Devient?

. . .

```
FP |  c  |  b  |
----------------
D  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 4.](figs/prim_4.png)

::::

:::: column

```
FP |  c  |  b  |
----------------
D  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

## Devient?

. . .

```
FP |  b  |
----------
D  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 5.](figs/prim_4.png)

::::

:::: column

```
FP |  b  |
----------
D  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

## Devient?

. . .

```
FP |
----
D  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exercice: algorithme de Prim

## Appliquer l'algorithme de Prim à (15min):

![En démarrant du sommet $V_1$.](figs/prim_exercice.png)

# Exercice: algorithme de Prim

## Solution

![](figs/prim_solution.png)

# Complexité de l'algorithme de Prim

\footnotesize

```C
file_priorité, distance, parent initalisation(graphe)
    // choix r et initialisation
    pour v dans sommets(graphe)
O(|V|)  // initialisation distance et parent
        fp = enfiler(fp, v, distance[v])
    retourne fp, distance, parent
sommets, parent prim(file_priorité, distance, parent)
    sommets = vide
    tant que !est_vide(file_priorité)
O(|V|)  u, fp = défiler(file_priorité)
        sommets = insérer(sommets, u)
        pour v dans voisinage de u et pas dans sommets
    O(|E|)  si w(u, v) < distance[v]
                // màj dista + parent
        O(|V|)  fp = changer_priorité(fp, w, w(u, v))
    retourne sommets, parent
```

* $O(|V|)+O(|E|)+O(|V|^2)=O(|E|+|V|^2)$
* Remarque: $O(|E|)$ n'est pas mutliplié par $O(|V|)$, car les arêtes parcourues qu'une fois en **tout**.

# Algorithme de Kruskal

* On ajoute les arêtes de poids minimal:
    * si cela ne crée pas de cycle;
    * on s'arrête quand on a couvert tout le graphe.

. . .

* Comment on fait ça?

. . .

* Faisons un exemple pour voir.

# Algorithme de Kruskal: exemple

::: columns

:::: column

## Un exemple

![Le graphe de départ.](figs/kruskal_0.png)

::::

:::: column

## On part de `(a, d)` (poids le plus faible)

![Les sommets `a, d` sont couverts.](figs/kruskal_1.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## On continue avec `(c, d)`

![On aurait pu choisir `(d, e)` aussi.](figs/kruskal_1.png)

::::

:::: column

## Résultat

![Les sommets `a, d, c` sont couverts.](figs/kruskal_2.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## On continue avec `(d, e)`

![Le poids de `(d, e)` est le plus bas.](figs/kruskal_2.png)

::::

:::: column

## Résultat

![Les sommets `a, d, c, e` sont couverts.](figs/kruskal_3.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## On continue avec `(b, e)`

![Le poids de `(b, e)` est le plus bas.](figs/kruskal_3.png)

::::

:::: column

## Résultat

![Les sommets `a, d, c, e, b` sont couverts.](figs/kruskal_4.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## Mais pourquoi pas `(c, e)`?

![Le poids de `(b, e)` ou `(a,c)` est le même.](figs/kruskal_3.png)

::::

:::: column

## Résultat: un cycle

![Les sommets `a, d, c, e` sont couverts.](figs/kruskal_cycle.png)

::::

:::

* Comment faire pour empêcher l'ajout de `(c, e)` ou `(a, c)`?

. . .

* Si les deux sommets sont déjà couverts nous sommes sauvés (presque)!

# Algorithme de Kruskal

## L'initialisation

* Créer un ensemble de sommets pour chaque de sommet du graphe ($V_1$, $V_2$, ...):
    * $V_1=\{v_1\}$, $V_2=\{v_2\}$, ...
    * S'il y a $n$ sommets, il y a $n$ $V_i$.
* Initialiser l'ensemble $A$ des arêtes "sûres" constituant l'arbre couvrant minimal, $A=\emptyset$.
* Initialiser l'ensemble des sommets couverts $F=\emptyset$
* Trier les arêtes par poids croissant dans l'ensemble $E$.

## Mise à jour

* Tant qu'il reste plus d'un $V_i$:
    * Pour $(u,v)\in A$ à poids minimal:
    * Retirer $(u,v)$ de $A$,
    * Si $u\in V_i$ et $v\in V_j$ avec $V_i\cap V_j=\emptyset$:
        * Ajouter $(u,v)$ à $A$;
        * Fusionner $U$ et $V$ dans $F$.