Как создать остовное дерево

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

Матрица смежности - это стандартный способ представления графа. В вашем случае каждый элемент матрицы может быть дополнен категорией узла (город и т. Д.).

Адрес пользователя можно получить, сохранив отдельную ссылку на самый внутренний узел данного адреса и проследив его до уровня города, чтобы построить адрес.

Лично я, вероятно, выбрал бы более структурированный подход, чем общий граф, создавая бизнес-объекты, такие как Город, Улица и т. Д., И, следовательно, применяя структуру адреса; например,

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()));