Licence CC BY-NC-SA

À la découverte des algorithmes de graphe

Les algorithmes les plus courants avec une implémentation en pseudo-code

Dernière mise à jour :

Ce tutoriel va vous expliquer ce qu'est un graphe, et à quoi il sert. Il détaillera les algorithmes de graphe les plus courants, en indiquant leur complexité en temps et en mémoire, avec peut-être des schémas si vous êtes sages.

Chaque algorithme sera accompagné d'un pseudo-code pour laisser au programmeur l'opportunité de le coder dans son langage favori. Le cours est ouvert aux contributions : vous pouvez m'envoyer une implémentation de l'algorithme dans le langage de votre choix et je l'y ajouterais.

Il sera appuyé d'exemples concrets pour que l'intérêt de chaque algorithme apparaisse dans une situation courante. L'objectif est d'apprendre à reconnaître des problèmes de graphe, ou à modéliser un problème sous forme de graphe, pour le résoudre avec des outils éprouvés et efficaces.

Ce document n'a pas pour ambition de faire une démonstration formelle de la complexité ou de la validité des algorithmes. Il n'a aucune vocation académique. Les concepts seront présentés de façon intuitive et didactique pour permettre à tous de les appréhender et de les appliquer aisément. Il se veut être une "boîte à outils" aussi bien qu'un moyen de découvrir ce domaine de l'algorithmique. Le formalisme et la rigueur ont été sacrifiés sur l'autel de la simplicité, mais pas l'exactitude ni la précision.

Pour suivre ce tutoriel vous devez

  • Savoir programmer (variables, boucles, tableaux, fonctions)
  • Avoir des notions de base en algorithmique : récursivité, structures de données courantes, tris…
  • Comprendre ce qu'est la complexité (facultatif mais utile)

Bases de la théorie des graphes

  1. Graphes et représentation de graphe

    1. Dessine moi un graphe !

    2. Un peu de vocabulaire

    3. Représentations et stockage en mémoire

  2. Parcourir un graphe

    1. Le parcours en profondeur et le labyrinthe

    2. Le parcours en largeur et le buzz

    3. L'exhaustif et Uno

  3. Les problèmes usuels de graphes

    1. Le tri topologique et make



Ce tutoriel n'est pas terminé !

D'autres chapitres viendront :

III] Problèmes usuels de graphes

  • Circuit Eulérien
  • Nœuds essentiels
  • Arêtes essentielles
  • Algorithmes dynamiques pour les DAG (Directed Acyclic Graph)

IV] Pathfinding

  • BFS (on en reparle)
  • Ford-Bellman
  • Dijkstra
  • Floyd-Warshall
  • A* et autres heuristiques du même type

Restez au courant si ça vous intéresse.

6 commentaires

