木の構築

[アルゴリズム,木構造]

練習のための問題は 競技プログラミングの履歴、 木構造自体の説明については木構造。

木の構築

• Programing Problem: Construct a Tree Given Its Edges から
  • 辺だけ与えられた時の閉路のない木構造を構築する方法を学びましょう

  問題

• 以下のような辺が与えられる（※どちらが親のノードか指示されない）

edges = [[0, 6], [17, 5], [2, 7], [4, 14], [12, 9], [15, 5], [11, 1], [14, 8], [16, 6], [5, 1], [10, 7], [6, 10], [8, 2], [13, 1], [1, 12], [7, 1], [3, 2], [19, 12], [18, 19]]

• この中のどれかが木構造の頂点になると想定して、木を構築せよ
  • 以下、サンプル

{
  "9": {
    "12": {
      "1": {
        "7": {
          "10": {
            "6": {
              "0": {},
              "16": {}
            }
          },
          "2": {
            "8": {
              "14": {
                "4": {}
              }
            },
            "3": {}
          }
        },
        "11": {},
        "13": {},
        "5": {
          "17": {},
          "15": {}
        }
      },
      "19": {
        "18": {}
      }
    }
  }
}

  解法

• whonose氏の書いたコードが一番理解しやすい

root要素の取得

• それぞれのタプルの最初の要素を子、次の要素を親と仮に決める
• それぞれの集合(set)を作成する
• root要素はその差集合となる

edges = [
  [0, 6], [17, 5], [2, 7],
  [4, 14], [12, 9], [15, 5], [11, 1], [14, 8], [16, 6], [5, 1], [10, 7], [6, 10], [8, 2], [13, 1], [1, 12], [7, 1], [3, 2], [19, 12], [18, 19]
]

parent   = edges.map{|e| e.last}
children = edges.map{|e| e.first}
root     = parent - children

辺の集合を探索

• root要素を始点として深さ優先探索する

    until stack.empty? # スタックがなくなるまでループ
      n = stack.pop    # スタックから一番最近入れた要素をpop

      edges.each do |e|
        if e.last == n
          @tree[e.first] = {} if @tree[e.first].nil?
          @tree[n] = {} if @tree[n].nil?
          @tree[n][e.first] = @tree[e.first]
          stack << e.first
        end

      end
    end

ソース全体

# coding: utf-8
require 'json'

class Tree
  attr :tree, :root

  def initialize()
    @tree = {}
  end

  def make_tree(edges)
    # 仮親を決める
    parent   = edges.map{|e| e.last}
    children = edges.map{|e| e.first}
    @root    = (parent - children).first

    # root要素があるほうが親
    edges = edges.map{|e| e.reverse } unless parent.include?(@root)

    # 深さ優先探索
    stack = [@root]
    until stack.empty?
      n = stack.pop
      edges.each do |e|
        if e.last == n
          # キーがなければ空のハッシュを入れる
          @tree[e.first] = {} if @tree[e.first].nil?
          @tree[n] = {} if @tree[n].nil?
          # ネストしたハッシュを構築
          @tree[n][e.first] = @tree[e.first]
          stack << e.first
        end

      end
    end
    @tree = {root=>@tree[root]}
    @tree
  end
end

edges = [
  [0, 6], [17, 5], [2, 7],
  [4, 14], [12, 9], [15, 5],
  [11, 1], [14, 8], [16, 6],
  [5, 1], [10, 7], [6, 10],
  [8, 2], [13, 1], [1, 12],
  [7, 1], [3, 2], [19, 12],
  [18, 19]
]

tree = Tree.new
t = tree.make_tree(edges)

puts JSON.pretty_generate(t)