木の頂点間距離と直径について【競技プログラミング】

はじめに（木とは何か？）

• グラフ理論は少しかじって、投稿もいくつか（重み最小経路、ダイクストラ法の高速化、ワーシャルフロイド法･経路情報）書いたけど、もっと基本的な「木」についてよく分かってなかったのでまとめてみた。
• まず、「木」も含む概念であるグラフ理論では、頂点と辺を結んだ下記のような関係を扱う
  
• これに対して、木は、頂点数「N」に対して、辺の数は「N-1」となり、全ての頂点は繋がっている。
• 上記のグラフ(頂点6，辺7)の辺を2本削って、木(全ての頂点が繋がっている)にすると下記の様になる。
  
• 辺「2-3」と辺「1−5」を削って木にしたが、木では、全ての頂点間の経路は一意に決まる。元のグラフでは経路「1〜6」について、同じ点を2度通らないという縛りを設けても、「1−5−4−6」「1-5-2-3-4-6」「1-2-3-4-6」「1-2-5-4-6」の4つあったが、木にした後は、「1-2-5-4-6」のみとなる。
• ちなみに、グラフＴが木であることは、下記と同義。
  • T に閉路はなく、 n − 1 本の辺を持つ
  • T は連結で、 n − 1 本の辺を持つ
  • T は連結で、すべての辺は橋である
  • T の任意の2点を結ぶ道がちょうど1つある
  • T に閉路はないが、新しい辺をつけ加えると閉路が必ず1つできる
    ※ 閉路とは、グラフ中のループ(輪っか)となっている部分
    ※ 橋とは、グラフから取り除くと、グラフが連結で無くなる辺のこと
    ※ 道とは、頂点と頂点の間の経路のこと

木と木構造

• 木構造とは、グラフ理論の木の形を利用する、データ構造のことであり、グラフ理論の木の話をする際には、木構造の用語が混ざると必要以上の情報が入り込んでしまうので気を付ける。
• 木構造では、以下のように、ある頂点を「根(ルート)」と名付け、頂点間の関係に名前が付けられる、各頂点には値が格納される。そして、辺に重みは存在しない。木構造の種類(順序木、二分木、完全二分木、等)については、ITmediaのコーディングに役立つ！ アルゴリズムの基本（2）
  
• これに対して、「木」では根の設定は必須ではなく、辺には重みがある。また、「木構造」には、「高さ（根から最下層の葉までの辺の数）」があるが、「木」では、高さがない代わりに、「直径」の概念がある。
• 直径とは「木」の各頂点間の距離のうち最大の距離のこと。例えば、下の「木」で、全ての辺の重みを1とすれば、1〜6の距離4が直径となる。もしここで、辺「3−4」のみ重み10とした場合、1〜3の距離13が直径となる。
  

木の頂点間の距離

• さて、まずは、ある頂点aから、別の各頂点までの距離を測ってみようと思う。
• そんなの、ダイクストラ法で既にやったよ！と思うじゃん？　でも、ダイクストラ法を使わないで解く方がシンプルだから、そっちを使うね。
• そもそも、2点間の距離でダイクストラ法を使ったのは、下のグラフみたいに、「木」じゃなかったからなんだよね。つまり、2点間の経路が複数あるケースが存在するということ。例えば、1〜2について、「1-2」の他にも「1-3-2」等がある。
  
• これに対して、「木」においては、2頂点間の経路は常に一つだから、もっと簡単に距離を計算できる。例えば、「はじめに」で出した「木」について、3-4の辺のみ重さ10として、残りの辺の重みを1として表現するとこんな感じ。

6 1 // 頂点の数6,距離測定のスタート地点1
1 2 1
2 5 1
4 5 1
3 4 10
4 6 1

• 上記より、各頂点への距離を下記の形式で出力することとする。

1 0 // 頂点1から頂点1への距離だから、必ず0になる。
2 ?? // 頂点1から頂点2への距離が??
3 ??
4 ??
5 ??
6 ??

• 上記のような出力をするためのコードは下記の通り

