Algo

Algo cycle de graph

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Algo cycle de graph

Willyzekid

Bonjour,

Je cherche un algo pour detecter les cycles (et retourner un pointeur sur le node ou le cycle commence) dans une liste. Le problème c'est de le faire avec une compléxité temps o(n) et en espace o(1).
C'est chaud mais les suggestions sont les bienvenues!

---------------
Horizon pas Net, reste à la buvette!!

Publicité

xiluoc

un pc pour les unirs ....

si ca peus taider voila uen fonction qui detecte si il y a un cycle, su tu veus le reste des fichiers je te les envoi par mp.

Code :

bool detectCycle()
{
return detectCycleAux(getFirstNodeId(1);
}
bool detectCycleAux(int n)
{
NodeIdList adjlist;
int numAdjMarked = 0;
bool found = false;
setnode(n).setMarked();
adjList = getNode(n).getAdj();
while (!found || adjList.empty())
{
if(!getnode(adjList.top()).isMarked())
found = detectCycleAux(adjList.top())
else
numAdjMarked++
found = found || numAdjMarked > 1
adjList.pop()
}
return found;
}

[/cpp]

FORUM HardWare.fr

Programmation

Algo

Algo cycle de graph

Sujets relatifs
[algo] approximation du sinus : on va jusqu'a quel ordre ?	Peut-on flasher la bibliothèque de programme d'une casio graph 65 ?
[ALGO/SQL] Gérer les arbres en SQL	Algo du plus court chemin avec des boucles dans le graphe
Algo de shannon fano	Analyse d'images : algo de Resenfeld
[algo] trouver le vainqueur à chi fou mi	[ALGO] optimisation, tout les possibilités variantes d'un mot
[IA] algo SMA*	Graph pour affichage se stat genre sondage.
Plus de sujets relatifs à : Algo cycle de graph

Page générée en 0.055 secondes