진행자

이건우

Graph?

노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미한다.

서로 다른 개체(객체)가 연결되어있다. → 그래프 알고리즘

ex1) 여러 개의 도시가 도로로 연결되어 있다 ex2) N개의 집을 방문하려는데, 도로로 연결되어 있다 ex3) 축제로 가는 최단 경로를 찾는데 각 마을마다 도로로 연결되어 있다

<aside> 💡 그래프를 탐색하면서 보통 알고리즘 문제를 해결하게 됨. 그래프 탐색? → 하나의 node로 부터 시작해 차례대로 모든 node들을 한 번씩 방문

</aside>

Graph vs Tree

??????? 순환 그래프, 완전 그래프, 정규 그래프, 가중 그래프

방향성이 있는 비순환 그래프 → 트리

그래프 표현 방법

인접 행렬(Adjacency Matrix)

• 2차원 배열을 사용하는 방식
  • 소요 메모리: O(V2)
  • 소요 접근 시간: O(1)
  • 메모리 공간이 많이 필요하지만 특정 노드 간 간선의 비용을 O(1) 시간으로 즉시 알 수 있음

인접 리스트(Adjacency List)

• 리스트를 사용하는 방식
  • 소요 메모리: O(E)
  • 소요 접근 시간: O(V)
  • 간선의 개수인 O(E) 만큼만 메모리 공간이 필요하지만 O(V) 시간 소요

메모리와 시간을 염두에 두고 알고리즘을 선택, 구현하는 것이 중요. ex) 최단 경로 문제를 만났을 때, 노드의 개수가 적다면 인접 행렬, 노드와 간선 개수가 많으면 인접 리스트

그래프 탐색 알고리즘 DFS / BFS

• DFS(Depth First Search) 깊이 우선 탐색
  • 최대한 깊이 내려간 뒤, 더 이상 깊이 내려갈 수 없을 때 옆으로 이동
  • 시작 node로 부터 가장 가까운 node를 먼저 방문하고, 멀리 떨어져 있는 node를 나중에 순회
  • 두 node 사이의 최단 경로를 찾고 싶을 때 사용
  • Code...