トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

木の構築

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

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

木の構築

  問題

  • 以下のような辺が与えられる(※どちらが親のノードか指示されない)
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)
お名前: コメント: