Ctrl →

solo.test88 · Авг. 6, 2016 23:38:23

 graph = {
1: [2, 3],
2: [4]
}

Имеется ориентированный граф Граф 1 и нужно вывести вершины в консоли:
1
2
4
3

Отредактировано solo.test88 (Авг. 6, 2016 23:40:37)

py.user.next · Авг. 7, 2016 03:36:53

  
>>> def walk_graph(tree, node):
...     yield node
...     if node in tree:
...         for i in tree[node]:
...             for j in walk_graph(tree, i):
...                 yield j
... 
>>> graph = {
...     1: [2, 3],
...     2: [4]
... }
>>> 
>>> tuple(walk_graph(graph, 1))
(1, 2, 4, 3)
>>>

doza_and · Авг. 7, 2016 10:35:17

Зря вы так. Гражданин даже вопрос не сформулировал.

Скажем так
Вот это короче.

 >>> set(reduce(add,graph.values())+graph.keys())
set([1, 2, 3, 4])

Но это для двушки, и не хватает одной строчки.

py.user.next · Авг. 7, 2016 11:39:13

doza_and
Вот это короче.
 set([1, 2, 3, 4])

Выводится не то. Во-первых, это множество, у которого нет порядка, а во-вторых, там нужно проходить в глубину (после двойки нужно выводить потомка двойки - четвёрку).

Отредактировано py.user.next (Авг. 7, 2016 11:40:59)

doza_and · Авг. 7, 2016 12:25:53

py.user.next
Выводится не то. ….. там нужно проходить в глубину

Где это написано? Автор просил дать все вершины. Он их получил.

solo.test88 · Авг. 7, 2016 14:19:52

Супер! Большое спасибо Всем за помощь и оперативность))

py.user.next · Авг. 7, 2016 14:41:14

doza_and
Где это написано?

Прямо у него в первом сообщении.

solo.test88
и нужно вывести вершины в консоли:
1
2
4
3

А вот сам граф, из которого понятно, почему именно так выводятся они.

doza_and · Авг. 7, 2016 14:54:24

Явного требования в спецификации нет.

py.user.next · Авг. 7, 2016 15:05:51

doza_and
Явного требования в спецификации нет.

Графы обычно выводятся вполне определённо, поэтому было бы странным выводить просто какое-то неупорядоченное множество вершин. Мало того, у ориентированного графа есть понятие корня, поэтому ты не можешь просто начать выводить его весь с любой вершины, так как из некоторых вершин могут быть недостижимы какие-то вершины, тогда как от корня достижима любая вершина.

Отредактировано py.user.next (Авг. 7, 2016 15:06:29)

solo.test88 · Авг. 7, 2016 17:33:56

py.user.next
Тут возникла следующая проблема, если использовать данный граф:

 graph = {
    1: [2, 3],
    2: [3, 4],
    4: [1]
}

то при запуске с первой вершины walk_graph(graph, 1) возникает рекурсивная ошибка: RecursionError: maximum recursion depth exceeded.

Отредактировано solo.test88 (Авг. 7, 2016 17:34:26)

Python-сообщество

Уведомления

#1 Авг. 6, 2016 23:38:23

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

#2 Авг. 7, 2016 03:36:53

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

#3 Авг. 7, 2016 10:35:17

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

#4 Авг. 7, 2016 11:39:13

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

#5 Авг. 7, 2016 12:25:53

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

#6 Авг. 7, 2016 14:19:52

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

#7 Авг. 7, 2016 14:41:14

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

#8 Авг. 7, 2016 14:54:24

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

#9 Авг. 7, 2016 15:05:51

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

#10 Авг. 7, 2016 17:33:56

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

Board footer