Je dois avouer que je suis un peu dubitatif. Tu revendiques ton cours comme étant une « présentation intuitive des graphes », ce qui implique que tu vises un public novice. Mais pourquoi alors sacrifier cette candeur en faisant un spoil massif de tous les algos classiques de graphe ? Je suppose qu'on est d'accord sur la nuisibilité de ne pas laisser l'opportunité à quelqu'un de chercher par lui-même, surtout en algo (il existe des plateformes qui te permettent justement un apprentissage autodidacte, et plus bénéfique qu'un cours magistral… ;) ).

Bref, je ne doute pas de la qualité de ce que tu as (et vas) écrire, mais j'ai un petit souci avec ta démarche.

Je dois avouer que je suis un peu dubitatif. Tu revendiques ton cours comme étant une « présentation intuitive des graphes », ce qui implique que tu vises un public novice. Mais pourquoi alors sacrifier cette candeur en faisant un spoil massif de tous les algos classiques de graphe ? Je suppose qu'on est d'accord sur la nuisibilité de ne pas laisser l'opportunité à quelqu'un de chercher par lui-même, surtout en algo (il existe des plateformes qui te permettent justement un apprentissage autodidacte, et plus bénéfique qu'un cours magistral… ;) ).

Bref, je ne doute pas de la qualité de ce que tu as (et vas) écrire, mais j'ai un petit souci avec ta démarche.

Lucas-84

D'accord mais bon un tutoriel qui te decrit le fonctionnement d'un algo sans jamais t'en donner son implementation c'est complique non ? Enfin meme dans les tutos avec des petits TP, les corrections sont donnees alors que ce ne sont pas les elements principaux …

Je dois avouer que je suis un peu dubitatif. Tu revendiques ton cours comme étant une « présentation intuitive des graphes », ce qui implique que tu vises un public novice. Mais pourquoi alors sacrifier cette candeur en faisant un spoil massif de tous les algos classiques de graphe ? Je suppose qu'on est d'accord sur la nuisibilité de ne pas laisser l'opportunité à quelqu'un de chercher par lui-même, surtout en algo (il existe des plateformes qui te permettent justement un apprentissage autodidacte, et plus bénéfique qu'un cours magistral… ;) ).

Bref, je ne doute pas de la qualité de ce que tu as (et vas) écrire, mais j'ai un petit souci avec ta démarche.

Lucas-84

D'accord mais bon un tutoriel qui te decrit le fonctionnement d'un algo sans jamais t'en donner son implementation c'est complique non ? Enfin meme dans les tutos avec des petits TP, les corrections sont donnees alors que ce ne sont pas les elements principaux …

MeliMelo

Peut⁻être me suis-je mal fait comprendre : je m'insurge justement contre le fait même de décrire le fonctionnement d'un algo sans laisser la peine au lecteur de chercher par lui-même une manière de résoudre ledit problème. Après, l'implémentation est de l'ordre du détail. ;)

C'est le cas partout. Tu vas en universite si tu as un cours sur les graphes, le prof te decrira le fonctionnement des algos et te donnera son implementation en pseudo code. Apres effectivement il y a des TP pour que l'eleve se familiarise avec l'algo et parfois le modifie un peu pour qu'il corresponde aux besoins d'un probleme.

Mais je ne vois toujours pas comment tu souhaiterais enseigner un algo sans en decrire le fonctionnement ? (tu peux pas balancer le pseudo code dans la figure de l'eleve et lui dire : " tiens maintenant tu as tout debrouilles toi ")

Je pense que ce que Lucas-84 veut dire, c'est qu'un exercice permettant de découvrir un algo, guidé si necessaire est plus utile que de lire un cours. Ensuite, une correction de l'exercice présentant l'algo (tel un cours) est nécessaire mais la partie recherche est tout aussi bénéfique que le cours en lui-même. Sinon, j'aime bien l'initiative mais je suis un peu (pas complétement) d'accord avec Lucas-84. Tout le monde n'a pas envie d'effectuer la partie recherche et ils devraient aussi pouvoir trouver du contenu. Toutefois, organiser le tuto de telle sorte à laisser le choix au lecteur de temps en temps (càd mettre un "exercice introductif" puis présenter l'algo en précisant que résoudre l'exercice introductif n'est pas nécessaire à la compréhension du cours) serait surement positif. Enfin, certains préfereraient peut-être choisir l'approche proposée par Lucas-84 mais n'ont pas forcement les ressources nécessaires. Je pense donc que tu devrais préciser dans ton intro qu'il existe d'autres approches pour apprendre ces algos et présenter des ressources pour ceux qui préféreraient. Ca pourrait d'ailleurs même être bénéfique pour ceux qui ne souhaitent pas chercher avant puisque ce sont souvent de bonnes sources d'exercices et donc d'entrainement. Or "practice makes perfect" comme disait une de mes profs d'anglais ;)

+0 -0

En tant qu'autodidacte, j'ai lu différents livres et tutoriels et aucun n'est parfait. Leur appréciation dépend des objectifs que l'on souhaite atteindre et du genre d'information que l'on recherche. Pour ma part, je trouve ce tutoriel intéressant et j'ai hâte de voir la suite. Il m'a permis de consolider ma compréhension sur les graphes. Et je continuerai à explorer d'autres documents pour approfondir.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte