차트란 무엇입니까?
- 여러 점이 복잡하게 연결되어 있는 관계를 표현하는 자료구조
- 목적 ▷ 그래프 검색은 하나의 노드에서 시작하여 모든 노드를 한번 방문(검색)!
- 차트의 데이터는 배열처럼 정렬되어 있지 않기 때문에 원하는 데이터를 찾으려면 각 데이터를 개별적으로 방문해야 합니다.
- 방법 ▷ BFS & DFS
다이어그램의 구조
- 직접적인 관계두 점 사이에 선이 있습니다.
- 간접적인 관계몇 개의 점과 선에 걸친 라면
그래픽 용어
- 꼭지점
- 데이터를 저장하는 차트의 기본 요소인 노드라고도 함
- 가장자리
- 꼭짓점 간의 관계를 나타냅니다.
(꼭짓점을 연결하는 선)
- 꼭짓점 간의 관계를 나타냅니다.
- 이웃 볏
- 정점에서 가장자리로 직접 연결된 정점
- 가중 그래프
- 연결 강도를 보여주는 그래프(추가 정보 예: 서울에서 부산까지의 거리 등)
- 비가중 그래픽
- 연결 강도를 표시하지 않는 차트
- 무방향 그래프
- 서울에서 부산까지 운전할 수 있듯이 부산에서 서울까지 운전할 수 있습니다.
- 하지만 감독 그래프로 구현하면 서울에서 부산으로 갈 수 있지만 부산에서 서울로(또는 그 반대로) 가는 것은 불가능하다.
- 2점이면 일회용의 도로로 연결된다면 단방향 엣지로 표현할 수 있다.
- 서울에서 부산까지 운전할 수 있듯이 부산에서 서울까지 운전할 수 있습니다.
- 연결 다이어그램
- 모든 꼭지점이 간선으로 연결된 그래프(관계 있음)
- 연결되지 않은 그래프
- 꼭짓점 사이에 간선을 추가할 수 없는 그래프(관계 없음)
- 인도/아웃도
- 정점에 들어가고(들어가고) 나가는(나가는) 가장자리 수를 지정합니다.
- 정점에 들어가고(들어가고) 나가는(나가는) 가장자리 수를 지정합니다.
- 이웃
- 두 정점 사이에 직접 가장자리가 있는 경우 두 정점이 인접해 있습니다.
- 두 정점 사이에 직접 가장자리가 있는 경우 두 정점이 인접해 있습니다.
- 셀프 루프
- 꼭짓점에서 나온 모서리가 자신에게 직접 들어가는 경우 “셀프 루프가 있었다” 그것을 인쇄하십시오.
- 다른 정점을 거치지 않는 것이 특징이다.
- 주기
- 정점에서 시작하여 해당 정점으로 돌아갈 수 있는 경우 주기가 있다표현하다
- 내비게이션 그래프는 서울 → 대전 → 부산 → 서울로 이동할 수 있으므로 주기가 있는 그래프입니다.
FSO(광범위한 우선 검색) → 대기열
- 너비 우선 검색, 너비 우선 검색
- 두 정점 사이의 최단 경로를 찾는 데 사용됩니다.
최악의 경우 모든 경로를 살펴봐야 합니다. - 기준점을 기준으로 가장 가까운 정점에서 목적지까지 도달하는 방법을 찾는다.
DFS(딥퍼스트 서치)→스택
- 깊이를 찾는 방법 깊이 우선 탐색, 깊이 우선 탐색
- DFS는 끝까지 경로를 탐색하고 미국까지 도달하지 못하면 다음 경로에서 계속됩니다.
- 정점에서 시작하여 다음으로 이동하기 전에 경로를 완전히 탐색하는 데 사용됩니다.
- 퀘스트는 BFS보다 조금 더 오래 걸리지만 모든 노드를 완전히 탐색할 수 있습니다.
- 트리에서 inorder, preorder 및 postorder는 DFS 절차에 해당합니다.
DFS와 BFS는 모든 꼭짓점을 한 번만 방문한다는 공통점이 있지만 사용에 따른 장단점이 뻔하므로 상황에 맞는 검색 기법을 사용해야 합니다.