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

… помогите решить задачу, ну или в каком месте копать? (гугл не помог)

Есть список граней ( 1, 2, 3, 4, 5, 6 )
Есть список вершин от граней ( (2, 6), (3, 7), (8, 2), (8, 3), (6, 9), (7, 9) ) (где индекс пары вершин соответствует индексу грани)

Задача: отсортировать грани по условию общих вершин. Если грань имеет общую вершину с проверяемой – добавляем в список.
к примеру:
грани (2, 6) и (6, 9) имеют общую вершину 6, в список (1)
грани (6, 9) и (7, 9) имеют общую вершину 9, в список (1, 5)
грани (7, 9) и (3, 7) имеют общую вершину 7, в список (1, 5, 6)
и т.д.

выход: ( 1, 5, 6, 2, 4, 3 )

как подобную проверку реализовать в коде?

Есть список вершин от граней ( (2, 6), (3, 7), (8, 2), (8, 3), (6, 9), (7, 9) )
судя по условию общие грани имеют элементы (2, 6) (8, 2) (6, 9)тогда в список уже должны добавлены быть 1 3 5 , затем (3, 7) (7, 9) это 2 и 6 потом (8, 2), (8, 3)
это еще добавляем 3 и 4 и наконец (6, 9), (7, 9) это 5 и 6
в итоге список получается 1 3 5 2 6 3 4 5 6. что то не очень понятна суть задания и результат

да, задание немного с путаницей. Сразу поправлюсь, не грани, а рёбра(edge).

Ну, а по теме, как подсказали, нужно смотреть в графы, а точнее в “обход в глубину”.
В данном случае, с этих наборов вершин должен получиться ориентированный граф-цикл что я пока не осилил…

upd: решение нашел тут http://python.su/forum/topic/27841/ )

Отредактировано KSN (Фев. 13, 2017 10:59:51)