#python #graph #depth-first-search #traversal
#питон #График #поиск в первую очередь по глубине #обход
Вопрос:
У меня есть список узлов, упорядоченных по метке времени. Каждый узел содержит информацию о своем родителе, и последовательность узлов определяется их временем.
time node parent 12:00 A * 12:01 B A 12:02 Z ** ... Моя цель-найти самую длинную последовательность обхода DFS в узлах. Поэтому в других узлах, проходя последовательность в обратном направлении, я хотел бы выяснить, какая ее часть была преобразована (вперед) с помощью DFS.
Я попытался построить последовательность отношений «ребенок-gt;родитель» в обратном порядке:
P = ['sentinel'] #stack of parents V = [] #stack of values of nodes v = 0 #initially each node has value 0 for _, row in df[::-1].iterrows(): while row['node']==P[-1]: value = V.pop() P.pop() value = 1 P.append(row['parent']) V.append(value) value = 0 return V Этот код работает с «обычными» обходами, но он не обрабатывает повторяющиеся посещения. Например, предположим, что A является родителем B, и это последовательность, которую я имею
A -gt; B -gt; A -gt; B -gt; A -gt; B ... Затем код суммирует значения, в то время как истинная самая длинная последовательность имеет длину 2.
Я знаю, что код не работает должным образом, как в DFS (вперед) Я бы использовал либо раскраску узлов, либо любой другой метод, чтобы отслеживать, какой узел уже был посещен или нет.
В моем обратном подходе моя проблема заключается в следующем: если я сталкиваюсь с уже посещенным узлом, я фактически должен игнорировать предыдущий вклад этого узла в самую длинную последовательность. Но для меня не очевидно, как я мог бы на самом деле это сделать.
Вот пример, который отчасти затрудняет мне поиск правильного подхода:
Assume B is parent of C, A is parent of B, * is parent of A and the sequence is: A B C A B C Node Parent Value #longest DFS sequence C [B] [1] B [A] [2] #B popped from stack A [*] [3] C [B] [1,?] Я знаю, что B уже вносил свой вклад в стоимость раньше. Но нужно ли мне вставлять значение с вкладом от B из стека? И что произойдет потом, когда мы попадем в А? Я уже извлек значение из стека, и что теперь?