BFS 탐색

그래프에 대한 기본 폭 우선 검색 탐색의 나의 이해는 다음과 같습니다BFS 탐색

BFS   
    Start from any node. 
    Add it to queue. 
    Add it to visited array. 

    While queue is not empty: 
     Remove head from queue; 
     Print node. 

     add all unvisited direct subchilds to que; 
     mark them as visited

그러나, 우리는 주어진에서 감독 그래프를 통과해야하는 경우 주어진 노드에서 (직접 또는 간접적으로) 모든 노드에 액세스 할 수있는 것은 아닙니다.이 상황의 그래프를 탐색하는 데 BFS를 어떻게 사용합니까?

당신은뿐만 아니라이 그래프에 설명 해주십시오 수 :

a=> b => d => e => d 
a=> c => d

을 여기에서 시작 노드가 b 경우, 우리는 a 및 c를 인쇄하지 않습니다.

알고리즘에 뭔가 빠졌습니까?

HashMap<String, ArrayList> adj = new HashMap();을 사용하여 그래프를 저장할 인접 목록을 만들었습니다.

출처

2010-04-06 user309687

아니요, 누락 된 것이 없습니다. 노드에 도달 할 수 없으면 검색에서 노드를 찾을 수 없습니다. – Ross

을 제외하고 "모든 노드에서 시작"부분 - BFS 순회는 루트 노드에서 시작해야합니다. 예를 들어, 은 노드 a로 시작하는을 가지고 있습니다. 그렇지 않으면 말한 것처럼 결코 방문하지 않습니다. 우리는 주어진 노드에서 감독 그래프를 통과하고있는 경우

출처

2010-04-06 04:06:43 RarrRarrRarr

깊이 우선 검색에서도 마찬가지입니다. – Thilo

그래프에 반드시 루트 노드가있는 것은 아닙니다. 질문은 분명히 그래프에 관한 것입니다. – Ross

그러나 내가 볼 수있는 것은 DAG에 관한 질문이며 DAG에는 하나 이상의 루트 노드가 있습니다 (루트 노드가 두 개 이상있는 경우 모든 루트 노드가없는 한 모든 그래프 검색 알고리즘이 일부 노드를 놓치게됩니다. 초기 세트에 추가됨). – Vatine

그러나, 모든 노드가 주어진 노드에서 액세스 할 수있는 [직접 또는 간접적으로] 어떻게 우리는 BFS는 같은 사용.

검색 알고리즘이 그래프를 탐색합니다. 탐색 할 수없는 가장자리와 도달 할 수없는 노드가있는 경우 검색에서 노드를 찾지 못합니다.

출처

2010-04-06 04:07:25 Thilo

답변

관련 문제