[알고리즘] Graph

우노·2024년 4월 28일

알고리즘

Algorithm

목록 보기

3/10

그래프; 개념과 활용

그래프란?

정점(vertex, node)와 간선(edge)으로 이루어진 자료구조로써 간선으로 연결된 정점들이 하나의 그래프를 구성한다.

코딩테스트에서는 주어진 그래프를 해당 언어의 자료구조로 구현하고 이를 활용하여 경로 비용, 조건 부합성 등을 계산하는 방향으로 제시된다.

➕ 컴퓨터공학에서 그래프는 알고리즘 그래프 이론에서 활용하며 유한 그래프의 구조를 계산하는 알고리즘과 알고리즘의 계산 복잡도를 연구한다. 일부 문제가 NP-완전 문제이다.

그래프 종류

방향/무방향 그래프
간선의 방향 유무로 구분
가중치 그래프
간선에 가중치/비용 부여
순환/비순환 그래프
회로(cycle)의 유무로 구분

회로(cycle)
= 간선을 한 번만 지나갈 수 있을 때, 한 정점에서 출발하여 다시 해당 정점으로 갈 수 있는 경로

🌲 트리
비순환 그래프의 일종으로 부모→자식 단방향 그래프
연결/비연결 그래프
그래프를 이루는 정점 중 두개를 선택하는 모든 경우에 대한 경로 존재 여부

이분 그래프
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프
⇒ 같은 그룹의 정점들끼리는 간선을 갖지 않도록 정점을 두 그룹으로 나눌 수 있는 그래프

완전 그래프
그래프를 이루는 정점 중 두개를 선택하는 모든 경우에 대한 간선 존재 여부
부분 그래프 (subgraph)
임의의 그래프의 부분집합

정규 그래프, 완벽 그래프 등 몇가지 더 있지만 코딩테스트에서 잘 쓰이지 않는다.

그래프 표현

인접 리스트
각 정점에 인접한 (간선으로 연결된) 정점을 저장

Linked List / vector 배열 (ctor<int> adj[]) / 딕셔너리 등
⇒ 간선이 있는 경우만 저장하기 때문에

공간 면에서 효율적 → 간선이 많지 않은 그래프에 효과적
탐색 면에서 효율적

➕ 간선 리스트 - 각 정점에 연결된 간선을 [출발 노드, 도착 노드, 가중치] 형태로 저장

인접 행렬
두 정점의 인접 여부와 가중치 등을 2차원 배열에 저장
⇒ 주어진 그래프에 쉽게 적용 가능

그래프 순회; Graph Traversal

그래프의 모든 정점들을 방문하는 것

각 정점들을 한 번 이상 방문하는 경우,
다른 모든 정점들을 연결시켜주는 정점이 존재하지 않는 경우 모두 가능하다.

트리 순회
사이클이 존재하지 않고 다른 모든 정점을 연결시켜주는 루트가 존재

루트 탐색 순서를 기준으로 전위(preorder), 중위(inorder), 후위(postorder) 탐색 방법과
흔히 BFS로 불리는 정점의 레벨 순서로 탐색하는 레벨 오더(level order) 탐색 방법이 존재한다.

그래프 활용

아래 알고리즘은 하나하나 따로 톺아보는 것이 필요하다.

그래프 탐색 - DFS/BFS
최단 경로 | 최소 비용 - 다익스트라 (Dijkstra), 벨만-포드 (Bellman-Ford), 플로이드 (Floyd)
최소 신장 트리 - 크루스칼 (Kruskal), 프림(Prim)
선후 관계 - 위상 정렬