DFS 와 BFS 가 옮 겨 다 니 고 있 습 니 다.

깊이 우선 순위
1. 깊이 우선 반복 정의
주어진 그림 G 의 초기 상태 가 모든 정점 에 접근 하지 않 았 다 고 가정 합 니 다.G 에서 정점 v 를 초기 출발점 (원점) 으로 선택 하면 깊이 는 다음 과 같이 정의 할 수 있 습 니 다. 먼저 출발점 v 에 접근 하고 방문 한 것 으로 표시 합 니 다.그리고 v 에서 출발 하여 v 의 모든 인접 점 w 를 검색 합 니 다.만약 w 가 방문 한 적 이 없다 면 w 를 새로운 출발점 으로 깊이 우선 순 위 를 계속 옮 겨 다 니 며 그림 의 모든 원점 v 와 경로 가 통 하 는 정점 (원점 에서 도달 할 수 있 는 정점 이 라 고도 함) 이 모두 방문 되 었 을 때 까지 합 니 다.만약 에 이 그림 에 방문 하지 않 은 정점 이 있다 면 방문 하지 않 은 정점 을 새로운 원점 으로 선택 하여 상기 과정 을 반복 하고 그림 의 모든 정점 이 방문 되 었 을 때 까지 합 니 다.
그림 의 깊이 는 나무의 앞 순 서 를 옮 겨 다 니 는 것 과 유사 합 니 다.사용 하 는 검색 방법의 특징 은 가능 한 한 종심 방향 을 먼저 검색 하 는 것 이다.이 검색 방법 을 깊이 우선 검색 (Depth - first Search) 이 라 고 합 니 다.이에 따라 이 방법 으로 그림 을 옮 겨 다 니 는 것 을 자 연 스 럽 게 그림 의 깊이 라 고 부 릅 니 다.
2. 기본 실현 사상:
(1) 정점 v 에 접근 하기;
(2) v 의 방문 되 지 않 은 인접 점 에서 정점 w 를 선택 하여 w 에서 출발 하여 깊이 를 우선 적 으로 옮 겨 다 닙 니 다.
(3) 그림 에서 v 와 경로 가 통 하 는 모든 정점 에 접근 할 때 까지 상기 두 단 계 를 반복 합 니 다.
3. 의사 코드
순환 실현
(1) 정점 v 에 접근 하기;visited[v]=1;//알고리즘 실행 전 visited [n] = 0
(2) w = 정점 v 의 첫 번 째 인접 점;
(3) while (w 존재)  
           if (w 에 접근 하지 않 음)
                   정점 w 에서 출발 하여 이 알고리즘 을 재 귀적 으로 실행 합 니 다.             w = 정점 v 의 다음 인접 점;
vector< list > graph;
bool visited[100] = {0};
void dfs(int v)
{
    list::iterator it;
    visited[v] = true;
    printf("%5d", v);
    for (it = graph[v].begin(); it != graph[v].end(); ++it)
        if (!visited[*it])
            dfs(*it);
}

비 귀속 실현
 (1) 스 택 S 초기 화;visited[n]=0;
 (2) 정점 v 에 접근 하기;visited[v]=1;정점 v 스 택 S
 (3) while (스 택 S 비 어 있 음)
            x = 스 택 S 의 최상 위 요소 (스 택 에서 나 오지 않 음);
            if (접근 하지 않 은 x 의 인접 점 w 를 찾 습 니 다)
                    w 방문 하기;visited[w]=1;
                    w. 창고 에 들 어가 기;
            else
                     x. 창고 에서 나 오기; 
범위 우선
1. 우선 순위 정의
 그림 의 넓이 가 우선 BFS 알고리즘 을 옮 겨 다 니 는 것 은 층 을 나 누 어 검색 하 는 과정 입 니 다. 트 리 의 층 차 를 옮 겨 다 니 는 알고리즘 과 같 습 니 다. 또한 행렬 의 순서에 따라 이 정점 의 인접 정점 에 접근 할 수 있 도록 행렬 이 필요 합 니 다.
2. 기본 실현 사상
(1) 정점 v 가 대열 에 들어간다.
(2) 대기 열 이 비어 있 지 않 을 때 계속 실행 합 니 다. 그렇지 않 으 면 알고리즘 이 끝 납 니 다.
(3) 대열 을 나 가 팀 의 정점 v 를 얻는다.정점 v 에 접근 하고 정점 v 가 접근 되 었 음 을 표시 합 니 다.
(4) 정점 v 의 첫 번 째 인접 정점 col 을 찾 습 니 다.
(5) v 의 인접 정점 인 col 이 접근 하지 않 으 면 col 이 대기 열 에 들 어 갑 니 다.
(6) 정점 v 의 또 다른 인접 정점 col 을 계속 찾 아 단계 로 이동 합 니 다 (5).
        정점 v 의 모든 접근 하지 않 은 인접 점 이 처 리 될 때 까지.단계 로 가기 (2).
광도 우선 스 트 리밍 그림 은 정점 v 를 시작 으로 가 까 운 곳 에서 먼 곳 까지 순서대로 방문 하고 v 와 경로 가 연결 되 며 경로 길 이 는 1, 2,... 의 정점 입 니 다.'맨 위 에 먼저 접근 하 는 인접 점' 을 '맨 위 에 접근 하 는 인접 점' 보다 먼저 접근 하기 위해 서 는 대기 열 저장 접근 의 정점 을 설정 해 야 합 니 다.
3. 의사 코드
(1) 대기 열 Q 초기 화;visited[n]=0;
(2) 정점 v 에 접근 하기;visited[v]=1;정점 v 대기 열 에 들 어가 기 Q;
(3) while (대기 열 Q 비 어 있 지 않 음)   
              v = 대기 열 Q 의 맞 춤 형 요소 가 나 옵 니 다.
              w = 정점 v 의 첫 번 째 인접 점;
             while (w 존재) 
                     w 에 접근 하지 않 으 면 정점 w 에 접근 합 니 다.
                     visited[w]=1;
                     정점 w 대기 열 Q;
                     w = 정점 v 의 다음 인접 점.
vector< list > graph;

bool visited[100] = {0};
void bfs(int v)
{
    list::iterator it;
    printf("%5d", v);
    visited[v] = true;
    queue t;
    t.push(v);
    while (!t.empty())
    {
        v = t.front();
        t.pop();
        for (it = graph[v].begin(); it != graph[v].end(); ++it)
            if (!visited[*it])
            {
                printf("%5d", *it);
                t.push(*it);
                visited[*it] = true;
            }
    }
    cout << endl;
}

좋은 웹페이지 즐겨찾기