Нахождение минимального охватавания дерева из списка смежности, где список смежных соседних находится в строковом массиве с использованием алгоритма Prims.

StackOverflow https://stackoverflow.com/questions/9449967

Вопрос

Так что мне нужна помощь, подойдя к способу, чтобы найти минимальное охваченное дерево. Предположим, у меня есть мой граф в виде списка смежности: 

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
.

Первая буква говорит, какой узел вы смотрите, и номер рассказывает, сколько подключений к любому другому узлу существуют.Например, имеет два соединения - один каждый до B и I. После этого номер, который следует за буквами, просто рассказывают вес края.B имеет вес 12, и у меня вес 25. Итак, я изначально планировал представить всю целую вещь как строковый массив называется Graph[8].Каждая строка будет другой слот в массиве.У меня есть трудности выяснить, как выполнить это с помощью алгоритма Prims или Kruskalls.

Это было полезно?

Решение

Предположим, у меня есть мое дерево в виде списка смежности

Важно (для вашего понимания) Обратите внимание, что у вас есть подключенный график в этом виде списка смежности, но я думаю, что это было просто опечатка. Я предложу это как редактировать, но я просто хочу, чтобы вы знали об этом. Тот факт, что это график, а не дерево, можно увидеть из этих линий: 

A 2 B 12 I 25
B 3 C 10 H 40 I 8
.

Здесь у вас есть круг уже в A-B-I: 

     A
  12/_\25
   B 8 I
.

Наличие круга по определению означает, что он не может быть деревом! Есть еще одна вещь, которую можно увидеть с того, как я представил этот подграф: Края имеют вес, а не узлы.

Теперь давайте посмотрим на ваш приведенный пример: 

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
.

Прежде всего, мы можем видеть, что этот список смежностей является либо неправильным, либо уже оптимизированным для ваших нужд. Это может (например) быть видно из строк 

E 2 F 60 G 38
F 0
.

Первая строка здесь показывает край от e до f, но вторая строка говорит, что F имеет степень 0, но степень определяется помимом, инцидентом к нему!

Это то, что будет выглядеть список смежний, если бы он был «полным»: 

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35
.

Мы можем видеть много избыточности, потому что каждый край встречается дважды, поэтому ваш «оптимизированный» список соседних лучше устраивает ваши потребности - будет ли этот «полный» пример, который будет делать много бесполезных чеков. Тем не менее, вы должны только полагаться на это, если вы можете быть уверены, что все данные, указанные для вашего кода, уже «оптимизированы» (или, скорее в этом формате)! Я возьму это как данное отныне.

Давайте поговорим о своей структуре данных. Вы, конечно, могут использовать ваш предложенный массив строк, но, честно говоря, я бы предпочел рекомендовать что-то вроде @ предложенную структуру данных Amirafghani. Использование его подхода сделает вашу работу проще (как она - как он уже указал - было бы ближе к вашему умственному представлению ) и еще более эффективно (я думаю, не полагаюсь на это догада;) ) Как вы будете делать много операций на строках в противном случае. В названии вы спросили после алгоритма Прими, но в вашем реальном вопросе вы сказали либо Prim's или Kruskal's. Я пойду с Крускалом просто потому, что его алгоритм проще, и вы, кажется, принимаете оба.

Алгоритм Крускала

алгоритм Крускала довольно прост, оно в основном:

    .
  • Начните с каждого узла, но нет ребер

    Повторите следующую как можно чаще:

      .
    • Из всех неиспользуемых / неиспользованных краев выбирают один с наименьшим весом (если есть более одного: просто выберите один из них)
    • Проверьте, приведет ли этот край, приведет к этому краю, если он делает, отметьте его как выбрано и «отказаться».
    • Если это не приведет к кругу, используйте его и пометите его как используемые / выбранные.

      Это все. Это действительно так просто. Однако я хотел бы упомянуть одну вещь в этот момент, я думаю, что он лучше всего подходит: в целом нет «минимального охватавания дерева», но «минимальное охваченное дерево», как может быть много, поэтому ваши результаты могут отличаться!

      Вернуться к своей структуре данных! Теперь вы можете понять, почему это будет плохая идея использовать массив строк в качестве структуры данных. Вы бы повторяли много операций на струнах (например, проверка веса каждого края) и em> strings неизменяются , это означает, что вы не можете просто «выбрасывать» одно из краев или Отметьте один из ребер любым способом. Используя другой подход, вы могли бы просто установить вес на -1 или даже удалить запись для края!

      Первый поиск глубины

      Из того, что я видел, я думаю, ваша главная проблема решает, приведет ли крае или нет, верно? Чтобы решить это, вам, вероятно, придется вызвать алгоритм поиска на глубину и использовать его возвращаемое значение. Основная идея такова: начните с одного из узлов (я назову этот узел корневой)

И попробуйте найти путь к узлу на другом конце выбранного края (я позвоню на этот узел целевой узел).(конечно, на графике, который еще не имеет этого края)
    .
  • Выберите один безвизненный край, инцидент для вашего root
  • Отметьте этот выбранный край, как посещено (или что-то в этом роде, что бы вы ни понравились)
  • повторить последние два шага для узла на другой стороне посещаемого края
  • всякий раз, когда нет никаких невизимых ребер, вернитесь на один край
  • Если вы вернулись в ваш root, и нет никаких безвизгодных ребер, инцидент по этому оставку, вы закончите.вернуть false.
  • Если вы в любой момент посетите свой целевой узел, вы закончите.вернуть правда.

    Теперь, если этот метод возвращает true, этот край приведет к окружности.

Другие советы

Это не прямой ответ на ваш вопрос.Почему бы не создать структуру данных, которая более близко соответствует вашим Mental Model и создать оттуда? 

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}
.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top