그래프
: 정점의 모음과 이 정점을 잇는 간선의 모음과의 결합
정점의 집합을 V, 간선의 집합을 E, 그리고 그래프를 Q라고 했을 때 G = (V, E)이다.
간선으로 연결되어 있는 두 정점을 가리켜 서로 '인접(adjacent), 또는 이웃 관계에 있다고 말한다.
경로는 길이는 가지는데, 길이는 정점과 정점 사이에 있는 간선의 수로 정의된다.
간선이 방향성을 가지면 방향성 그래프, 방향성이 없으면 무방향성 그래프가 된다.
인접 행렬(Adjacency Matrix)
: 정점끼리의 인접 관계를 나타내는 행렬
그래프의 정점의 수를 N이라고 한다면 N*N크기의 행렬을 만들어 행렬의 각 원소를 한 정점과 또 다른 정점이 인접해 있는 경우 1로 표시하고, 인접해 있지 않은 경우 0으로 표시한다.
장점 : 정점 간의 인접 여부를 빠르게 알 수 있다.
단점 : 인접 관계를 행렬 형태로 저장하기 위해 사용하는 메모리의 양이 정점의 크기 * N^2에 이른다.
인접 리스트(Adjacency List)
: 그래프 내의 각 정점의 인접 관계를 표현하는 리스트. 각 정점을 자신과 인접해 있는 모든 정점의 목록을 리스트로 관리하도록 하는 것이다.
장점 : 정점과 간선의 삽입이 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리의 양이 적다.
단점 : 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차 탐색을 해야한다.
p.s) 화요일부터 3일 간 온라인 코딩 테스트가 있는 관계로 금요일부터 포스팅 하겠습니다.
