<자료구조> 그래프(Graph)

ming·2023년 3월 26일

목록 보기

10/12

그래프란?

정점(Node, Vertex)과 간선(Edge,연결된 정점간의 관계를 표현)으로 이루어진 자료구조(Cyclic).
G = (V,E)로 나타낸다.

무방향 그래프

- 간선에 방향이 없는 그래프(양방향 이동 가능)
- 정점(vertex): {A,B,C,D,E}
- 간선(edge) 표현: (A,B)=(B,A)/(A,C)=(C,A)/(A,D)=(D,A)/(B,D)=(D,B)/(D,E)=(E,D)/(C,E)=(E,C)
- 인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점.
- 정점의 차수(Degree): 하나의 정점에 인접한 정점의 수
(A: 3개(B, C ,D)/ B: 2개(A, D)/ C: 2개(A, E)/ D: 3개(A, B, E)/ E: 2개(C, D))
- 모든 정점 차수의 합 = 그래프 간선의 수 2배

방향 그래프

- 간선에 방향이 있는 그래프(해당 방향으로만 이동 가능).
- 간선 표현: <A,B>!=<B,A>
- 진입 차수(In-degree): 외부에서 오는 간선의 수.
(A: 1개(E), B: 1개(A), C: 1개(B), D: 1개(C), E: 1개(D))
- 진출 차수(Out-degree): 외부로 나가는 간선의 수.
(A: 1개(B), B: 1개(C), C: 1개(D), D: 1개(E), E: 1개(A))
- 경로 길이(Path length): 경로를 구성하는데 사용된 간선의 수.
- 단순 경로: 경로 중에서 반복되는 정점이 없는 경우.
- 사이클(Cycle): 단순 경로의 시작 정점과 끝 정점이 동일한 경우.

가중치 그래프

간선에 값이 있는 그래프(이동 비용)

완전 그래프

모든 정점이 서로 연결되어 있는 그래프
정점이 N개일 경우, 간선의 수는 N(N-1)/2개

그래프 탐색

목적 : 모든 정점을 1번씩 방문

깊이 우선 탐색, DFS(Depth First Search)

각 노드에 방문했는지 여부를 체크할 배열과 스택 이용하여 구현.
스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아간다.
dfs(x) = x를 방문.

너비 우선 탐색, BFS(Breath First Search)

각 노드에 방문했는지 여부를 체크할 배열과 큐 이용하여 구현.
모든 가중치가 1일 경우, 최단거리 찾는 알고리즘이 됨.

그래프 구현

인접 행렬(Adjacency Matrix)- 2차원 배열 이용

간선 정보의 확인과 업데이트가 빠르다. O(1).
구현하기 쉽다.
필요 공간 : V^2
인접 행렬에서 그래프의 정점은 행과 열을 나타낸다. 즉, 그래프에 N개의 정점이 있는 경우 인접 행렬의 크기는 NxN.

가중치그래프는 아래 그림(가중치는 한 정점에서 다른 정점으로 '1'이 아닌 간선이 있을 때마다 지정된다.)