グラフ内のすべての接続コンポーネントをトラバースする必要があります。 グラフのパスは、このような配列に格納されている:ここ配列の配列を各配列に含まれる要素で並べ替えます。
var paths = [
[5,6],
[1,2],
[4,7,5,6],
[6]
]
iはpaths[2]=[4,7,5,6]
が順番にpaths[3]=[6]
から依存paths[0]=[5,6]
から依存していることを見ます。
今、私は再帰的に他のものに含まれているものをチェックするためにすべてのパスをトラバースする必要があり、最初に他のものを解決するのに役立つものを処理します。 :
例:
process [6]
process [5,6]
process [4,7,5,6]
process [1,2]
ための要素を大量に、私は再帰を使用しないでしょう。 他のすべての配列に含まれる1つの配列の要素によって、この配列のリストをソートする方法はありますか?
編集:私は、これは次のように構成される各パスに重みを割り当てることによって解決することができる 考える:このノードが他のパスに含まれている回数を乗じ、各パスに含まれるノードの 和を、次にパスを並べ替えます長さの昇順と重量の降順で - しかし、これは私の推測だけです...
'大量の要素のため、私は再帰を使わないほうがいいでしょう。'関数が最大スタックサイズに達することが懸念される場合、その周りに方法があります。これは「独自のTCOをかける」のようなものですが、これは非常に効果的です(こちらは良い記事です)(http://www.integralist.co.uk/posts/js-recursion.html)。とにかく、 '[5,6]'には '[6]'が含まれていると考えて正しいのでしょうか?本質的に、より大きい配列だけがより小さい配列を含むであろうが、 '[5,6]'に_ [4,7,5,6]の部分が含まれているケースではない? – vlaz
@ Vld:あなたが言及した記事をちょうど昨日読んだ、私はそれを消化する途中であることを認めなければならない...ポイントまで:彼らはまた、長さで並べ替えることができますが、いくつかのより複雑なグラフでは成功しません。 – deblocker
あなたのケースで賢明な比較作業をペアにしませんか? 'n 'がパスの数であるならば' O(n * n) '時間がかかるでしょう(パス長がいくつかの最大長' kよりも短いと仮定します) –