jumpingz   2년 전

비가중치 그래프에서 BFS 가 최단 경로알고리즘이다라고는 들어보았으나 왜인지 설명하는 곳은 찾아 보질 못했네요... 검색능력이 꽝인건지 검색해도 보이지 않는데.. 혹시 설명된 링크나 해당 원리를 설명해주실수 있으신가요??

wooljs   2년 전

큐가 가지는 FIFO 특성에 따라서 가장 가까운 거리에 있는 노드들이 큐에 먼저들어가게 됩니다. 따라서 같은 컴포넌트 안에 있는 것이 보장이 된다면 최단거리를 구하는데 사용될 수 있습니다.

wooljs   2년 전

수정이 안되서 정정 댓글남깁니다.


bfs는 자신과 바로 연결되어 있는 노드들을 큐에 넣습니다.


그리고 큐는 FIFO에 따라서 가장 먼저들어온 것들을 가장먼저 처리합니다. 


이 두 개가 특성이 결합되서 시작지점으로부터 간선의 수가 작은 곳 부터 먼저 처리되게됩니다.


따라서 간선 2개로 연결되어 있는 노드에 도달하는 경우가 간선 1개로 도달하는 경우는 발생하지 않습니다.

wooljs   2년 전

모바일이라 그런지.. ㅠㅠ 

간선 2개로 도달할 수 있는 노드가 간선 1개로 도달할 수 있는 노드보다 큐에 먼저 들어오는 일은 발생하지 않는다.

jumpingz   2년 전

아이고 인제서야 답글 다네요 까먹고잇엇네... 감사합니다.

댓글을 작성하려면 로그인해야 합니다.