Trouver le cycle le plus long dans un graphe orienté en utilisant DFS

J'ai besoin de trouver le plus long cycle dans un graphe orienté à l'aide de DFS.

Une fois, j'ai vu cet article de Wikipédia décrivant la façon de faire cela, et je pense qu'il a approché le problème, quelque chose comme marquant le nœud avec l'un des trois états suivants: Nœud pas encore visité, Terminé la recherche dans le noeud et le Noeud visité, mais pas encore fini de visiter.

Je vous serais reconnaissant si quelqu'un pouvait partager le lien avec moi. Par ailleurs, il n'est pas de l'Algorithme de Tarjan.

Le problème ci-dessous est ce que j'essaie de résoudre, dans le cas où vous voudriez connaître.

Les deux chiffres donnés dans la première ligne est N et M représentent chacun le nombre de nœuds et le nombre d'arêtes orientées.

À partir de la deuxième ligne de M ensembles de deux chiffres A et B, ce qui signifie que le nœud A et B sont connectés, mais vous ne pouvez traverser le nœud de A à B.

input.txt:

7 9  
1 2  
2 3  
3 1  
3 4  
4 5  
5 1  
5 6  
6 7  
7 2

La réponse dans ce cas est de 6, depuis le 2>3>4>5>6>7>2.

source d'informationauteur John Graveston

  1. 5

    Je pense que la plus longue élémentaire cycle (ou circuit) est une meilleure terminologie que le cycle le plus long.

    De toute façon, ce fichier pdf peut être utile: Trouver Tous les Circuits Élémentaires d'un Graphe orienté

    Cette année, un vieux stackoverflow question a également de nombreux liens vers des problèmes et algorithmes:
    Trouver tous les cycles dans un graphe orienté

  2. 1

    En effet, cela peut être démontré que vous pouvez réduire le cycle Hamiltonien dans ce problème en temps polynomial, de sorte qu'il finit par NP-complet. Peu importe si le graphe est orienté ou non orienté.

    Aussi loin que l'algorithme de la manière la plus facile pour résoudre le problème est de backtrack---start dans les nœuds i=1 à n, et toujours d'explorer tous les cycles de départ dans le nœud particulier je. Une fois cela fait, vous éliminez le nœud i et continuer pour le reste du graphe, à partir du nœud i+1. Vous voudrez peut-être faire quelque chose comme nœud de coloration dans la dsv, de distinguer les nœuds que vous ne voulez jamais de visiter à nouveau et ceux que vous avez visité le long du chemin dans ce passage. Vous pouvez également mettre quelque chose comme un horodatage sur les nœuds, semblable à la découverte de fois, mais dans ce cas, vous devez écrire ces temps chaque fois que vous découvrez un nœud, comme la plupart des nœuds sera découvert de nombreuses fois. Les documents énumérés ci-dessus pourrait être utile, et il ya plusieurs façons de le faire pour vous.

  3. 0

    Ce problème est NP-Complet et il n'y a pas un algorithme polynomial en temps.
    Quelle est la taille de votre problème? Je veux dire combien de nœuds sera dans l'entrée graphique?

    le cycle le plus long problème se réduit à cycle Hamiltonien problème:
    http://mathworld.wolfram.com/HamiltonianCycle.html

  4. 0

    J'ai une réponse expliquant un moyen facile de trouver tous les cycles dans un graphe orienté à l'aide de Python et networkX dans un autre post. Trouver tous les cycles dans un graphe orienté

    La solution en sortie une liste contenant tous les cycles du graphe orienté.

    Vous pouvez utiliser cette sortie pour trouver le cycle le plus long et c'est montré ci-dessous:

    import networkx as nx

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["1","2","3","4","5","6","7","9"])

# Add a list of edges:
G.add_edges_from([("7","9"),("1","2"),("2","3"),("3","1"),("3","4"),("4","5"),("5","1"),("5","6"),("6","7"),("7","2")])

#Return a list of cycles described as a list o nodes
all_cycles = list(nx.simple_cycles(G))

#Find longest cycle
answer = []
longest_cycle_len = 0
for cycle in all_cycles:
    cycle_len = len(cycle)
    if cycle_len>longest_cycle_len:
        answer =cycle
        longest_cycle_len = cycle_len

print "Longest Cycle is {} with length {}.".format(answer,longest_cycle_len)

    Réponse: le Cycle le plus long est ['3', '4', '5', '6', '7', '2'] avec une longueur de 6.

    Si vous le trouvez intéressant upvote la réponse originale à cette question. C'est une vieille discussion avec beaucoup de réponses et il va aider à apporter la nouvelle solution.