Нахождение минимального связующего дерева из списка смежности, где список смежности находится в массиве строк с использованием алгоритма простых чисел - PullRequest
Новая
       20

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

5 голосов
/ 26 февраля 2012

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

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

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

Ответы [ 2 ]

6 голосов
/ 26 февраля 2012

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

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;
    }

}
2 голосов
/ 09 апреля 2012

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

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

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. Использование его подхода сделало бы вашу работу проще (поскольку - как он уже указывал - было бы ближе к вашему умственному представлению ) и даже более эффективным (я полагаю, не полагайтесь на это предположение;)) в противном случае вы выполняете много операций со строками. В названии, которое вы спросили по алгоритму Прима, но в своем реальном вопросе вы сказали или Прима или Крускала. Я пойду с Крускалом просто потому, что его алгоритм намного проще, и вы, кажется, принимаете оба.

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

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

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

Повторяйте как можно чаще:

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

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

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

Поиск в глубину

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

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

Теперь, если этот метод возвращает true, это ребро вызовет круг.

...