BFS의 알파벳순 정렬

Question

알파벳 순서로 BFS를 구분하지 않고 BFS를 구분하는 데 문제가 있습니다.

예를 들어,이 그래프에서 스패닝 트리를 찾으려면 (E에서 시작).

Starting G

{E, B}와 {E, C}를 추가 한 후

T after added EB and EC

나는 계속 추가 할 수 있는지 확실하지 않다 {B, F} 또는 {C, F }. 대단히 감사합니다.

Answer 1

{B, F} 또는 {C, F}을 계속 추가 할 것인지 확실하지 않습니다. 매우 고맙습니다.

글쎄, 대답은 당신이 BFS의 알고리즘의 대기열에 정점 B 및 C을 추가 한 순서에 따라 달라집니다. 당신이 알고리즘을 보면 :

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. 

그것의 명확한

그것은 하는 당신이 정점의 이웃을 enque 위해해야한다 무엇을 지정하지 않습니다. 당신이 순서대로 E의 이웃을 방문하는 경우

그래서 : CB, , 큐 데이터 구조, 노드이 dequed됩니다 B의 다음 명확 인해 FIFO 에 속성 (에서 촬영 대기열) C 전에 당신은 가장자리가 B - F 것입니다. 주문이 C 인 경우 인 경우 비슷한 이유 때문에 가장자리가 C - F이됩니다.

일단 의사 코드를 이해하면 매우 명확하게 이해할 수 있습니다.