let (N,S) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1]-1)}[0]

var gs = [[(Int,Int)]](repeating:[],count:N)
for _ in 0..<(N-1) {
    let (a,b,w) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1,$0[2])}[0]
    gs[a] += [(b,w)]
    gs[b] += [(a,w)]
}

var ds = [Int](repeating:-1,count:N) // 各頂点への距離を格納する

// 再帰関数rf (recursive function)
func rf(_ d:Int,_ n:Int){ // 頂点nに到達するまでの距離をdとして、配列dsに記録する
    ds[n] = d
    for (next_n,w) in gs[n] {
        if ds[next_n] == -1 { // 通過後の頂点への逆走を防ぐ
            rf(d + w,next_n)
        }
    }
}

rf(0,S) // スタート地点Sまでの距離は当然0

for (i,d) in ds.enumerated() {
    print(i+1,d)
}

• 結果は次のとおり。うむ、上手くいった様子。ちなみに、上記コードは、過去の知見を元に自分の発想だけで書いたので、これが通常の方法かどうか分からない。自分的には、各頂点への距離を格納する配列dsを逆走防止にも活用している点がオシャレな気がするんだけど、どうなんだろ。

1 0
2 1
3 13
4 3
5 2
6 4

木の直径

• 「木」の直径(最大の頂点間距離)の求め方は簡単。
  • 最初に、任意の点からの最長距離頂点を探す。
  • 例えば、頂点4から最も遠いのは、頂点3だった。

1 3
2 2
3 10 // 最長距離頂点 ⇒ 頂点3
4 0 // 任意のスタート地点
5 1
6 1

• • 次に、頂点3からの最長距離を算出する。
  • 頂点3をスタート地点とすると､以下の結果であり、直径は13と分かる。

1 13 // 最長距離は13 ⇒　つまり、木の直径は13
2 12
3 0
4 10
5 11
6 11

競技プログラミングでの活用

• そもそも、「木」を学習しようと思った切掛の問題がこれ。
  
• 問題文より、この都市と道路は「木」であることが分かる。1本の辺を追加して閉路をつくり、その閉路を最長にすれば良いので、この問題の解は、「木」の直径を求めて、1(＝追加する道路の重み)を追加したものとなる。
• 入力例

10 // 頂点の数
1 2 // 辺1：頂点1-頂点2 重み1
1 3
2 4
4 5
4 6
3 7
7 8
8 9
8 10

• 前記のコードをイジって、本問用にしたのが、次のコード

let N = Int(readLine()!)!

var gs = [[Int]](repeating:[],count:N)
for _ in 0..<(N-1) {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    gs[a] += [b]
    gs[b] += [a]
}

let d0 = [Int](repeating:-1,count:N) // 各頂点への距離を格納する
var ds = d0 // 二回処理するため、d0を残しておく

// 再帰関数rf (recursive function)
func rf(_ d:Int,_ n:Int){ // 頂点nに到達するまでの距離をdとして、配列dsに記録する
    ds[n] = d
    for (next_n) in gs[n] {
        if ds[next_n] == -1 { // 通過後の頂点への逆走を防ぐ
            rf(d + 1,next_n) // 辺の重みは全て1
        }
    }
}

rf(0,0) // 最初の任意の頂点を0とした

// 頂点0からの最長距離となる頂点vのindexを取得
let v_max = ds.index(of:ds.max()!)! //maxメソッドもindexもオプショナル値を持つため、強制解除

ds = d0 // リセット
rf(0,v_max)

// 「直径+1」を出力
print(ds.max()! + 1)

• よし、出力も8で正解だった!

さいごに

• 過去の自分の学習を振り返ると、何か、歪だと気付くね。
• なんで、「木」の直径より先にダイクストラ法とか学習してんだろ...効率が悪すぎる...
• アルゴリズムを一通りマスターしたら、アルゴリズムの講師にでもなろうかな。効率悪い学習をしてるからこそ、人に教えるときは、効率のよい進め方が出来そうな気もするね。