데이터 구조에서 그래프를 두 번 순회하고 알고리즘과 아이디어를 적어주세요. 감사합니다

BFS, 너비 우선 검색

먼저 시작점에 가장 가까운 영역을 탐색한 다음 전체 그래프까지 멀리 있는 영역을 탐색합니다. 먼저 시작점에서 거리가 1인 모든 지점을 탐색한 다음 거리가 2인 모든 지점으로 이동합니다...

구체적인 구현을 위해서는 보조 저장을 위한 대기열이 필요합니다.

예를 들어 S는 시작점이고 S는 세 점 A, B, C에 인접해 있습니다. A는 A1과 A2에 인접하고, B는 B1과 B2에 인접하며, C는 다른 점과 인접하지 않습니다. A를 순회할 때 일어나는 일은 A1과 A2가 "발견"된다는 것입니다. 그러나 A1과 A2는 즉시 통과할 수 없으므로 BFS의 목적에 어긋나므로 B와 C를 먼저 통과해야 합니다. 그리고 B와 C는 확실히 A1과 A2보다 먼저 "발견"되므로 이는 "선입 선출" 특성을 반영하므로 확장된 노드를 임시로 저장하기 위한 대기열이 필요합니다

BFS()

{

queue q;

q.push(s); //초기 s 포인트

while (q는 비어 있지 않음)

{

q에서 요소 가져오기

q Enqueue의 노드를 입력하지 않고 요소를 "검색"

}

}

DFS, 깊이 우선 검색

먼저 경로를 선택하고 경로의 지점을 탐색합니다. 그런 다음 경로 끝에서 시작하여 뒤로 물러서서 다른 경로와 각 분기에서 그 위의 지점을 횡단합니다.

구체적인 구현은 재귀로 작성하는 경우가 많기 때문에 스택을 통한 보조 저장소로 이해할 수 있습니다.

그래도 위의 거리를 유지하더라도 DFS에서 생성되는 시퀀스 중 하나는 S, A, A1, A2, B, B1, B2, C입니다. 경로 S, A 및 A1은 첫 번째 경로로 선택된 다음 다시 돌아가서 점차적으로 A2 경로를 A의 두 번째 경로로 선택합니다. 각 지점에서 수행되는 작업은 "발견", "순회", "되감기"이므로 작업 유형이 동일하므로 재귀적으로 작성하는 경우가 많습니다. . .

DFS(int target)

{

for(대상의 각 검색 지점)

{

DFS(검색 지점)

}

//기능 종료는 실제로 롤백 프로세스입니다.

}