자료구조/비선형구조/그래프

Graph란?

• 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

• 목적 ▷ 그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것!
• 그래프의 데이터는 배열처럼 정렬되어 있지 않기 때문에 원하는 자료를 찾으려면, 하나씩 모두 방문해야 함
  • 방식 ▷ BFS & DFS

---

Graph의 구조

• 직접적인 관계가 있는 경우, 두 점 사이를 이어주는 선이 있습니다.
• 간접적인 관계라면, 몇 개의 점과 선에 걸쳐 이어집니다

Graph terms

• 정점 (vertex)
  • 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge)
  • 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
• 인접 정점 (adjacent vertex)
  • 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프 (weighted Graph)
  • 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프
• 비가중치 그래프 (unweighted Graph)
  • 연결의 강도가 적혀져 있지 않는 그래프
• 무(방)향 그래프 (undirected graph)
  
  • 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다.
  • 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대).
  • 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 연결 그래프
  • 정점들이 간선으로 전부 연결이 되어 있는 그래프 (관계가 있다)
• 비연결 그래프
  • 정점 사이에 어떠한 간선도 추가할 수 없는 그래프 (관계가 없다)
• 진입차수 (in-degree) / 진출차수 (out-degree)
  • 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 인접 (adjacency)
  • 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
• 자기 루프 (self loop)
  • 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 "자기 루프를 가졌다" 라고 표현합니다.
  • 다른 정점을 거치지 않는다는 것이 특징입니다.
• 사이클 (cycle)
  • 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다.
  • 내비게이션 그래프는 서울 → 대전 → 부산 → 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.

---

BFS(Breadth-First Search)→Queue

• 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색

• 두 정점 사이의 최단 경로를 찾을 때 사용합니다. 최악의 경우에는 모든 경로를 다 살펴봐야 함.
• 기준점을 기준으로 목표점까지 가는 방법을 가까운 정점부터 탐색한다.

---

DFS(Depth-First Search)→Stack

• 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색

• DFS는 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색
• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용
• BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다.
• tree에서 inorder, preorder, postorder이 DFS방식에 해당됨

DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 사용할 때의 장단점은 분명하기 때문에 해당 상황에 맞는 탐색 기법을 사용해야 합니다.