알고리즘 --- 깊이 우선 검색 DFS 와 넓이 우선 검색 BFS (최 단 경로)

범위 우선 검색 (BFS) (대기 열 구현) 은 가장 짧 은 경 로 를 구 하 는 데 사 용 됩 니 다. 보통 경로 의 최소 값 을 제시 합 니 다. 이미지 에 의 해 '수박 겉 핥 기' 라 고 묘사 할 수 있 습 니 다. 구체 적 으로 모든 정점 은 인접 노드 (인접 노드 가 방문 되 지 않 았 다 면) 에 만 접근 하고 이 인접 노드 를 기록 하 는 것 입 니 다.인접 노드 에 접근 한 후에 이 정점 에 대한 접근 을 끝 냅 니 다.
'선진 선 출' 대기 열 을 우선 사용 하고 이 대기 열 을 통 해 처음 발 견 된 노드 를 저장 하여 다음 에 처리 할 수 있 도록 합 니 다.그리고 다시 발 견 된 노드 에 대해 우 리 는 무시 합 니 다. 대열 에 넣 지 않 습 니 다. 다시 발 견 된 노드 이기 때 문 입 니 다.

이미 처 리 된 것 일 뿐이다.

또는 대기 열 에 저장 되 어 처리 되 지 않 은 것.

깊이 우선 검색 (DFS) (스 택 클래스 구현) 은 이미지 에 의 해 '뚝배기 깨 기 끝까지 묻 기' 라 고 묘사 할 수 있 습 니 다. 구체 적 인 것 은 정점 을 방문 한 후에 저 는 다음 인접 한 정점 을 방문 하 는 것 입 니 다. 이렇게 왕복 하면 현재 정점 이 방문 되 거나 인접 한 정점 이 존재 하지 않 습 니 다.
마찬가지 로 알고리즘 서론 은 '똑똑 한 방법' 을 사용 하여 세 가지 색깔 로 세 가지 상 태 를 표시 했다.그러나 이 세 가지 상 태 는 범위 우선 검색 과 다르다.

WHITE 정점 미 방문

GRAY 의 깊이 있 는 검색 경로 의 정점, 즉 발견 되 었 을 때

블랙 은 이 정점 의 인접 정점 을 모두 방문 했다

두 알고리즘 모두 O (V + E) 로 사용 할 때 적당 하 게 선택 합 니 다.흰 회색 표 지 를 사용 할 때 갑자기 깊이 우선 검색 으로 그림 에 고리 가 있 는 지 여 부 를 판단 하 는 방법 을 깨 달 았 다.
깊이 우선 과 넓이 우선 은 각각 장단 점 이 있다.

광 우 는 메모리 가 많 고 가장 좋 은 해 를 찾 을 수 있 으 며 모든 가 지 를 옮 겨 다 녀 야 합 니 다. 광 우 는 디 코스 처 단원 의 가장 짧 은 경로 알고리즘 입 니 다.

깊이 가 좋 으 면 메모리 가 적 고 가장 좋 은 해 (일정한 조건 에서) 를 찾 을 수 있 지만 접근 해 (장점) 를 빨리 찾 을 수 있 습 니 다. 모든 가지 (즉 속도 가 빠르다) 를 옮 겨 다 니 지 않 아 도 될 수도 있 습 니 다. 깊 은 응용 은 바로 게임 을 계속 보 는 것 입 니 다.

더 많은 상황 에서 심 우 는 비교적 좋 은 방안 이다.
DFS:

void dfs(int p,const int end,int dist,int weit){  
    if(p==end){  
        if(distmind)return;//             case     
  
    for(i=0;i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

정렬 의 거품 정렬

거품 정렬 (BubbleSort) 의 기본 개념 은 인접 한 두 개의 수 를 순서대로 비교 하고 소 수 를 앞 에 놓 고 대 수 를 뒤에 놓 는 것 이다.즉, 첫 번 째: 먼저 첫 번 째 와 두 번 째 수 를 비교 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

알고리즘 --- 깊이 우선 검색 DFS 와 넓이 우선 검색 BFS (최 단 경로)

좋은 웹페이지 즐겨찾기