✔ 그래프(Graph)
- 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계 표현.
- 그래프(Graph) : 정점의 집합과 간선의 집합으로 구성된 자료 구조
- V : 정점의 개수, E : 간선의 개수, 무향 그래프.
- V개의 정점을 가지는 그래프는 최대 [(V * (V-1))/ 2]의 간선이 가능.
- 선형, 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소 표현에 용이.
◾ 그래프 용어
정점(Vertex): 그래프의 구성 요소로 하나의 연결점.간선(Edge): 두 정점을 연결하는 선.차수(Degree): 정점에 연결된 간선의 수.인접(Adjacency): 두 개의 정점에 간선이 존재(연결됨)하는 경우.- 완전 그래프에 속한 임의의 두 정점은 서로 인접.
경로(Path): 어떤 정점 A에서 다른 정점 B로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것.- 단, 같은 정점을 거치지 않는 간선들의 sequence.
- 경로는 여러가지일 수 있음.
싸이클(Cycle): 경로의 시작 정점과 끝 정점이 같음.
◾ 그래프 유형
무향 그래프(Undirected Graph): 방향이 없음. 양방향.유향 그래프(Directed Graph): 방향이 있음. 단뱡향.가중치 그래프(Weighted Graph): 간선에 정보(값)을 부여한 그래프.사이클 없는 방향 그래프 그래프(DAG, Directed Acyclic Graph): .완전 그래프: 정점들에 대해 가능한 모든 간선들을 가진 그래프.부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프.트리: 아래 제한을 가지는 그래프.- 각 노드는 최대 하나의 부모 노드 존재.
- 각 노드는 자식 노드가 없거나 하나 이상 존재.
- 두 노드 사이에는 유일한 경로 존재.
◾ 그래프 표현
- 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해 결정.
- 정점 중심 문제 해결 : Prim(MST)
인접 행렬(Adjacent Matrix): [V X V] 크기의 2차원 배열을 이용해 간선 정보 저장.인접 리스트(Adjacent List): 각 정점마다 다른 정점으로 나가는 간선의 정보 저장.
- 간선 중심 문제 해결 : Kruskal(MST)
간선 리스트(Edge List): 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장.
1. 인접 행렬
2. 인접 리스트
3. 그래프 탐색(순회)
순회: 비선형적인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것.- 너비 우선 탐색(Breadth First Search, BFS)
- 깊이 우선 탐색(Depth First Search, DFS)
◾BFS(Breadth First Search)
- 너비 우선 탐색 : 탐색 시작점의
인접한 정점들을 차례로 방문. 방문한 정점을 시작점으로 다시 인접한 정점 방문.- 인접한 정점들에 대해 탐색 후 차례로 다시 너비 우선 탐색 진행.
- 선입 선출 형태의
큐활용.
// G : 그래프.
// v : 시작 정점.
void BFS(G, v){
Queue<T> q = new Queue<T>();
q.offer(v);
// v 방문 예약
while (!q.isEmpty()){
T data = q.poll();
// data 방문
for (data와 연결된 모든 간선){
q.offer(data의 인접 정점);
// 인접 정점 방문 예약.
}
}
}◾DFS(Depth First Search)
- 깊이 우선 탐색 : 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색. 더이상 갈 곳이 없다멵 가장 마지막 갈림길로 돌아가 다른 방향 탐색.
- 가장 마지막에 만난 갈림길의 정점으로 돌아가 깊이 우선 탐색 반복..
재귀적구현 또는 후입 선출 형태의스택활용.
// G : 그래프.
// v : 탐색 정점
void DFS(v){
// v 방문 설정.
for (v와 연결된 모든 간선){
if (아직 방문하지 않은 정점 newV){
DFS(newV)
}
}
}
후라이드 치킨