Représentations Mémoire des Graphes

Liste d'Adjacence

Cette structure est optimale pour les graphes creux. Elle utilise un vecteur de listes pour stocker les voisins de chaque sommet.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

class GrapheAdjacence {
private:
    int nbSommets;
    std::vector<std::list<int>> adj;

public:
    GrapheAdjacence(int n) : nbSommets(n), adj(n) {}

    void connecter(int source, int destination, bool bidirectionnel = true) {
        if (source < nbSommets && destination < nbSommets) {
            adj[source].push_back(destination);
            if (bidirectionnel) {
                adj[destination].push_back(source);
            }
        }
    }

    void deconnecter(int u, int v) {
        adj[u].remove(v);
        adj[v].remove(u);
    }

    void afficher() {
        for (int i = 0; i < nbSommets; ++i) {
            std::cout << "Sommet " << i << " :";
            for (int voisin : adj[i]) std::cout << " " << voisin;
            std::cout << std::endl;
        }
    }
};

Matrice d'Adjacence

Utilise un tableau bidimensionnel. Idéal pour les graphes denses ou pour vérifier rapidement l'existence d'une arête.

class MatriceGraphe {
private:
    int ordre;
    std::vector<std::vector<int>> grille;

public:
    MatriceGraphe(int n) : ordre(n), grille(n, std::vector<int>(n, 0)) {}

    void insererArete(int i, int j, int poids = 1) {
        grille[i][j] = poids;
        grille[j][i] = poids;
    }

    bool sontConnectes(int i, int j) {
        return grille[i][j] != 0;
    }
};

Algorithmes de Plus Court Chemin

Dijkstra (Optimisation par Tas)

Recherche du chemin le plus court à partir d'une source unique dans un graphe à poids positifs.

#include <queue>
#include <vector>

const int INF = 0x3f3f3f3f;
typedef std::pair<int, int> PII;

void calculerDijkstra(int depart, int n, std::vector<PII> adj[], int dist[]) {
    std::fill(dist, dist + n + 1, INF);
    dist[depart] = 0;
    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> file_prio;
    file_prio.push({0, depart});

    while (!file_prio.empty()) {
        int d = file_prio.top().first;
        int u = file_prio.top().second;
        file_prio.pop();

        if (d > dist[u]) continue;

        for (auto& arete : adj[u]) {
            int v = arete.first;
            int poids = arete.second;
            if (dist[v] > dist[u] + poids) {
                dist[v] = dist[u] + poids;
                file_prio.push({dist[v], v});
            }
        }
    }
}

Bellman-Ford et SPFA

Bellman-Ford permet de gérer les poids négatifs. SPFA (Shortest Path Faster Algorithm) est une optimisation utilisant une file d'attente pour ne traiter que les sommets dont la distance a été mise à jour.

bool spfa(int n, int depart, std::vector<PII> adj[], int dist[], int compteur[]) {
    std::vector<bool> en_file(n + 1, false);
    std::queue<int> q;

    std::fill(dist, dist + n + 1, INF);
    dist[depart] = 0;
    q.push(depart);
    en_file[depart] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        en_file[u] = false;

        for (auto& cible : adj[u]) {
            int v = cible.first;
            int w = cible.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                compteur[v] = compteur[u] + 1;
                if (compteur[v] >= n) return true; // Cycle négatif détecté
                if (!en_file[v]) {
                    q.push(v);
                    en_file[v] = true;
                }
            }
        }
    }
    return false;
}

Floyd-Warshall

Algorithme de programmation dynamique pour trouver les plus courts chemins entre toutes les paires de sommets (O(n³)).

void floydWarshall(int n, std::vector<std::vector<int>>& d) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF)
                    d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

Arbres Couvrants Minimaux (MST)

Algorithme de Kruskal

Basé sur le tri des arêtes et l'utilisation d'une structure Union-Find pour éviter les cycles.

struct Arete {
    int u, v, poids;
    bool operator<(const Arete& autre) const { return poids < autre.poids; }
};

int trouverRacine(int i, std::vector<int>& parent) {
    if (parent[i] == i) return i;
    return parent[i] = trouverRacine(parent[i], parent);
}

int kruskal(int n, std::vector<Arete>& aretes) {
    std::sort(aretes.begin(), aretes.end());
    std::vector<int> parent(n + 1);
    for (int i = 1; i <= n; i++) parent[i] = i;

    int cout_total = 0, arcs_ajoutes = 0;
    for (auto& e : aretes) {
        int r1 = trouverRacine(e.u, parent);
        int r2 = trouverRacine(e.v, parent);
        if (r1 != r2) {
            parent[r1] = r2;
            cout_total += e.poids;
            arcs_ajoutes++;
        }
    }
    return (arcs_ajoutes == n - 1) ? cout_total : -1;
}

Parcours de Graphes et Recherche

Le DFS (Depth First Search) explore aussi loin que possible le long de chaque branche avant de revenir en arrière. Le BFS (Breadth First Search) explore les voisins immédiats avant de passer au niveau suivant.

Exemple de recherche avec mémoïsation (DFS)

std::vector<int> memo;
int dfsExploration(int u, const std::vector<std::vector<int>>& adj) {
    if (memo[u] != -1) return memo[u];
    
    int resultat = 1;
    for (int v : adj[u]) {
        resultat = std::max(resultat, 1 + dfsExploration(v, adj));
    }
    return memo[u] = resultat;
}

Structures Spécialisées : Trie et Segment Tree

Trie (Arbre Préfixe)

Structure de données utilisée pour stocker un ensemble de chaînes de caractères, optimisant les recherches de préfixes.

struct NoeudTrie {
    NoeudTrie* enfants[26] = {nullptr};
    bool estFin = false;

    void inserer(const std::string& mot) {
        NoeudTrie* courant = this;
        for (char c : mot) {
            int idx = c - 'a';
            if (!courant->enfants[idx]) courant->enfants[idx] = new NoeudTrie();
            courant = courant->enfants[idx];
        }
        courant->estFin = true;
    }
};

Arbre Binaires et Propriétés

Les arbres sont des graphes acycliques connectés. Dans un Arbre Binaire de Recherche (BST), pour chaque nœud, les valeurs du sous-arbre gauche sont inférieures et celles du sous-arbre droit supérieures.

struct NoeudArbre {
    int donnee;
    NoeudArbre *gauche, *droit;
    NoeudArbre(int val) : donnee(val), gauche(nullptr), droit(nullptr) {}
};

// Recherche de l'ancêtre commun le plus proche (LCA)
NoeudArbre* trouverLCA(NoeudArbre* racine, int p, int q) {
    if (!racine || racine->donnee == p || racine->donnee == q) return racine;
    NoeudArbre* G = trouverLCA(racine->gauche, p, q);
    NoeudArbre* D = trouverLCA(racine->droit, p, q);
    if (G && D) return racine;
    return G ? G : D;
}