TP d'algorithmique des graphes (IR2)

Projet

Son énoncé (site de Cyril Nicaud).
Voici un exemple de parser utilisant l'interface SAX : Parser.java.

Fiches de TP

• Fiche 1
• Fiche 2
• Fiche 3
• Fiche 4
• Fiche 5

Corrections

• Fiches 1 et 2

Graphes de test

Voici une collection de graphes pour tester les algorithmes implantés.
Ne jamais oublier que «Tester un programme peut démontrer la présence de bugs, jamais leur absence» (Edsger W. Dijkstra).

Algorithme d'Euler

• GrapheN6.dot image
• GrapheN9.dot image
• GrapheN11.dot image

Connexité (cas non orienté)

• GrapheN10.dot image
• GrapheN11.dot image

Connexité (cas orienté)

• GrapheON10.dot image
• GrapheON13.dot image

Détection de DAG

• GrapheON5.dot image
• GrapheON6.dot image
• GrapheON22.dot image

Tri topologique

• GrapheON7.dot image
• GrapheON9.dot image

Nombre de chemins entre deux sommets s et t d'un DAG

• GrapheON9.dot image, s = 3, t = 6
• GrapheON22.dot image, s = 17, t = 6

Algorithme de Dijkstra

• GraphePN7.dot image, plus courte chaîne entre s = 3 et t = 1 ; entre s = 1 et t = 4
• GraphePN10.dot image, plus courte chaîne entre s = 6 et t = 0

Algorithme de Kruskal

• GraphePN7.dot image
• GraphePN12.dot image