Comment fonctionnent les algorithmes
Chapter 5 Graphs

Chapitre 5 : Graphes dans les algorithmes

Les graphes sont une structure de données fondamentale qui modélise les connexions et les relations entre les objets. Ils ont de nombreuses applications dans l'informatique et au-delà, de la modélisation des réseaux sociaux et des liens de pages Web, à la résolution de problèmes dans les transports, la planification et l'allocation des ressources. Dans ce chapitre, nous explorons les propriétés de base et les algorithmes pour travailler avec des graphes, en nous concentrant sur les graphes non orientés, la recherche en profondeur et en largeur, les arbres couvrants minimaux et les plus courts chemins.

Graphes non orientés

Un graphe non orienté est un ensemble de sommets (ou nœuds) reliés par des arêtes. Formellement, nous définissons un graphe non orienté G comme une paire (V, E), où V est un ensemble de sommets et E est un ensemble de paires non ordonnées de sommets, appelées arêtes. Une arête (v, w) relie les sommets v et w. Nous disons que v et w sont adjacents ou voisins. Le degré d'un sommet est le nombre d'arêtes qui y sont incidentes.

Voici un exemple simple d'un graphe non orienté :

   A --- B
  /     / \
 /     /   \
C --- D --- E

Dans ce graphe, l'ensemble des sommets V = {A, B, C, D, E} et l'ensemble des arêtes E = {(A, B), (A, C), (B, D), (B, E), (C, D), (D, E)}.

Il existe plusieurs façons de représenter un graphe dans un programme. Deux représentations courantes sont :

  1. Matrice d'adjacence : Une matrice booléenne n x n A, où n est le nombre de sommets. L'entrée A[i][j] est vraie s'il y a une arête du sommet i au sommet j, et fausse sinon.

  2. Listes d'adjacence : Un tableau Adj de taille n, où n est le nombre de sommets. L'entrée Adj[v] est une liste contenant les voisins du sommet v.

