15

DFS を使用して有向グラフの最長サイクルを見つける必要があります。

このウィキペディアの記事でこれを行う方法を説明しているのを見たことがありますが、ノードを 3 つの状態のいずれかでマークするような問題にアプローチしたと思います。 .

誰かが私とリンクを共有していただければ幸いです。ちなみに、Tarjan のアルゴリズムではありません。

以下の問題は、知りたい場合に備えて、私が解決しようとしているものです。

最初の行にある 2 桁の数字は N と M で、それぞれノードの数と有向エッジの数を表します。

2 行目からは、A と B の 2 つの数字の M セットが与えられます。これは、ノード A と B が接続されているが、A から B へのノードのみをトラバースできることを意味します。

入力.txt:

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

この場合の答えは、2>3>4>5>6>7>2 なので 6 です。

4

4 に答える 4

9

最長の基本サイクル（または回路）は、最長のサイクルよりも優れた用語だと思います。

とにかく、このpdfは役立つかもしれません：有向グラフのすべての基本回路を見つける

この1年前のスタックオーバーフローの質問には、関連する問題やアルゴリズムへのリンクも多数あります。 有向グラフですべてのサイクルを見つける

于 2011-01-09T19:47:15.967 に答える
4

確かに、ハミルトン閉路を多項式時間でこの問題に還元できることを示すことができるため、最終的にNP完全になります。グラフが有向か無向かに関係なく。

アルゴリズムに関する限り、問題を解決する簡単な方法は、バックトラックすることです---ノードi = 1からnで開始し、常に特定のノードiで開始するすべてのサイクルを探索します。これが完了したら、ノードiを削除し、ノードi+1から開始してグラフの残りの部分を続行します。DFSでノードの色付けなどを実行して、二度とアクセスしたくないノードと、この特定のパスのパスに沿ってアクセスしたノードを区別することができます。検出時間と同様に、ノードにタイムスタンプのようなものを配置することもできますが、この場合、ほとんどのノードは何度も検出されるため、ノードを検出するたびにこれらの時間を書き込む必要があります。上記の論文が役立つ可能性があり、これを確実に行う方法は他にもあります。

于 2012-05-09T10:00:28.153 に答える
0

別の投稿で、Python と networkX を使用して有向グラフ内のすべてのサイクルを簡単に見つける方法を説明する回答があります。有向グラフのすべてのサイクルを見つける

ソリューションは、有向グラフのすべてのサイクルを含むリストを出力します。

この出力を使用して、最長のサイクルを見つけることができます。以下に示します。

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)

答え:最長サイクルは ['3', '4', '5', '6', '7', '2'] で、長さは 6 です。

面白いと思ったら、元の回答にも賛成票を投じてください。これは多くの答えを伴う古い議論であり、新しい解決策を生み出すのに役立ちます.

于 2015-12-30T15:34:41.390 に答える
0

この問題は NP-Complete であり、そのための多項式時間アルゴリズムはありません。あなたの問題の大きさは？入力グラフにはいくつのノードがあるのでしょうか?

最長サイクル問題はハミルトニアン サイクル問題に還元されます: http://mathworld.wolfram.com/HamiltonianCycle.html

于 2011-10-14T07:23:39.180 に答える