Python - Структура данных графика - Как реализовать поиск в ширину, чтобы правильно найти достижимые вершины - PullRequest
Новая
       34

Python - Структура данных графика - Как реализовать поиск в ширину, чтобы правильно найти достижимые вершины

1 голос
/ 11 мая 2011

В Python у меня есть класс Graph, в котором есть словарь объектов вершин. Каждый объект вершины имеет словарь ребер (который состоит из начального узла, конечного узла и веса ... представьте конец стрелки, указывающей на другой узел с присвоенным ему номером стоимости поездки).

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

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

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

1 Ответ

1 голос
/ 11 мая 2011

Ваш код слишком сложен.

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

from collections import deque

class fringe(object):
    def __init__(self, kind= 'stack'):
        f= deque()
        self._p= f.append if kind is 'stack' else f.appendleft
        self._f= f

    def __call__(self, item):
        self._p(item)
        return self

    def __iter__(self):
        while len(self._f):
            item= self._f.pop()
            yield item

    def __repr__(self):
        return self._f.__repr__().replace('deque', 'fringe')

def paths(G, start, terminal, F= fringe()):
    for node, path in F((start, [start])):
        for node in G[node]:
            if node is terminal:
                yield path+ [terminal]
            elif node not in path:
                F((node, path+ [node]))

, а тест: 

if __name__ == '__main__':
    a, b, c, d, e, f= 'A', 'B', 'C', 'D', 'E', 'F'
    G= {a: [b, c], b: [c, d], c: [d], d: [c], e: [f], f: [c]}
    print 'All paths from:', a, 'to:', d
    print 'BFS'
    for path in paths(G, a, d): print path
    print 'DFS'
    for path in paths(G, a, d, fringe('queue')): print path

run выдаст: 

All paths from: A to: D
BFS
['A', 'C', 'D']
['A', 'B', 'D']
['A', 'B', 'C', 'D']
DFS
['A', 'B', 'D']
['A', 'C', 'D']
['A', 'B', 'C', 'D']
...