알고리즘 - 그래프 개념

자료구조의 종류
사물이나 개념의 연결관계를 표현
정점과 간선으로 이루어져 있으며 간선은 정점간의 관계를 나타내는데 사용.
G = (V,E)

경로 : 한 정점에서 특정 노드로 이동하는 방법
사이클 : 경로중에서 시작노드와 도착노드가 같은 방법
단순경로와 단순 사이클 : 같은 정점을 두번 이상 방문하지 않는 경로와 사이클
방향이 있는 그래프 : 특정 방향으로만 이동이 가능한 그래프
방향이 없는 그래프 : 이동에 대한 방향 제약이 없는 그래프
다중 그래프 : 두 정점 사이에 두개 이상의 간선이 있는 그래프
루프 : 시작점과 끝점이 같은 간선
가중치 : 이동하는데 필요한 시간등 수치가 있는 그래프
차수 : 정점과 연결되어 있는 간선의 개수
방향이 있는 그래프의 차수 : 나가는 간선 / 들어오는 간선의 개수를 따로 센다.

 

그래프의 표현
1. 인접행렬
정점의 개수가 V일 때 V*V크기의 이차원 배열 이용.
행렬 A[i][j] = 1(i -> j로의 간선이 있을 때), 0(간선이 없을 때)
  123
1 010
2 101
3 011
장점 : 구현이 쉬움
단점 : 없는 간선까지 저장하여 비효율

가중치가 있는 그래프는 1,0 대신 가중치를 1 위치에 넣으면 된다.

2. 인접리스트
A[i] = i와 연결된 정점이 링크드 리스트로 저장
A[1] = 2
A[2] = 1 3
A[3] = 3 2
장점 : 필요한 만큼 공간 사용
단점 : 구현하는데 시간이 오래 걸리고 디버깅 어려움

그래프의 탐색
DFS - 깊이 우선 탐색 -> 스택 사용
BFS : 너비 우선 탐색 -> 큐 사용