재귀를 사용하여 BFS 구현

Question

연결된 목록 표현이 주어지면 BFS을 재귀를 사용하여 구현하는 방법은 무엇입니까?

DFS은 재귀를 사용하여 구현할 수 있지만 BFS은 사용할 수 없습니다. 가능한 방법을 제안 하시겠습니까?

Answer 1

[]은 목록을 나타냅니다.

f(graph, past_nodes, current_nodes, mark): 
    new_nodes = all neighbors of current_nodes which are not in past_nodes 
    if new_nodes == []: 
     return 
    else 
     for each n in new_nodes: 
      mark(n) 
     f(graph, past_nodes union current_nodes, new_nodes, mark) 

는 m 당신이 BFS 순서의 각 노드에 대해 실행하고자하는 기능입니다 f(graph, [], [start_node], m)를 호출하여 시작합니다.

Answer 2

void bfs(int vertex) 
{ 
int p; 
void mark(int); 
m=g[vertex]; 
if(m->v==1) 
return; 
m->v=1; 
printf("%c ",m->a); 
while(m->link!=NULL) 
     { 
     m=m->link; 
     if(m->v==0) 
      { 
      m->v=1; 
      p=int(m->a)-65; 
      mark(p); 
      } 
     } 

m=g[vertex]; 
while(m->link!=NULL) 
     { 
     m=m->link; 
     bfs(p); 
      } 
} 

여기에 붙어 있습니다.