Je souhaite trouver le nombre total de cycles et de longueurs de cycles dans un graphe non orienté connecté. Puis-je utiliser DFS? Ou DFS peut-il trouver un seul cycle? Tout code va certainement aider.Recherche du nombre total de cycles et de la longueur de cycle
Jetez un oeil à la référence suivante:
Exactement ce que j'ai posté. Je n'ai pas reçu de nouvelle notification à temps, désolé. – colithium
comme noté dans le pdf cité: Le nombre de cycles peut être exponentiel dans le nombre de nœuds. En utilisant un simple DFS, chaque cycle est trouvé en utilisant un pas de temps, résultant en un temps de fonctionnement exponentiel. Si cela devient un problème (sur un graphe dense même pour moins de 100 nœuds), il faut utiliser un algorithme plus sophistiqué. Je pensais qu'il existe un. – eci
Quelle langue travaillez-vous? Et je pense que l'un d'eux devrait être BFS =) – colithium
Aussi, sachez que le nombre de cycles dans un graphique de taille modérée peut être ÉNORME. – colithium
Je veux utiliser Java –