DFS - Реализация решения сложности времени O (| E |)

Question

Я пытаюсь реализовать DFS, однако, согласно A StackOverFlow link about DFS, DFS использует только Stack.

Это моя текущая реализация:

def DFS_graph_recursive(graph, start, end, stack): 
    #Stack to push the node when we are entering the node 
    stack.append(start) 
    while(end not in stack): 
     for i in graph.edges[start]: 
      #check if this is inside the stack, to make sure that it doesn't try to go back 
      if (i not in stack): 
       #Recursive Call 
       DFS_graph_recursive(graph, i, end, stack) 
     #Pop the stack when we are leaving this node, but need to make sure if end is inside 
    if(end not in stack): 
     stack.pop() 

Существует несколько проблем, временная сложность не выглядит как O (| E |). Первый цикл while - это O (| E |), однако мне нужно проверить, является ли мой следующий узел уже внутри стека, чтобы избежать перехода назад, если этот стек большой, и я предполагаю, что i not in stack принимает O (n) для вычисления, делая этот алгоритм похожим на O (| E |^2) по сложности.

if(end not in stack), делает алгоритм хуже с точки зрения временной сложности, так как для каждого поиска по краю ему нужно проверить, находится ли конец в стеке, что означает, что мы не хотим выталкивать стек, если нашли решение. Это, кроме того, увеличивает сложность времени до O (| E |^2 + | E |). Есть ли способ сделать это только с одним циклом?

С точки зрения космической сложности, это должно быть O (| V |) в худшем случае, что у нас есть длинное дерево с ветвящейся коэффициентом 1.

можно легко реализовать O (| E |) решение если он был двоичным типом дерева, который имеет направленный путь вниз к дочерним узлам. Проблема заключается в том, что поскольку проблема представляет собой неориентированный граф, допустим, что есть две вершины: A и B. Если A подключается к B, тогда B соединяется с A. Поэтому, если я не проверю if (i not in stack), я буду застревать, возвращаясь назад и вперед от А к в, в к А ... и т.д.

Answer 1

Используя этот алгоритм, вы на самом деле в конечном итоге будет тот же узел множественного числа раз (сложность i not in stack является дополнительным беспокойство)

You следует рассмотреть вопрос о сохранении списка visited/словаря, чтобы отслеживать посещаемые вами узлы. Если вы посетили узел, вы не будете толкать его в стеке. Код будет как -

vis = {} 
def DFS_graph(graph, start, end, stack): 
    #Stack to push the node when we are entering the node 
    stack.append(start) 
    vis[start] = 1 
    while len(stack): 
     # got to an element 
     found_element = stack[-1] 
     if found_element == end: 
      # you found the end, so break now 
      break 
     stack.pop() 
     for i in graph.edges[start]: 
      #check if this is inside the stack, to make sure that it doesn't try to go back 
      if i not in vis: 
       #Recursive Call 
       stack.push(i) 

Здесь я использую словарь, чей на самом деле сложность делает if i not in vis должна быть O (N) в худшем случае и O (1) в среднем случае. Если вы представляете свои узлы графика как g[0], g[1], g[2] ...., то вы можете сделать сложность в O (1) наихудшем случае, используя список.