1

会社の組織図を作成するプログラムに取り組んでいます。私は頂点を階層化するための最長パスアルゴリズムについて読んでいますが、1つのことが私を悩ませています。私が行った読みは、グラフを下から上に階層化する必要があることを示唆しています。最初に、子のないノードを最下層に配置してから、上に向かっていきます。ただし、最長パスアルゴリズムでは、底が非常に広いグラフが作成されることも読みました。

親のいないノードから始めて、上から下に向かってグラフを作成してみようと思っていました。たぶんこれは一般的で、私はそれが使われているのを見たことがありませんが、私が見ない理由がこのアプローチを非現実的にしているのではないかと心配しています。足りないものはありますか？

4

1 に答える 1

1

最長パス アルゴリズムは、高さを最小化しますが、基本的に幅を無視します。グラフを下から上に重ねていき、グラフに多くのシンク (アウトディグリーがゼロの頂点) がある場合、下のレイヤーが広くなります。グラフを上から下に重ねて、多くのソース (次数が 0 の頂点) がある場合、広いトップ レイヤーが得られます。シンクの数とソースの数を比較すると、使用するバリアントを選択できます。ただし、それでも広い中間層が得られる場合があります。すべてのレイヤーの幅を減らす (最小化しない) には、 Coffman-Graham アルゴリズムのようなアルゴリズムを調べる必要があります。

于 2012-11-02T17:40:00.320 に答える