정점(V)과 간선(E)으로 이루어진 자료구조
경로
정점 A에서 B로 가는 경로
사이클
시작점과 끝점이 동일한 경로
단순경로(사이클)
경로(사이클)에서 같은 정렬을 두 번 이상 방문하지 않는 경로(사이클)
가중치
간선을 사용할 때 드는 비용
차수(degree)
하나의 정점에 연결되 있는 간선의 수
간선에 방향이 있는 경우 in-degree 와 out-degree 를 나눠서 생각해야 함
방향이 있는 경우 방향도 같이 저장해줘야 함
그래프 저장의 목적
: 하나의 정점과 연결된 간선을 빠르게 찾기 위함
: 전체 공간의 수를 적게 만들어야 함
1. 인접행렬
정점x정점 이차 배열에 간선의 유(1)/무(0) 또는 간선의 가중치를 저장
2. 인접리스트
정점 일차 배열에 각 정점과 연결된 정점들로 이루어진 배열을 값으로 가짐
3. 간선리스트
1. 깊이 우선 탐색(DFS)
Stack 사용
2. 너비 우선 탐색(BFS)
Queue 사용
참고
다익스트라 알고리즘
연결요소
그래프의 모든 정점이 연결되어있지 않는 경우, 나누어진 각각의 그래프를 연결 요소라고 함
이분 그래프
그래프를 A/B 두 그룹으로 나눌 수 있고, 각 그룹안의 정점끼리 연결된 간선이 없는 경우
모든 간선의 한 끝점은 A 그룹, 다른 끝점은 B인 경우
플러드필
어떤 위치와 연결된 모든 위치를 찾는 알고리즘