C++: 그래프(Graph)

그래프

• 정점(Vertex)의 연결인 간선(Edge)로 이루어진 자료구조이다.
  • 리스트나 트리는 그래프의 특수한 케이스로 볼 수 있으며, 사실상 모든 자료구조의 가장 환원적인 근본에 있는 것이 그래프이다.

    종류

    그래프의 연결/간선 형태에 따라 크게 몇가지 기준으로 분류할 수 있다.

• 방향성(Directionality)
  • 무방향(Undirectional) - 간선에 방향성이 없음, 양방향 이동 가능
  • 방향(Directional) - 간선에 방향이 있음, 한쪽으로만 이동 가능
• 가중치 여부(Weightedness)
  • 가중치(Weighted)
  • 비가중치(Unweighted)
  • 비가중치에서 BFS, DFS등의 단순 탐색을 주로 사용하며, 가중치가 있는 까다로운 형태에서 다익스트라를 사용한다.

표현법

• 인접 행렬(Adjacency Matrix)
  • nxn 행렬에 간선에 해당하는 원소를 마킹하는 방식으로 표현한다.
  • 간선을 찾기가 매우 빠르지만 메모리 효율성이 좋지 못하다.
  • 정점들이 밀집해있거나 연결 확인을 많이 해야할 때 적합하다.
• 인접 리스트(Adjacency List)
  • 각 노드에서 이동할 수 있는 다른 노드를 들고있는 형태로 간선을 표현한다.
  • 인접 행렬보다 메모리 효율성은 높지만 간선을 찾는데 시간이 더 걸린다.
  • 대부분의 그래프 활용 상황에 적합한 편이다. 정점이 드문되게 분포되있거나 많이 있을 때 적합하다.
• 간선 리스트(Edge List)
  • 간선을 표현하는 시작과 끝의 쌍을 리스트 형태로 보관한다.
  • 구조가 매우 단순하지만 특정 정점의 이웃, 즉 공통 인자를 가지는 간선을 찾는데 오래걸린다.
  • 크루스칼 알고리즘(Kruskal’s algorithm)같은 간선 단위의 처리가 중요한 상황에 적합하다.

표현법	공간	연결 확인	이웃 찾기	적합한 상황
인접 행렬	O(V²)	O(1)	O(V)	밀집 그래프, 빠른 연결 확인
인접 리스트	O(V+E)	O(V)	O(deg)	희소 그래프, 대부분의 실전 상황
간선 리스트	O(E)	O(E)	O(E)	간선 단위 처리(정렬, MST 등)

탐색

• 깊이 우선 탐색 (Depth First Search)
  • 깊이 있는 정점까지 먼저 진행한다.
  • 미로 풀이나 사이클 검출에 강하다.
  • 보통 재귀함수나 스택을 활용한다.
• 너비 우선 탐색(Breadth First Search)
  • 가까이 있는 정점부터 먼저 확인한다.
  • 최단거리 확인에 적합하다.
  • 보통 큐를 활용해 구현할 수 있다.

    활용

• 게임
  • 맵 구조, 경로 탐색 - 점: 방/위치, 선 - 경로
    • 다익스트라/A*와 조합
  • 스킬트리, 퀘스트 의존성
  • 매치메이킹
• 웹/서버
  • 웹 검색 - 점: 페이지, 선: 링크
    • PageRank - 구글 검색 엔진 알고리즘
  • SNS - 점: 사람, 선: 친구/팔로우
  • 추천 시스템 - 점: 사용자/상품/영상 등 , 선 - 구매/선택/시청 등
  • CI/CD 빌드 파이프라인
  • 마이크로 서비스(Micro Service Architecture MSA) 호출 관계
• CS 전반
  • 컴파일러 호출 그래프
  • OS 프로세스 의존선
  • DB 조인 계획
  • 네트워크 라우팅
• “관계”로 정리될 수 있는 상황 전반.
• 코딩 테스트 최빈출 문제이자 알고리즘 핵심.