プリューファー列から木を生成するアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:32 UTC 版)
「プリューファー列」の記事における「プリューファー列から木を生成するアルゴリズム」の解説
{ a 1 , a 2 , ⋯ a n } {\displaystyle \{a_{1},a_{2},\cdots a_{n}\}} を与えられたプリューファー列とする。生成される木は 1 {\displaystyle 1} から n + 2 {\displaystyle n+2} まで n + 2 {\displaystyle n+2} 個の頂点を持つ。すべての頂点について、列の中に出てくる回数に1を加えた値を次数として記録する。 Convert-Prüfer-to-Tree(a) 1 n ← length[a] 2 T ← a graph with n + 2 isolated nodes, numbered 1 to n + 2 3 degree ← an array of integers 4 for each node i in T do 5 degree[i] ← 1 6 for each value i in a do 7 degree[i] ← degree[i] + 1 次に、次数 d e g r e e j {\displaystyle degree_{j}} が 1 {\displaystyle 1} であり、かつ最小となるような j {\displaystyle j} を見つけて、木に辺 ( j , a i ) {\displaystyle (j,a_{i})} を追加する操作を繰り返す。 8 for each value i in a do 9 for each node j in T do10 if degree[j] = 1 then11 Insert edge[i, j] into T12 degree[i] ← degree[i] - 113 degree[j] ← degree[j] - 114 break すべての a i {\displaystyle a_{i}} について操作を終えた後、次数が1となる残った2つの頂点 u , v {\displaystyle u,v} について辺 ( u , v ) {\displaystyle (u,v)} を追加し、アルゴリズムは終了する。 15 u ← v ← 016 for each node i in T17 if degree[i] = 1 then18 if u = 0 then19 u ← i20 else21 v ← i22 break23 Insert edge[u, v] into T24 degree[u] ← degree[u] - 125 degree[v] ← degree[v] - 126 return T
※この「プリューファー列から木を生成するアルゴリズム」の解説は、「プリューファー列」の解説の一部です。
「プリューファー列から木を生成するアルゴリズム」を含む「プリューファー列」の記事については、「プリューファー列」の概要を参照ください。
- プリューファー列から木を生成するアルゴリズムのページへのリンク
