그래프의 정의
그래프는 정점의 모음과 이 정점을 잇는 간선의 모음
“정점의 집합을 V, 간선의 집합을 E, 그리고 그래프를 G라고 할 때, G = (V, E)”
•
Adjacent (인접) : 간선으로 연결되어 있는 두 정점을 가리켜 인접 또는 이웃관계에 있다고 말한다.
•
Path (경로) : 간선을 통해 서로 이웃이 된 각 정점들이 그래프 안에서 형성하는 길
•
Cycle (사이클) : 어느 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 그 경로를 일컬어 사이클이라 한다.
•
Directed Graph (방향성 그래프) : 간선이 방향성을 가지면 방향성 그래프
•
Undirected Graph (무방향성 그래프) : 간선에 방향성이 없으면 무방향성그래프
•
Connectivity (연결성) : 무방향성 그래프 내의 두 정점 사이에 Path 가 존재하면 ‘이 두 정점은 연결되어 있다'고 한다. 그리고 그래프 내의 각 정점들이 다른 모든 정점들과 연결되어 있으면 ‘이 그래프는 연결되었다' 라고 한다.
그래프의 표현
그래프는 정점 집합과 간선 집합의 결합이기에 다시말해 그래프를 표현한다는 것은 정점의 집합과 간선의 집합의 표현문제이다.
간선이 그냥 선이 아닌 정점과 정점의 인접관계를 표현하는 것이므로 결국 그래프를 표현하는 것은 간선, 즉 정점과 정점의 인접 관계를 어떻게 나타내는가로 귀결된다.
Adjacency Matrix (인접 행렬)
정점끼리의 인접 관계를 나타내는 행렬
•
정점의 수가 N 개라면, N * N 크기의 이차원 행렬에 한 정점과 다른 정점이 인접해 있는 경우 값을 1로 표시한다.
•
방향성이 존재하는 경우 화살표를 받는 쪽에 값을 1로 표시한다.
Adjacency List (인접 리스트)
그래프 내의 각 정점의 인접 관계를 표현하는 리스트
•
각 정점을 자신과 인접해 있는 모든 정점의 목록을 리스트로 관리한다.
