Graphes

Point de départ

// Listes d'adjacence. Deux composantes connexes, et un cycle dans la première.
const G = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"],      // A-B-D-C-A : un cycle
  E: ["F"],
  F: ["E"],           // seconde composante
};

// ── Le parcours SANS marquage, pour voir ──────────────────────────────────
function dfsSansMarquage(g, s, visites = {}, garde = { n: 0 }) {
  if (garde.n++ > 60) return visites;         // sans cette garde : pile pleine
  visites[s] = (visites[s] ?? 0) + 1;
  for (const v of g[s]) dfsSansMarquage(g, v, visites, garde);
  return visites;
}

// ── Parcours en profondeur ────────────────────────────────────────────────
function dfs(g, depart, vus = new Set(), ordre = []) {
  // ← à écrire : marquer, traiter, puis descendre chez les voisins non vus
  return ordre;
}

// ── Parcours en largeur, avec prédécesseurs ───────────────────────────────
function bfs(g, depart) {
  const vus = new Set([depart]);
  const pere = { [depart]: null };
  const file = [depart];
  const ordre = [];
  while (file.length > 0) {
    const u = file.shift();
    ordre.push(u);
    for (const v of g[u]) {
      // ← à écrire : marquer À L'ENFILEMENT, noter le père, enfiler
    }
  }
  return { ordre, pere };
}

