Алфавитный порядок в BFS

Question

У меня есть проблемы, различающие BFS с алфавитным порядком и BFS без него.

Например, чтобы найти связующее дерево в этом графе (начиная с E).

Начиная с G

После добавления {E, B} и {E, C}

T после добавления EB и EC

Я не уверен, стоит ли продолжать добавлять {B, F} или {C,F}. Большое спасибо.

Answer 1

Я не уверен, стоит ли продолжать добавлять {B,F} или {C,F}. Большое спасибо.

Что ж, ответ зависит от порядка, в котором вы добавляете вершины B и C в свою очередь алгоритма BFS. Если вы посмотрите на алгоритм:

BFS (G, s)      //Where G is the graph and s is the Source Node

  let Q be queue.
  Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.

  mark s as visited.
  while ( Q is not empty)
       //Removing that vertex from queue,whose neighbour will be visited now
       v  =  Q.dequeue( )

      //processing all the neighbours of v  
      for all neighbours w of v in Graph G
           if w is not visited 
                Q.enqueue( w ) //Stores w in Q to further visit its neighbours                       

      mark w as visited.

Понятно, что в нем не указан порядок следования соседям вершины.

Поэтому, если вы посещаете соседей E в следующем порядке: B, C, то, очевидно, благодаря свойству FIFO структуры данных Queue, узел B будет отключен (удален из очереди) перед C, и у вас будет преимущество B- F, Если порядок C, B, то ребро будет C- F по аналогичным причинам.

Как только вы поймете псевдокод, вы поймете его очень четко.