Discussion :

[sebus]

Bonjour,

Je cherche des algorithmes sur les graphes et plus précisément les DAG.
Mon premier besoin et but et de montrer qu'un graphe est un DAG, mais j'arrive plus a me souvenir de la méthode !!!

Quelqu'un sait il ou il y aurait un bon lien vers de telles informations? (Désolé mais j'ai pas trouvé dans FAQ ni les liens conseillés...)

Si ca n'existe pas, ne faudrait il pas crée un mémo pour rassembler tout les algos? (Stable, bipolaire et autre....)

[progfou]

Tu peux traduire DAG ?

[sebus]

DAG = Direct Acyclic Graph

Donc un graphe orienté sans cycle

[millie]

Des parcours en profondeur devrait suffir. Si lors d'un parcours tu retombes sur le sommet initial, c'est que la partie du graphe la n'etait pas acyclique.

[sebus]

Je suis d'accord mais ca oblige a faire un parcours en profondeur par sommet ......

Et comme je risque d'avoir plusieurs millier de sommets....

Sinon y'a pas moyen d'optimiser un peu le truc ? Je sais qu'il existe un algo minimal, mais je m'en souviens plus (j'ai completement oublié tous mes précieux cours d'algo et de théorie des graphes de la fac....)

Sinon une FAQ special Graphe ca existe? Ou serait il interessant d'en créer une ? (arbre, graphe, DAG + théorie avec stable, coloration, bipolarité, parcours, flots et autres)

[borisd]

Tu as moins de parcours en profondeur à faire qu'un par sommet : tu n'as besoin de recommencer qu'à partir d'un sommet non marqué par les parcours précédents. La complexité globale est de O(M), M étant le nombre d'arcs, ce qui est déjà assez faible.

[millie]

Sinon une FAQ special Graphe ca existe?

Une cours introductif sur les graphes est en préparation par l'un des membres de developpez.com. Le premier jet de ce cours devrait définir les notions de base, les implémentations possibles des graphes et leur parcours.

Ou serait il interessant d'en créer une ? (arbre, graphe, DAG + théorie avec stable, coloration, bipolarité, parcours, flots et autres)

Oui, effectivement, il serait intéressant d'aborder toutes ces théories. Si tu souhaites contribuer à un cours sur ces notions, tu es le bienvenu Certains d'entre nous ont les connaissances pour réaliser un cours sur certaines de ces parties, mais nous n'avons pas forcement le temps car on travaille en général sur d'autres choses à côté.