binary-tree - Dijkstra のアルゴリズム、バイナリ ツリーの深さ優先順を参照してください

Question

二分木を扱っていますが、二分木を深さ優先順にアクセスするためにエッジに重みを付ける方法を考えています。
最初にアクセスしたいノードにつながるエッジに割り当てる重みを減らす必要があることはわかっています。
しかし、ノードの深さとの関係はありますか?
乾杯。

Answer 1

これは学生の練習のように聞こえます。ダイクストラのアルゴリズムを使用して、最初に二分木の深さを検索することができます。実際、エッジとツリーの深さの間には次のような関係があります。

             A
          1      4
       B             E
     1   2         1   2
   C       D     F      G

上のツリーでは、文字はノードを表し、数字は加重エッジを表します。ダイクストラのアルゴリズムは、深さ優先順でこのツリーのノードを訪問します。この特定のケースでは、アルファベット順です。

Answer 2

ダイクストラ アルゴリズムは各頂点の先行オブジェクト間の最小値を計算するため、常にこのような BFS 動作が行われます。たとえば、最初に知っている頂点から開始しますA。pred なし、値は 0 に設定されます。その後継をすべて取得し、それぞれについて、すべての先行の距離と関連する値をテストします。それは私にとってBFSのような場所です。