1

ノード間のホップを表すペアのベクトルがありますが、これはサイクルがあるときに折りたたむ必要があります (サイクル内のホップ間の合計時間を 1 つとして表示するなど)。したがって、たとえば、パス A --> B --> C --> D --> B --> C --> D --> E は、サブパス B--> C --> D を 2 回トラバースします。私の構造では、次のようなものになります。

(A,B,1)(B,C,3)(C,D,2)(D,B,4)(B,C,5)(C,D,8)(D,E,6)

理想的には次のように減らします。

(A,B,1)(B,C,3+5)(C,D,2+8)(D,E,6)

D から B への 4 つ (ループバック エッジ時間) も格納して個別に集計し、B --> C --> D を要約して表示できるようにします (すべてのエッジ時間の集計とループバック時間の集計)。 D-->B インスタンスとループ回数のカウント)

これについてどうすればよいですか？

4

2 に答える 2

1

基本的に、パスを通過し、このような各エッジ ( (A, B), 1 ) を amapに格納し、検出されたすべてのノードを a に格納します。set

  • すでに検出されたノードとして宛先ポイントを持つエッジに遭遇するたびに、それがループバック エッジであることがわかります。

  • 同じエッジに遭遇するたびに、その値をmap

于 2012-06-25T23:52:44.507 に答える
1

suffix arrayまたはsuffix treeを使用します。トークン (この場合は (from, to) ) を生成し、それを Suffix Array または Suffix Tree に入れるだけです。その後、ペアを取得できます。シンプルだが効率的ではない方法：

トークンを生成し、このトークンストリームのすべてのサフィックスを生成します。それらを並べ替えます。次に、並べ替えられたリストに共通のすべてのサブシーケンスが互いに近くにあります（トークンストリームの長さ-トークンストリームのサフィックスの長さ=位置）たとえば、クイックソートで並べ替えを行うか、単にサフィックス配列の実装を探します。Suffix Arrays は、 O(n)およびO(n)空間で構築できます。そして、最大のペア/繰り返し(それはあなたが望むもの) を見つけることは、O(n+k) (n = トークン番号、k = リスト内のサイクル) で行うことができます。

おそらくこれが役立ちます。次に、次のようなトークンストリームを生成できます: ABCDBCDE

迅速で汚い解決策はここにあります

于 2012-06-25T19:24:14.937 に答える