DFS 와 BFS 가 옮 겨 다 니 고 있 습 니 다.
3671 단어 알고리즘상용 시험 데이터 구조 와 알고리즘
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.