Блог

Главная - Вопросы по программированию - Как этот код на Python представляет взвешенный ориентированный граф

Как этот код на Python представляет взвешенный ориентированный граф

#python #graph

#python #График

Вопрос:

Я пытаюсь выполнить некоторый hw с помощью алгоритма Дейкстры, но у меня возникают проблемы с визуализацией того, что этот ввод хотел бы видеть в виде графика. Код написан на python. Что это за график?

 example = [[(1, 1), (2, 2), (4, 3)], [(1, 3), (3, 4)], [(2, 3), (3, 5)], [(1, 4), (2, 5)], [], []]

Комментарии:

1. Вы можете представлять граф по-разному. Этот способ выглядит как список ребер.

2. Значит ли это, что 1 равен 1 длине из 2, что равно 2 длине из 4? @sashaaero

3. Это список списков кортежей. По сути, это не несет в себе большего значения, чем это. Чтобы убедиться, вам пришлось бы поговорить с человеком, который это написал, или прочитать какой-нибудь код, который работает с ним, или прочитать документацию об этом и т.д. Насколько нам известно, это могут быть лотерейные номера. Существует много возможных значений.

4. @rmcknst2 этот список действительно немного странный, список списков кортежей. Первоначально (x, y) означает, что узел x имеет ребро к y . Возможно, каждый внутренний список означает вес ребра, я действительно не могу знать.

5. Если у вас действительно нет другой информации, вы можете принять индекс списка за вес (начинается с 1), а кортеж за ребро, но ребро (1, 1) с некоторым весом кажется странным.

Ответ №1:

Я предполагаю, что i -й элемент списка example представляет все ребра с весом i . Вы можете изменить структуру данных графика на что-то другое, например, dict, где каждый ключ является узлом, а его значение — список узлов, к которым он подключен, с соответствующими весами.

 example = [[(1, 1), (2, 2), (4, 3)], [(1, 3), (3, 4)], [(2, 3), (3, 5)], [(1, 4), (2, 5)], [], []]

nodes = list(set([i for k in example for j in k for i in j ]))
arcs = [(i,example.index(j)) for j in example for i in j]

example_graph = {str(i):[] for i in nodes}
for i in arcs:
    example_graph[str(i[0][0])]  = [(i[1],str(i[0][1]))]

print example_graph

Это дает

 example_graph = {'1': [(0, '1'), (1, '3'), (3, '4')],
                 '2': [(0, '2'), (2, '3'), (3, '5')],
                 '3': [(1, '4'), (2, '5')],
                 '4': [(0, '3')], 
                 '5': []}

Теперь вы можете реализовать алгоритм Дейкстры, вот пример, который я нашел :

 from heapq import heappop,heappush    

def dijkstra(s, t, neighbors):
    M = set()
    d = {s: 0}
    p = {}
    new = [(0, s)] 
    while new != []:
        dx, x = heappop(new)
        if x in M:
            continue
        M.add(x)
        for w, y in neighbors(x):
            if y in M:
                continue
            dy = dx   w
            if y not in d or d[y] > dy:
                d[y] = dy
                heappush(new, (dy, y))
                p[y] = x
    path = [t]
    x = t
    while x != s:
        x = p[x]
        path.insert(0, x)
    return d[t], path

def neighbors(s,graph=example_graph):
    return graph[s]

Например, dijkstra('1', '4', neighbors) возвращает (2, ['1', '3', '4'])