широта первый поиск/глубина первого поиска или режиссерский график?

Question

Я уже некоторое время борется с этим. задано множество узлов:

nodes = { ('A','B'), 
      ('B','C'), 
      ('C','D'), 
      ('C','E'), 
      ('B','E'), 
      ('C','F') } 

, что является лучшим способом для достижения следующего:

      A 
          | 
          B 
       _________|_________ 
       |     | 
       C     E 
      _____|_____    | 
      | |  |   C 
      D E  F  ____|____ 
           |  | 
           D  F 

, где я могу видеть, что:

the routes from A -> B: 
A -> B 
the routes from A -> C: 
A -> B -> C 
A -> B -> E -> C 
the routes from A -> D: 
A -> B -> C -> D 
A -> B -> E -> C -> D 

etc... 

Моя причина для этого, является потому что я хочу понять, как это сделать.

Я знаю, что BFS находит самый быстрый маршрут, (я думаю, я мог бы использовать что-то подобное в функции получить ребенок)

, но я не знаю, лучший путь к петле/рекурсивно работать над графиком. Должен ли я использовать словарь и работать с ключом/vals или списком. Или устанавливает ...

def make_graph(nodes): 
    d = dict() 
    for (x,y,*z) in nodes: 
     if x not in d: d[x] = set() 
     if y not in d: d[y] = set() 
     d[x].add(y) 
     d[y].add(x) 
    return d 

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

def display_graph(nodes): 
    for (key,val) in make_graph(nodes).items(): 
     print(key, val) 

# A {'B'} 
# C {'B', 'E', 'D', 'F'} 
# B {'A', 'C', 'E'} 
# E {'C', 'B'} 
# D {'C'} 
# F {'C'} 

GetChildren функция находит все возможные конечные точки для корневого узла:

def getchildren(noderoot,graph): 
    previousnodes, nextnodes = set(), set() 
    currentnode = noderoot 
    while True: 
     previousnodes.add(currentnode) 
     nextnodes.update(graph[currentnode] - previousnodes) 
     try: 
      currentnode = nextnodes.pop() 
     except KeyError: break 
    return (noderoot, previousnodes - set(noderoot)) 

В этом случае A:

print(getchildren('A', make_graph(nodes))) 

# ('A', {'C', 'B', 'E', 'D', 'F'}) 

Answer 1

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

Сначала вы должны думать о свойствах вашего графика, такие как циклический/ациклические, режиссер/неориентированный, и т.д ..

Затем вам нужно выбрать способ решить вашу проблему соответственно. например если это ациклический, неориентированный и связанный граф, то вы можете представить график как tree и использовать BFS или DFS для его перемещения.

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

Answer 2

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

Answer 3

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

Для базового ориентированного графика словарь имеет смысл. Просто сохраните родительский: список детей.

nodes = [ ('A','B'), 
      ('B','C'), 
      ('C','D'), 
      ('C','E'), 
      ('B','E'), 
      ('C','F') ] 

from collections import defaultdict 
d = defaultdict(list) 
for node in nodes: 
    d[node[0]].append(node[1]) 

Нахождение всех достижимых детей из любого корневого узла проста:

def getchildren(root, graph, path=[]): 
    path = path + [root] 
    for child in graph[root]: 
     if child not in path: #accounts for cycles 
      path=getchildren(child, graph, path) 
    return path 

При вызове:

>>> print getchildren('A',d) 
['A', 'B', 'C', 'D', 'E', 'F'] 
>>> print getchildren('C',d) 
['C', 'D', 'E', 'F'] 

Answer 4

Спасибо всем, проблема решена. Функция, которую мне нужно было написать, была следующей.

def trace_graph(k, graph): 
    """ takes a graph and returns a list of lists showing all possible routes from k """ 
    paths = [[k,v] for v in graph[k]] 
    for path in paths: 
     xs = path[:-1] 
     x = path[-1] 
     for v in graph[x]: 
      if v not in xs and path + [v] not in paths: 
       paths.append(path + [v]) 
    paths.sort() 
    return paths 


for path in trace_graph('A', make_graph(nodes)): 
    print(path) 


['A', 'B'] 
['A', 'B', 'C'] 
['A', 'B', 'C', 'D'] 
['A', 'B', 'C', 'E'] 
['A', 'B', 'C', 'F'] 
['A', 'B', 'E'] 
['A', 'B', 'E', 'C'] 
['A', 'B', 'E', 'C', 'D'] 
['A', 'B', 'E', 'C', 'F']