問題タブ [cyclic-graph]

私の質問に対する答えは明白かもしれません。私はその明白な答えを紙の上で知っています。つまり、いくつかの例に関して言えば、Lowest Common Ancestor アルゴリズムを実行するためのループが許可されていない理由は理解できますが、DAG での LCA のソリューションについて書かれた論文を理解するのに問題があります。そして、ソリューションのどの部分が巡回グラフでの使用を妨げている..

私が知りたいこと、およびお知らせいただけるとありがたいこと:

• DAG の LCA 問題に対する解決策の 1 つを説明できますか?
• どのステップにサイクルの問題があり、その理由を特定できますか?

私の問題では、LCAを見つけるためのノードのペアが1つのループ内にないため、それを解決する方法があると思います..

前もって感謝します

ソリューションの実装方法について多少混乱しているコーディング演習に取り組んでいます。

JavaDoc によると、この EmployeeManager インターフェイスを実装する必要があります。従業員データは、他のリクエストとは別のスレッドで到着すると想定します。getSalary() は一定時間 O(n) で実行されることに注意してください。実行時間は、従業員または部門の数によって変化してはなりません。

質問:

1. これはどのような問題ですか？

2. Employee クラスと Department クラスを POJO として作成する必要がありますか? その中には何が含まれますか? スレッドセーフにするためにランナブルを実装する必要がありますか?

3. これにはどのようなタイプのデータ構造が必要ですか?

私のデータ構造とCSのものは本当に錆びているので、フィードバックをいただければ幸いです。

Rust で巡回リンク データ構造を実装しようとしています。私Nodeの s は次のように定義されています。

私はこのような最小限の構造を構築しようとしています (より良い生涯可視性のための余分な括弧):

link2これは機能しますが、プレースホルダーを「サイクルを閉じる」への参照に置き換える方法がわかりません。link1私はこれを試しましたが、上記の行を借用した に割り当てることができず、link2まだ によって参照されている間に範囲外になるため、機能しませんlink1:

sを使用してこれらのライフタイムの問題を回避しようとすることもできますRcが、それは Rust のランタイム コストがゼロのライフタイム管理の目的に反するように思えます。

すべてのノードを に入れ、それへのVec直接参照のみを取得する別の試みも機能しませんでした:

ノードをミュータブルに借用せずにノードを変更することはできませんが、それらはすべてすでにイミュータブルに借用されているためです。

たとえば、私が試したような純粋な参照を使用して、実行時のオーバーヘッドなしで循環リンクを使用してそのような構造を作成する方法はありますか? Vecすべてのノードの所有権を保持するバッキングのように、追加のメモリ コストは問題ありません。