Возникли проблемы при написании жадного алгоритма для раскраски вершин в графе - PullRequest
Новая
       57

Возникли проблемы при написании жадного алгоритма для раскраски вершин в графе

0 голосов
/ 17 октября 2019

Я считаю, что моя главная проблема в том, что я не знаю, как обновить словарь соседних цветов. Допустим, вершина окрашивается как 2, в этот момент словарь цветов не будет обновляться. В словаре просто останутся все значения, установленные как их значения по умолчанию 1. Мое решение, как правило, тоже плохо себя чувствует, поэтому любая помощь / советы приветствуются. 

def greedy(graph, vOrder):

  #graphOut represents the final coloring of vertices
  #colorDict represents each vertices current neighbor colors

  graphOut = {}
  colorDict = {}
  originalOrder = []

  # Records original order of graph for outputting the colored graph in original graph order later
  for z in graph:
    originalOrder.append(z)

  # Setting the order of the graph to the order of vOrder user input (will reset to original order for output later)
  print(graph)
  print()
  for x in vOrder:

    graph[x] = graph.pop(x)

  # Initializes all colors to 1
  for v in vOrder:
    graphOut[v] = 1

  # Dictionary that stores all current colors. Key is specific vertex, values are all neighbor colors
  for vertice in graph:
    colorDict[vertice] = []  
    for neighbor in graph[vertice]:
      colorDict[vertice].append(graphOut[neighbor])

  # (skip the first for greedy algorithm, default set is 1 and the first gets 1 no matter what)
  vert = iter(graphOut)
  next(vert)

  # Where the coloring happens The minimum color is 1, all colors default set to 1, so if a neighbor color is 1 the current color of the vertex will continue to increase until it is different than its neighbors color
  for vert in graphOut:
    while graphOut[x] in colorDict[x]:
      graphOut[x] += 1

  # Reset graphOut to original order of graph
  for x in originalOrder:
    graphOut[x] = graphOut.pop(x)

  print(graphOut)

пример ввода 

greedy({"A" : ["B"],"B" : ["A","C"],"C" : ["B","D"],"D" : ["C"]},["A","D","B","C"])

ожидаетсявывод 

{"A": 1, "B": 2, "C": 3, "D": 1}
...