有向木には根となる頂点が必要
まず下図のグラフは、有向木とは呼べないグラフの例である。
でももし無向グラフだったら木と呼べそうな形をしている。
「木の各辺を有向にしたもの」だから「有向木」と呼びたくなるが、いろいろググってみたところ、どうやら有向木には根から各頂点へのパスが存在しなければならないという暗黙のルールがあるらしいのだ。
上図のグラフは根になれる頂点がないため、有向木とは呼べない。
（上図のグラフは閉路がない有向グラフなので、DAGの一種ではある。）
一方、例えば下図のグラフなら、頂点４から出発して任意の頂点へ到達可能なので頂点４を根とする有向木と呼べる。
有向グラフにクラスカル法やプリム法は使えない
無向グラフの最小全域木を求めるアルゴリズムといえばクラスカル法やプリム法が有名である。
しかしこれらのアルゴリズムを有向グラフに使ってみても、結果は有向木にはならない（それどころか全域木にならないかもしれない）。
例えば下図のグラフでイメージしてみる。
上図のグラフに対してクラスカル法をやってみると、コスト1の辺⇒コスト3の辺⇒コスト6の辺と採用したあと、コスト7の辺を採用しようとする。しかしコスト7の辺を採用してしまうと、**頂点５に侵入する辺が２本存在してしまい、有向木にならなくなる。**クラスカル法を改造して「採用すると有向木にならなくなるような辺は採用せずスキップする」とすればうまくいくのかもしれないが、改造したらそれはもはやクラスカル法ではない。
次に、頂点１を根としてプリム法をやってみる。コスト3の辺⇒コスト6の辺⇒コスト7の辺⇒コスト8の辺と採用したところでアルゴリズムが終了する。いちおう有向木は得られたが、**合計コストが最小になっていない（コスト7の辺の代わりにコスト1の辺を使ったほうが合計コストは小さくなる）。**プリム法の性質上、コスト8の辺が邪魔でコスト1の辺に手が届かないのである。
では有向全域木を求めるにはどうしたらいいのかというと、Chu–Liu/Edmondsのアルゴリズムというものがあるらしい。
このアルゴリズムはまず、根以外の各頂点について「その頂点に侵入する辺の中でコストが最小のものを探す」という操作をする。探し出した辺の集合がもし木だったら、それが有向全域木。もし木になっていなかった（どこかに閉路があった）ら、ちょっとずつ集合の中身を変えて探索を続けていく。
面白そうなアルゴリズムなので今度自分も実装してみようかな。
参考にしたページ（一部）
- https://stackoverflow.com/questions/22478372/prims-algorithm-for-weighted-directed-graph
- https://www.geeksforgeeks.org/why-prims-and-kruskals-mst-algorithm-fails-for-directed-graph/
- https://ark4rk.hatenablog.com/entry/2017/09/15/011937
補足
- この記事に載せているグラフの画像は「generate DOT」というツールで作成したものである。このツール、とても便利。作者さんありがとうございます。
- 「有向木には根から各頂点へのパスが存在するという暗黙のルールがあるらしい」などと書いたが、暗黙のルールではなく、有向木という言葉にはちゃんとした数学的な定義があるのかもしれない。今度調べておきます。
今日はここまで。