Свяжите все точки, по крайней мере, еще один на графике

Question

У меня есть проблема, когда мне нужно, учитывая, что граф находит минимальное количество ребер, необходимых для каждой вершины, связанной, по крайней мере, с одной. Чтобы решить эту проблему, я попытался сделать этот метод в псевдокоде:

getEdgesCount(listOfPoints): 
linkedPoints = set() 
edgeCount = 0 

for point in listOfPoints: 
    alternative = None 
    best = None 
    foundEdge = false 
    if point not in linkedPoints: 
     for secondPoint in listOfPoints: 
      if secondPoint != point: 
       if canLink(secondPoint,point): 
        if secondPoint in linkedPoints: 
         alternative = secondPoint 
         foundEdge = true 
        else: 
         best = secondPoint 
         foundEdge = true 
         break 
     if foundEdge: 
      linkedPoints.push(point) 
      edgeCount++ 
      if best != None: 
       linkedPoints.push(best) 
      else: 
       linkedPoints.push(alternative) 
return edgeCount 

Но этот код, кажется, не всегда дают правильный ответ, то есть он рассчитывает на многое края, поэтому я прошу вас, что неправильно в этом коде ?

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

Answer 1

Это проблема обхода графа, и вы можете выбрать любой аромат, который вам нравится:

• BFS: http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
• DFS: http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Очевидно, что если граф состоит из несвязанных компонентов, то нет решения. Это можно легко проверить с помощью описанного выше алгоритма DFS.

Answer 2

Давайте посмотрим на конфигурацию, и как он не в вашем случае:

• возможностью подключения к C
• B С возможностью подключения к D
• возможностью подключения к B (но не требуется)

Ваш алгоритм

1. подключить ап первый
2. находка C до d B только для A возможностью подключения
3. находка D быть только возможностью подключения к B

Так что вам нужно 3 ребра вместо 2. Вы должны найти наборы точек (С возможностью подключения как A , B, C, D) и сначала соединяйте точки с наименьшими возможностями. В нашем примере C-A-B-D - такой набор. C имеет только одну возможность, поэтому мы соединяем C-A, оставшийся B-D.

Лучше, но все еще жадные и, таким образом, не оптимальный алгоритм будет:

1. Искать одинокую точку с наименьшим количеством возможных соединений.
2. В набор возможных партнеров возьмите еще один вариант с наименьшими возможными соединениями и подключите его к первому.
3. Повторите 1. до тех пор, пока не будут выполнены все соединения между попарно одиночными точками.
4. Сделайте то же самое с соединениями одиночных точек с не одинокими точками.

Пример (треугольники на концах линии):

• Возможные соединения:
  • А к В
  • В к С
  • от А до D
  • D к B
  • C по E
  • Е к F
  • F к C
• Число возможных соединений (отсортированных)
  • А: 2
  • D: 2
  • Е: 2
  • F: 2
  • B: 3
  • C: 3
• А имеет только два возможных соединений (AB или AD)
  • В имеет 3 и D только 2 => подключить AD
• Количество оставшихся возможных соединений оставшихся точек
  • Б: 1
  • Е: 2
  • F: 2
  • С: 3
• В имеет только 1 возможную связь => подключить BC
• Количество оставшихся возможных соединений оставшихся точек
  • Е: 1
  • F: 1
• Е имеет только 1 возможное соединение => подключение EF
• Решено

Но это далеко не самый сложный случай. Проблема не может быть оптимальной решена с помощью greedy algorithm. Если вы, например, подумайте о двух возможных пятиугольниках (вместо треугольников), соединенных одним краем, вы обнаружите, что соединение любой пары с наименьшим количеством возможных соединений все равно не сможет найти оптимальное решение. Корпус пентагона можно решить с помощью 5 ребер, но только если вы начнете с правильной пары.

Удачи и получайте удовольствие.