데이터들과 그 관계를 보여주는 방법 중 하나
데이터 : node, vertex(정점), point(꼭짓점)
관계(노드 간의 관계) : edge(변), 간선(줄기 간, 줄 선)
서로 연관 있는 노드의 집합 G(graph) = (N(node), E(edge))
네트워크 형태의 관계를 보여주기 적합
복잡한 실세계의 문제를 모델링하기에 적합
그래프 관련 용어
노드(정점, 꼭짓점)
변(간선, 선)
차수(degree) : 특정 노드에 연결된 간선이 몇개
루프(loop) : 특정 노드가 자기 자신을 어떠한 기준까지 반복하며 참조하는 경우
그래프의 종류
방향 가중 그래프, 방향 비순환 그래프(DAG) 와 같은 다양한 그래프도 있다
방향(directed) 그래프
변이 한 방향만 가리킴, 꼬리 -> 머리로 이동 가능, 반대로는 불가능
무방향(undirected) 그래프
변에 특별한 방향이 없으며 양방향을 가리키는 것과 같음
순환(cyclic) 그래프
노드를 지나서 같은 노드로 돌아오는 경로가 있음, 이런 노드가 하나만 있어도 순환 그래프
비순환(acyclic) 그래프
노드를 지나면 돌아오는 경로가 없음, 그래프 안의 모든 노드 동일
가중(weighted) 그래프
각 변의 관계 정도가 다름, 각 변의 값이 다름
비가중(unweighted) 그래프
모든 변이 동일한 의미, 각 변의 값 같음, 별도 표기가 불필요
그래프의 다양한 표현 방법
원과 선
인접 행렬(adjacency matrix) : 노드 간의 연결을 배열로 표현
인접 리스트(adjacency list) : 노드 간의 연결을 리스트로 표현
인접 행렬, 인접 리스트
N x N 행렬
ㄴ G[N][N], N : G(그래프) 안에 있는 노드 수
서로 인접한 노드를 표현
ㄴ 인접 : 두 노드 사이를 연결하는 변
ㄴ i 에서 j 로 향하는 변이 있으면 G[i][j] = 1, 없으면 G[i][j] = 0
G 가 가중 그래프인 경우 0/1 대신 실제 가중치 저장
인접 행렬 장/단점
장점
쉽게 구현 가능
변 제거의 시간 복잡도 O(1)
두 노드의 변 존재 유무 확인 시간 O(1)
단점
공간을 더 차지함 O(N²), 2차원 배열이므로
간선의 유무 상관없이 언제나 같은 공간 차지
인접 행렬 만드는 시간 O(N²)
인접 노드를 찾는 시간 O(N)
인접 리스트 장/단점
장점
공간을 적게 사용 O(N + E), 최악 O(N²) : 모든 노드가 서로 연관관계가 있는 경우
삽입/삭제 빠름(연결리스트 사용한 경우)
단점
인접 행렬 장점의 반대로 두 노드의 변 존재 유무를 찾는 시간이 O(1) 보다 느림
ㄴ 인접 행렬처럼 색인한 데이터가 없어서 나온 시간
위상 정렬 알고리듬
2가지 방식 : 깊이 우선 탐색(DFS), 칸 알고리듬(Kahn's algorithm) 있음
2가지 용도 : 위상 정렬, 위상 정렬이 가능한 그래프인지 판단
전위 순회, 후위 선회를 사용하여 가능한지 확인
강의 자료에서는 후위 선회를 사용하고 역순으로(Stack, LinkedList) 확인하면 정렬이 되는 경우를 확인
강한 결합 요소(SCC : Strongly Connected Component)
방향 그래프에서 끈끈한 관계를 가지는 노드들의 최대 그룹
SCC 주 용도는 최적화
다른 알고리듬에서 고려해야 할 정점 수를 줄여줌
위상 정렬과 SCC
순환 그래프는 위상 정렬이 불가능
순환하는 노드들은 SCC
SCC 로 치환한 그래프는 DAG 이므로 위상 정렬 가능
위상 정렬을 하기 위해 SCC 사용하는 일이 흔함
강한 결합 알고리듬
DFS 기반 알고리듬
ㄴ 코사라주 알고리듬(Kosaraju's algorithm)
ㄴ 타잔 알고리듬(Tarzan's algorithm)
ㄴ 경로 기반 알고리듬
도달 가능성 기반 알고리듬(분할 정복)
