BFS и правильность термина «ПОСЕТИЛ»

Question

mark x as visited 
list L = x 
tree T = x 
while L nonempty 
    choose some vertex v from front of list 
    process v 
    for each unmarked neighbor w 
     mark w as visited 
     add it to end of list 
     add edge vw to T 

Основная часть кода будет выбирать, как отмечать соседний узел как посетивший его перед посещением. Не будет ли технически корректным добавлять всех соседей и посещать их позже?

list L = x 
tree T = x 
while L nonempty 
    choose some vertex v from front of list 
    if (V NOT YET VISITD) 
     MARK V AS VISITED HERE 
     for each unmarked neighbor w 
      add it to end of list 
      add edge vw to T 

Почему каждый BFS, кажется, отмечает узел как посетивший вас, когда вы еще не посещали их? Я пытаюсь найти теоретически правильный код для BFS. Какой из них правильный?

Answer 1

Оба правильные, но они используют разные определения слова visited. Обычно алгоритмы имеют множество вариаций и имеют множество различных реализаций, которые являются правильными, а BFS - один из примеров.

Answer 2

Оба алгоритма работают, но вторая версия может добавить один и тот же узел в список L два раза. Это не влияет на правильность из-за дополнительной проверки, был ли узел посещен, но он увеличивает потребление памяти и требует дополнительной проверки. Вот почему вы обычно видите первый алгоритм в учебниках.