bfsearch
너비 우선 그래프 탐색(Breadth-first Graph Search)
구문
설명
예제
입력 인수
출력 인수
팁
dfsearch
와bfsearch
는 무방향 그래프를 유방향 그래프와 동일하게 처리합니다. 노드s
와 노드t
사이의 무방향 간선은s
에서t
로 연결되는 유방향 간선과t
에서s
로 연결되는 유방향 간선, 이 두 가지 유방향 간선처럼 처리됩니다.
알고리즘
너비 우선 탐색 알고리즘은 시작 노드 s
에서 시작하고 인접 노드의 인덱스 순서대로 인접 노드를 모두 탐색합니다. 그런 다음, 방문하지 않은 이웃 노드를 각각 순서대로 방문합니다. 이 알고리즘은 시작 노드에서 도달할 수 있는 모든 노드를 방문할 때까지 계속됩니다.
알고리즘은 아래와 같은 의사코드(Pseudo-code)로 작성될 수 있습니다.
Event startnode(S) Event discovernode(S) NodeList = {S} WHILE NodeList is not empty C = NodeList{1} Remove first element from NodeList FOR edge E from outgoing edges of node C, connecting to node N Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E) (depending on the state of node N) IF event was edgetonew Event discovernode(N) Append N to the end of NodeList END END Event finishnode(C) END
bfsearch
는 새 노드가 발견된 경우나 노드의 모든 진출 간선이 방문된 경우와 같이, 알고리즘의 다양한 이벤트를 설명하는 플래그를 반환할 수 있습니다. 이벤트 플래그가 아래 나열되어 있습니다.
이벤트 플래그 | 이벤트 설명 |
---|---|
'discovernode' | 새 노드가 발견되었습니다. |
'finishnode' | 노드의 모든 진출 간선이 방문되었습니다. |
'startnode' | 이 플래그는 탐색의 시작 노드를 나타냅니다. |
'edgetonew' | 간선이 발견되지 않은 노드에 연결되어 있습니다. |
'edgetodiscovered' | 간선이 이전에 발견된 노드에 연결되어 있습니다. |
'edgetofinished' | 간선이 완료된 노드에 연결되어 있습니다. |
자세한 내용은 events
에 대한 입력 인수 설명을 참조하십시오.
참고
입력 그래프가 시작 노드에서 도달할 수 없는 노드를 포함하는 경우, 'Restart'
옵션을 사용하면 너비 우선 탐색이 그래프에 포함된 모든 노드를 방문하게 됩니다. 이 경우, 'startnode'
이벤트는 탐색이 다시 시작될 때마다 시작 노드를 나타냅니다.
확장 기능
버전 내역
R2015b에 개발됨