Algo cycle de graph

Algo cycle de graph - Algo - Programmation

Marsh Posté le 29-05-2004 à 14:22:17    

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!!
Reply

Marsh Posté le 29-05-2004 à 14:22:17   

Reply

Marsh Posté le 29-05-2004 à 14:58:51    

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 :
  1. bool detectCycle()
  2. {
  3.       return detectCycleAux(getFirstNodeId(1);
  4. }
  6. bool detectCycleAux(int n)
  7. {
  8.       NodeIdList adjlist;
  9.       int numAdjMarked = 0;
  10.       bool found = false;
  11.       setnode(n).setMarked();
  12.       adjList = getNode(n).getAdj();
  14.       while (!found || adjList.empty())
  15.       {
  16.            if(!getnode(adjList.top()).isMarked())
  17.                 found = detectCycleAux(adjList.top())
  18.            else
  19.                 numAdjMarked++
  20.                 found = found || numAdjMarked > 1
  21.                 adjList.pop()
  22.           }
  23.   return found;
  24.   }


 
 
 
[/cpp]

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed