スパニングツリーを作成する方法

Question

サイクルを含むJavaで利用可能なすべてのアドレス形式の有向グラフを用意しています。私は上記のテンプレートに加えて、このグラフのスパンであるユーザーアドレスを保存します。私のグラフは以下のXMLから得られます：

<address> 
    <city start="true"> 
     <minicity /> 
     <street /> 
     <square /> 
    </city> 
    <minicity> 
     <street /> 
     <alley /> 
     <square /> 
    </minicity> 
    <street> 
     <street /> 
     <alley /> 
     <blibd /> 
    </street> 
    <square> 
     <street /> 
     <alley /> 
     <blibd /> 
    </square> 
    <alley final="true"> 
     <alley /> 
     <blibd /> 
     <plaque /> 
    </alley> 
    <blibd final="true"> 
     <alley /> 
     <blibd /> 
     <plaque /> 
    </blibd> 
    <plaque final="true"> 
     <stage /> 
     <unit /> 
    </plaque> 
    <stage final="true"> 
     <unit /> 
    </stage> 
    <unit final="true"> 
    </unit> 
</address> 

グラフの通りノードは、それ自身の上にサイクルがあります。

市：ストリート：Bストリート：Cの通り：D路地：

fの私の質問は次のとおりです。 格納するための最良の方法は何であるユーザアドレスのサンプルは次のようになります。ユーザーのアドレスグラフ？私は上記のテンプレートグラフを持っていて、このテンプレート内または別の構造の外にユーザーグラフを保存する方が良いかどうかを知りたがっています。

Answer 1

adjacency matrixは、グラフを表す標準的な方法です。あなたのケースでは、行列の各要素にノードカテゴリ（都市など）を追加することができます。

ユーザーのアドレスは、特定のアドレスの最も内側のノードへの別の参照を格納し、アドレスを構築するために市外へトレースすることによって導き出すことができます。

個人的には、都市、街路などのビジネスオブジェクトを作成して住所の構造を強化するという、一般的なグラフよりも構造化されたアプローチを選択することになります。例えば

public interface Residence { 
    int getNumber(); 
    Street getStreet(); 
} 

public interface Street { 
    City getCity(); 
} 

public interface City { 
    Country getAddress(); 
} 

居住地の住所を表示するには、単にオブジェクトグラフを表示するだけです。例えば

Residence r = ... 
System.err.println(String.format("%d %s %s %s", r.getNumber(), r.getStreet(), r.getStreet().getCity(), r.getStreet().getCity().getCountry()));