パッケージ library.graph

クラス LowestCommonAncestor

java.lang.Object

library.graph.LowestCommonAncestor

型パラメータ:

G - Graph, あるいはWeightedGraphクラスを入れる

public final class LowestCommonAncestor
extends Object

最小共通祖先を求めるクラス [注意] verifyをしていない

コンストラクタの概要

コンストラクタ

コンストラクタ	説明
LowestCommonAncestor(Graph g)	コンストラクタ

メソッドの概要

修飾子とタイプ	メソッド	説明
final int	climb(int u, int k)	頂点uからk個親に遡った頂点を返す
final int	dist(int u, int v)	頂点uと頂点vとのパスの辺の本数を返す
final int	query(int u, int v)	頂点uと頂点vとの最小共通祖先を求める

クラスから継承されたメソッド java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

コンストラクタの詳細

LowestCommonAncestor

public LowestCommonAncestor(Graph g)

コンストラクタ

パラメータ:

g - グラフ

メソッドの詳細

query

public final int query(int u,
 int v)

頂点uと頂点vとの最小共通祖先を求める

パラメータ:

u -

v -

climb

public final int climb(int u,
 int k)

頂点uからk個親に遡った頂点を返す

パラメータ:

u -

k -

戻り値:

頂点uからk個親に遡った頂点

dist

public final int dist(int u,
 int v)

頂点uと頂点vとのパスの辺の本数を返す

パラメータ:

u -

v -

戻り値:

頂点uと頂点vとのパスの辺の本数