// Reconstitue le chemin en remontant les pères depuis l'arrivée.
function chemin(pere, arrivee) {
  if (!(arrivee in pere)) return null;
  const c = [];
  for (let s = arrivee; s !== null; s = pere[s]) c.unshift(s);
  return c;
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez dfs() et complétez bfs().
// 2. Comptez les composantes connexes de G.
// 3. Détectez le cycle : un voisin déjà vu qui n'est PAS le père immédiat.

console.log("sans marquage :", JSON.stringify(dfsSansMarquage(G, "A")));

Solution

const G = {
  A: ["B", "C"], B: ["A", "D"], C: ["A", "D"], D: ["B", "C"],
  E: ["F"], F: ["E"],
};

// Un graphe pondéré pour Dijkstra.
const P = {
  A: [["B", 4], ["C", 1]],
  B: [["A", 4], ["D", 1]],
  C: [["A", 1], ["B", 2], ["D", 6]],
  D: [["B", 1], ["C", 6]],
};

function dfsSansMarquage(g, s, visites = {}, garde = { n: 0 }) {
  if (garde.n++ > 60) return visites;
  visites[s] = (visites[s] ?? 0) + 1;
  for (const v of g[s]) dfsSansMarquage(g, v, visites, garde);
  return visites;
}

function dfs(g, depart, vus = new Set(), ordre = []) {
  vus.add(depart);          // marquer AVANT de descendre
  ordre.push(depart);
  for (const v of g[depart]) if (!vus.has(v)) dfs(g, v, vus, ordre);
  return ordre;
}

function bfs(g, depart) {
  const vus = new Set([depart]);
  const pere = { [depart]: null };
  const file = [depart];
  const ordre = [];
  while (file.length > 0) {
    const u = file.shift();
    ordre.push(u);
    for (const v of g[u]) {
      if (vus.has(v)) continue;
      // Marquer À L'ENFILEMENT : sinon un sommet accessible par deux chemins
      // serait enfilé deux fois avant d'être défilé une première fois.
      vus.add(v);
      pere[v] = u;
      file.push(v);
    }
  }
  return { ordre, pere };
}

function chemin(pere, arrivee) {
  if (!(arrivee in pere)) return null;
  const c = [];
  for (let s = arrivee; s !== null; s = pere[s]) c.unshift(s);
  return c;
}

function composantes(g) {
  const vus = new Set();
  const morceaux = [];
  for (const s of Object.keys(g)) {
    if (vus.has(s)) continue;
    morceaux.push(dfs(g, s, vus, []));   // une relance = une composante
  }
  return morceaux;
}

function aUnCycle(g) {
  const vus = new Set();
  function explorer(s, pere) {
    vus.add(s);
    for (const v of g[s]) {
      // La nuance qui compte : en non orienté, l'arête par laquelle on est
      // arrivé mène évidemment à un sommet déjà vu. Il faut l'exclure.
      if (v === pere) continue;
      if (vus.has(v)) return true;
      if (explorer(v, s)) return true;
    }
    return false;
  }
  for (const s of Object.keys(g)) if (!vus.has(s) && explorer(s, null)) return true;
  return false;
}

function dijkstra(g, depart) {
  const distance = {}, pere = {}, traites = new Set();
  for (const s of Object.keys(g)) distance[s] = Infinity;
  distance[depart] = 0;
  pere[depart] = null;

  while (traites.size < Object.keys(g).length) {
    // Le choix glouton : le non traité le plus proche. Une file de priorité
    // (le tas du chapitre 8) remplacerait cette recherche linéaire.
    let u = null;
    for (const s of Object.keys(g)) {
      if (!traites.has(s) && (u === null || distance[s] < distance[u])) u = s;
    }
    if (u === null || distance[u] === Infinity) break;
    traites.add(u);
    for (const [v, poids] of g[u]) {
      if (distance[u] + poids < distance[v]) {
        distance[v] = distance[u] + poids;
        pere[v] = u;
      }
    }
  }
  return { distance, pere };
}

console.log("— sans marquage, sur un graphe cyclique —");
console.log("   visites par sommet :", JSON.stringify(dfsSansMarquage(G, "A")));
console.log("   (la garde a coupé à 60 appels ; sans elle, la pile déborde)");

console.log("");
console.log("— avec marquage —");
console.log("   profondeur depuis A :", dfs(G, "A").join(" "));
const b = bfs(G, "A");
console.log("   largeur    depuis A :", b.ordre.join(" "));

console.log("");
console.log("composantes connexes :", composantes(G).map((c) => c.join("")).join("  |  "));
console.log("contient un cycle    :", aUnCycle(G));
console.log("chemin le plus court A -> D :", chemin(b.pere, "D").join(" -> "),
            "  (" + (chemin(b.pere, "D").length - 1) + " arêtes)");

console.log("");
console.log("— Dijkstra sur le graphe pondéré —");
const d = dijkstra(P, "A");
for (const s of Object.keys(P)) {
  console.log("   A -> " + s + " : distance " + String(d.distance[s]).padStart(2) +
              "  par " + chemin(d.pere, s).join(" -> "));
}
// A -> B coûte 3 en passant par C (1 + 2), pas 4 en direct : c'est
// exactement ce que le BFS ne saurait pas voir, puisqu'il compterait
// une arête contre deux et choisirait la mauvaise.

Avant de commencer

• Les TP 5 à 8 : liste, file, tas, file de priorité
• Un fichier de réseau : arrêts et liaisons avec durées — le vôtre, ou celui d'une ville ouverte

Énoncé

1. Choisir la représentation — Représentez le graphe de deux façons : matrice d'adjacence et listes d'adjacence. Mesurez la mémoire de chacune sur votre réseau, et calculez sa densité. Indice : Comptez le rapport entre le nombre d'arêtes et le carré du nombre de sommets.
2. Charger le réseau — Lisez le fichier et construisez le graphe. Comptez sommets, arêtes, et vérifiez qu'aucun arrêt cité dans une liaison n'est absent de la liste des arrêts.
3. Parcours en largeur — Écrivez le parcours en largeur avec votre file. Utilisez-le pour trouver l'itinéraire en un minimum de CORRESPONDANCES entre deux arrêts, et reconstituez le chemin.
4. Parcours en profondeur — Écrivez-le avec votre pile, puis en récursif. Utilisez-le pour compter les composantes connexes du réseau, et identifiez les arrêts isolés.
5. Détecter un cycle — Sur un graphe orienté de dépendances — par exemple l'ordre des travaux d'un chantier —, détectez un cycle, puis produisez un ordre topologique quand il n'y en a pas.
6. Dijkstra — Implémentez le plus court chemin en TEMPS, avec la file de priorité du TP 8. Comparez le résultat à celui du parcours en largeur et expliquez la différence.
7. Mesurer ce que le tas apporte — Écrivez aussi la version de Dijkstra qui cherche le minimum par balayage linéaire. Comparez les deux sur un réseau de mille, puis de cent mille sommets.
8. Le piège — Ajoutez au réseau une liaison de durée négative — une correspondance qui ferait gagner du temps. Exécutez Dijkstra et expliquez pourquoi le résultat est faux.

C'est réussi quand

• ✓ Votre chargeur signale un arrêt manquant plutôt que de planter
• ✓ Le parcours en largeur et Dijkstra donnent des chemins DIFFÉRENTS, et vous savez expliquer lequel répond à quelle question
• ✓ La version à tas bat nettement la version linéaire à cent mille sommets
• ✓ Vous savez dire précisément quelle hypothèse de Dijkstra une arête négative viole

Correction

réseau : 4 200 arrêts, 9 800 liaisons
densité = 9 800 / 4 200² = 0,00055        → graphe CREUX

matrice d'adjacence : 4200² × 4 o = 70 Mo   (99,9 % de zéros)
listes d'adjacence  : (4200 + 2×9800) × 16 o = 380 Ko

matrice : test d'arête en O(1), parcours des voisins en O(n)
listes  : test en O(degré),     parcours des voisins en O(degré)

void largeur(Graphe *g, int depart, int *distance, int *precedent) {
  for (int i = 0; i < g->n; i++) { distance[i] = -1; precedent[i] = -1; }
  File f; file_init(&f);
  distance[depart] = 0;
  enfiler(&f, depart);

  while (!file_vide(&f)) {
      int u = defiler(&f);
      for (Arete *a = g->voisins[u]; a; a = a->suivant)
          if (distance[a->vers] == -1) {          /* pas encore vu */
              distance[a->vers] = distance[u] + 1;
              precedent[a->vers] = u;             /* pour reconstituer */
              enfiler(&f, a->vers);
          }
  }
}
/* le chemin se relit à l'ENVERS depuis l'arrivée, via precedent */

void dijkstra(Graphe *g, int depart, int *dist, int *prec) {
  for (int i = 0; i < g->n; i++) dist[i] = INT_MAX;
  dist[depart] = 0;
  FilePrio f; fp_init(&f);
  fp_inserer(&f, depart, 0);

  while (!fp_vide(&f)) {
      Element e = fp_extraire_min(&f);
      if (e.priorite > dist[e.sommet]) continue;   /* entrée périmée */
      for (Arete *a = g->voisins[e.sommet]; a; a = a->suivant) {
          int nouveau = dist[e.sommet] + a->duree;
          if (nouveau < dist[a->vers]) {
              dist[a->vers] = nouveau;
              prec[a->vers] = e.sommet;
              fp_inserer(&f, a->vers, nouveau);
          }
      }
  }
}

                     1 000 sommets   100 000 sommets
minimum par balayage     0,004 s          38 s
file de priorité         0,001 s           0,42 s

O(n²) contre O((n + m) log n)

A --(5)--> B --(-4)--> C
A --(2)--> C

Dijkstra traite C en premier (distance 2), le déclare DÉFINITIF,
et ne le reconsidère jamais.
La vraie distance passe par B : 5 - 4 = 1.

→ résultat FAUX, sans aucune erreur signalée

/* ordre topologique par degrés entrants, avec une file */
compter les degrés entrants
enfiler tous les sommets de degré entrant nul
tant que la file n'est pas vide :
  défiler u, l'ajouter au résultat
  pour chaque voisin v : décrémenter son degré entrant,
                         l'enfiler s'il tombe à zéro

si le résultat contient moins de n sommets → il y a un CYCLE