Как заполучить эту плохо написанную статью о DFS?

Question

Как человек, у которого нет английского как языка мам (Россия), я читал эту статью в Википедии: http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Depth-first_search

и я стараюсь следовать этому примеру псевдокода, написанному на хардкорном английском языке с минимальными объяснениями или комментариями.

В частности, я не понимаю, что они пытаются сказать этим предложением:

DFS(u):

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

для всех узлов v, смежных с вами, сделать

Моя проблема с этим предложением - «смежная» часть. Мой словарь говорит, что это означает что-то вроде «сосед». Итак, я должен перебрать подузлы суперузла u? Обратите внимание, что u является узлом в графе.

Или они пытаются сказать, что я должен перебрать все подузлы u? Потому что это будет иметь огромное значение.

Помимо этих английских проблем, они забыли упомянуть, что означают d и p , что заставляет меня рвать все мои волосы (да, даже те, что усы).

Ссылки в статье просто повторяют этот мало-мальски загадочный материал. Может быть, кто-то смог переписать это так, чтобы оно было более понятным для человека, с большим количеством комментариев и значимых переменных? Я не нашел ни одного по-настоящему хорошего объяснения, которое могло бы похвастаться доминирующим интеллектом автора, связанного с DFS.

Так что, если кто-то может переписать это на лету лучшим способом с большей учебной ценностью, которая спасет мой день, сохраните мои усы. Сохранить все Спасибо.

Answer 1

Мой код из похожего вопроса может быть полезным для вас:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

dfs(t)

Answer 2

Это означает: «Для всех узлов v, напрямую связанных с u».

Псевдокод в http://en.wikipedia.org/wiki/Depth-first_search намного проще.Надеюсь, что это работает лучше для вас.

Если я правильно помню, d, p и f взяты из книги Кормена об алгоритмах.Они означают (соответственно) момент, когда узел был обнаружен, предыдущий узел в дереве обхода DFS и момент, когда узел был завершен.Некоторые из них полезны для некоторых приложений (таких как топологическая сортировка, поиск компонентов и другие алгоритмы вокруг DFS), но они не являются критическими для самой DFS.

Answer 3

Я был бы немного менее укоризненным, когда языковой барьер на вашем сторона.

В любом случае, «смежный» означает напрямую связанный. На этом графике:

    A   E
   / \ /
  B   C
       \
        D

A смежно с B и C, B смежно с A, C смежно A, E и D, D смежно с C, а E смежно с C.

Вот тот же код, более подробный:

{with the following global variable:
    time, which is a single integer, and initially 0;}

{and a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;
    previous-node;
    discovery-time;
    finishing-time;}

{depth-first-search of node u is:
    visit the value of u;
    increase time by 1;
    set the discovery-time of u to time;
    set the colour of u to grey;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            set the previous-node of v to u;
            depth-first-search of v;}}

    increase time by 1;
    set the finishing-time of u to time;
    set the colour of u to black;}

В этом коде есть несколько вещей, которые служат исключительно иллюстративным цели. Центральная тема такова:

{with a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;}

{depth-first-search of node u is:
    visit the value of u;
    set the colour of u to black;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            depth-first-search of v;}}}