Le choix de la représentation dépend de la densité du graphe (rapport entre le nombre d'arêtes et le nombre de sommets) et des opérations que nous devons effectuer. Les matrices d'adjacence sont simples mais peuvent être inefficaces pour les graphes épars. Les listes d'adjacence sont plus économes en espace pour les graphes épars et permettent un accès plus rapide aux voisins d'un sommet.

Voici un exemple de la façon dont nous pourrions représenter le graphe ci-dessus à l'aide de listes d'adjacence en Java :

List<Integer>[] graph = (List<Integer>[]) new List[5];
graph[0] = Arrays.asList(1, 2);        // A -> B, C
graph[1] = Arrays.asList(0, 3, 4);     // B -> A, D, E
graph[2] = Arrays.asList(0, 3);        // C -> A, D
graph[3] = Arrays.asList(1, 2, 4);     // D -> B, C, E
graph[4] = Arrays.asList(1, 3);        // E -> B, D

Recherche en profondeur (DFS)

La recherche en profondeur (DFS) est un algorithme fondamental de parcours de graphe qui explore autant que possible le long de chaque branche avant de revenir en arrière. Il peut être utilisé pour résoudre de nombreux problèmes de graphe, comme la recherche de composants connexes, le tri topologique et la détection de cycles.

L'algorithme DFS fonctionne comme suit :

  1. Commencer à un sommet source s.
  2. Marquer le sommet courant comme visité.
  3. Visiter de manière récursive tous les sommets non marqués w adjacents au sommet courant.
  4. Si tous les sommets adjacents au sommet courant ont été visités, revenir en arrière vers le sommet à partir duquel le sommet courant a été exploré.
  5. S'il reste des sommets non marqués, en sélectionner un et répéter à partir de l'étape 1.

Voici une implémentation Java simple de DFS utilisant des listes d'adjacence :

boolean[] visited;
 
void dfs(List<Integer>[] graph, int v) {
    visited[v] = true;
    for (int w : graph[v]) {
        if (!visited[w]) {
            dfs(graph, w);
        }
    }
}

Pour effectuer un parcours DFS complet, nous appelons dfs(graph, s) pour chaque sommet s du graphe, où visited est initialisé à false pour tous les sommets.

DFS a de nombreuses applications. Par exemple, nous pouvons l'utiliser pour trouver les composants connexes dans un graphe non orienté en exécutant DFS à partir de chaque sommet non visité et en attribuant chaque sommet à un composant en fonction de l'arbre DFS.

Recherche en largeur (BFS)

La recherche en largeur (BFS) est un autre algorithme fondamental de parcours de graphe qui explore les sommets par couches. Il visite tous les sommets au niveau de profondeur actuel avant de passer aux sommets au niveau de profondeur suivant.

L'algorithme BFS fonctionne comme suit :

  1. Commencer à un sommet source s et le marquer comme visité.
  2. Enfiler s dans une file d'attente FIFO.
  3. Tant que la file d'attente n'est pas vide : a. Défiler un sommet v de la file d'attente. b. Pour chaque sommet w adjacent à v non marqué, le marquer comme visité et l'enfiler dans la file d'attente.Voici la traduction française du fichier Markdown avec la traduction des commentaires pour le code :

Tant que la file d'attente n'est pas vide :

  • Défiler un sommet v.
  • Pour chaque sommet non marqué w adjacent à v :
    • Marquer w comme visité.
    • Enfiler w.

Voici une implémentation Java de BFS en utilisant des listes d'adjacence :

boolean[] visited;
 
void bfs(List<Integer>[] graph, int s) {
    Queue<Integer> queue = new LinkedList<>();
    // Marquer le sommet de départ comme visité
    visited[s] = true;
    queue.offer(s);
 
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w : graph[v]) {
            // Si le sommet w n'a pas été visité
            if (!visited[w]) {
                // Marquer w comme visité
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

BFS est particulièrement utile pour trouver les plus courts chemins dans les graphes non pondérés. La distance du sommet source à tout autre sommet est le nombre minimum d'arêtes dans un chemin entre eux. BFS garantit de trouver le plus court chemin.

Arbres couvrants minimaux

Un arbre couvrant minimal (ACM) est un sous-ensemble des arêtes d'un graphe non orienté connexe et pondéré qui relie tous les sommets, sans aucun cycle et avec le poids total des arêtes minimal possible.

Deux algorithmes classiques pour trouver les ACM sont l'algorithme de Kruskal et l'algorithme de Prim.

L'algorithme de Kruskal fonctionne comme suit :

  1. Créer une forêt F où chaque sommet est un arbre séparé.
  2. Créer un ensemble S contenant toutes les arêtes du graphe.
  3. Tant que S n'est pas vide et F n'est pas encore un arbre couvrant :
    • Retirer une arête de poids minimal de S.
    • Si l'arête retirée relie deux arbres différents, l'ajouter à F, combinant ainsi deux arbres en un seul.

L'algorithme de Prim fonctionne comme suit :

  1. Initialiser un arbre avec un seul sommet, choisi arbitrairement dans le graphe.
  2. Faire grandir l'arbre d'une arête : parmi toutes les arêtes qui relient l'arbre aux sommets qui n'y sont pas encore, trouver l'arête de poids minimal et l'ajouter à l'arbre.
  3. Répéter l'étape 2 jusqu'à ce que tous les sommets soient dans l'arbre.

Voici une implémentation Java de l'algorithme de Prim :

int minKey(int[] key, boolean[] mstSet, int V) {
    // Trouver l'indice du sommet avec la clé minimale parmi les sommets non inclus dans l'ACM
    int min = Integer.MAX_VALUE, min_index = -1;
    for (int v = 0; v < V; v++)
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    return min_index;
}
```Voici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :
 
```java
for (int v = 0; v < V; v++) {
    // Si le nœud v n'est pas dans l'ensemble MST et que sa clé est inférieure au minimum actuel
    if (!mstSet[v] && key[v] < min) {
        min = key[v];
        min_index = v;
    }
}
return min_index;
}
 
void primMST(int[][] graph, int V) {
    int[] parent = new int[V];
    int[] key = new int[V];
    boolean[] mstSet = new boolean[V];
 
    // Initialiser toutes les clés à la valeur maximale et tous les nœuds comme n'appartenant pas à l'ensemble MST
    for (int i = 0; i < V; i++) {
        key[i] = Integer.MAX_VALUE;
        mstSet[i] = false;
    }
 
    // Définir la clé du nœud source à 0 et son parent à -1
    key[0] = 0;
    parent[0] = -1;
 
    // Construire l'arbre couvrant minimal
    for (int count = 0; count < V - 1; count++) {
        // Sélectionner le nœud avec la plus petite clé parmi ceux qui ne sont pas dans l'ensemble MST
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;
 
        // Mettre à jour les clés des nœuds voisins de u
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
 
    printMST(parent, graph, V);
}

Les arbres couvrants minimaux (MST) ont de nombreuses applications, comme la conception de réseaux (communication, électrique, hydraulique, informatique) et l'approximation des problèmes du voyageur de commerce.

Chemins les plus courts

Le problème des chemins les plus courts consiste à trouver un chemin entre deux sommets d'un graphe de sorte que la somme des poids de ses arêtes soit minimisée. Ce problème a de nombreuses variantes, comme les chemins les plus courts à source unique, tous les plus courts chemins, et les plus courts chemins à destination unique.

L'algorithme de Dijkstra est un algorithme glouton qui résout le problème des chemins les plus courts à source unique pour un graphe avec des poids d'arêtes non négatifs. Il fonctionne comme suit :

  1. Créer un ensemble sptSet (ensemble de l'arbre des plus courts chemins) qui garde la trace des sommets inclus dans l'arbre des plus courts chemins.
  2. Attribuer une valeur de distance à tous les sommets du graphe. Initialiser toutes les valeurs de distance à l'infini. Attribuer une valeur de distance de 0 au sommet source.
  3. Tant que sptSet n'inclut pas tous les sommets, choisir un sommet v qui n'est pas dans sptSet et qui a la plus petite valeur de distance. Inclure v dans sptSet.
  4. Mettre à jour la valeur de distance de tous les sommets adjacents à v. Pour mettre à jour les valeurs de distance, parcourir tous les sommets adjacents. Pour chaque sommet adjacent w, si la somme de la distance de v et du poids de l'arête (v, w) est inférieure à la distance actuelle de w, mettre à jour la distance de w.Voici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :

Valeur de v (à partir de la source) et poids de l'arête v-w, est inférieure à la valeur de distance de w, alors mettre à jour la valeur de distance de w.

Voici une implémentation Java de l'algorithme de Dijkstra :

public void dijkstra(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
    boolean[] sptSet = new boolean[V];
 
    for (int i = 0; i < V; i++) {
        dist[i] = Integer.MAX_VALUE;
        sptSet[i] = false;
    }
 
    dist[src] = 0;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
 
    printSolution(dist);
}

L'algorithme de Bellman-Ford est un autre algorithme pour trouver les plus courts chemins d'un seul sommet source vers tous les autres sommets dans un graphe orienté pondéré. Contrairement à l'algorithme de Dijkstra, l'algorithme de Bellman-Ford peut gérer les graphes avec des poids d'arêtes négatifs, tant qu'il n'y a pas de cycles de poids négatifs.

L'algorithme fonctionne comme suit :

  1. Initialiser les distances depuis la source vers tous les sommets comme infini et la distance vers la source elle-même comme 0.
  2. Détendre toutes les arêtes |V| - 1 fois. Pour chaque arête u-v, si la distance vers v peut être raccourcie en prenant l'arête u-v, mettre à jour la distance vers v.
  3. Vérifier les cycles de poids négatifs. Exécuter une étape de détente pour toutes les arêtes. Si une distance change, alors il y a un cycle de poids négatif.

Voici une implémentation Java de l'algorithme de Bellman-Ford :

public void bellmanFord(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
 
    for (int i = 0; i < V; i++)
        dist[i] = Integer.MAX_VALUE;
    dist[src] = 0;
 
    for (int i = 1; i < V; i++) {
        for (int u = 0; u < V; u++) {
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
 
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }
    }
 
    printSolution(dist);
}

Les algorithmes de plus courts chemins ont de nombreuses applications, comme dans les systèmes de navigation, les protocoles de routage réseau et la planification des transports. Ils sont des outils fondamentaux en théorie des graphes et sont essentiels dans de nombreuses tâches de traitement des graphes.

Conclusion

Les graphes sont des structures de données polyvalentes et puissantes qui peuvent modéliser une grande variété de problèmes. Dans ce chapitre, nous avons exploré les propriétés et les types de base des graphes, et étudié les algorithmes de graphes fondamentaux, notamment la recherche en profondeur, la recherche en largeur, les arbres couvrants minimaux et les plus courts chemins.

La recherche en profondeur et la recherche en largeur fournissent des moyens systématiques d'explorer un graphe et constituent la base de nombreux algorithmes de graphes avancés. Les algorithmes d'arbre couvrant minimal comme ceux de Kruskal et de Prim permettent de trouver un arbre qui connecte tous les sommets avec un poids total minimal. Les algorithmes de plus courts chemins comme ceux de Dijkstra et de Bellman-Ford permettent de trouver les chemins de poids minimal entre les sommets.

Comprendre ces concepts et algorithmes de base est crucial pour travailler efficacement avec les graphes et relever des problèmes complexes dans divers domaines. Au fur et à mesure de votre progression dans l'étude des algorithmes, vous rencontrerez des algorithmes de graphes plus avancés qui s'appuient sur ces techniques fondamentales.

Les graphes offrent un langage puissant pour décrire et résoudre des problèmes en informatique et au-delà. Maîtriser les algorithmes de graphes vous équipera d'un ensemble d'outils polyvalents pour modéliser et résoudre une large gamme de problèmes computationnels.Voici la traduction française du fichier Markdown fourni, avec les commentaires traduits mais le code laissé intact :

Défis NAL

Défi 1 : Créer une fonction pour calculer la moyenne d'une liste de nombres

def calculate_average(numbers):
    """
    Calcule la moyenne d'une liste de nombres.
 
    Args:
        numbers (list): Une liste de nombres.
 
    Returns:
        float: La moyenne des nombres.
    """
    if not numbers:
        return 0.0
    return sum(numbers) / len(numbers)

Défi 2 : Écrire une fonction pour inverser une chaîne de caractères

def reverse_string(string):
    """
    Inverse une chaîne de caractères.
 
    Args:
        string (str): La chaîne de caractères à inverser.
 
    Returns:
        str: La chaîne de caractères inversée.
    """
    return string[::-1]

Défi 3 : Créer une fonction pour trouver le nombre le plus grand dans une liste

def find_max(numbers):
    """
    Trouve le nombre le plus grand dans une liste.
 
    Args:
        numbers (list): Une liste de nombres.
 
    Returns:
        int: Le nombre le plus grand de la liste.
    """
    if not numbers:
        return None
    return max(numbers)

Défi 4 : Écrire une fonction pour vérifier si un nombre est premier

def is_prime(n):
    """
    Vérifie si un nombre est premier.
 
    Args:
        n (int): Le nombre à vérifier.
 
    Returns:
        bool: True si le nombre est premier, False sinon.
    """
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

Défi 5 : Créer une fonction pour trier une liste de nombres par ordre croissant

def sort_numbers(numbers):
    """
    Trie une liste de nombres par ordre croissant.
 
    Args:
        numbers (list): Une liste de nombres.
 
    Returns:
        list: La liste de nombres triée par ordre croissant.
    """
    return sorted(numbers)
Chapter 4 Searching AlgorithmsChapter 6 Strings