그래프

1. 개념

• 원소간의 관계를 표현한 자료구조
• 그래프는 연결할 객체를 나타내는 정점(Vertex)과 객체를 연결하는 간선(Edge)의 집합으로 구성
• 정점(Vertex) : 노드(node)라고도 하며 정점에는 데이터가 저장됨
• 간선(Edge) : 정점을 연결하는 선으로 link, branch라고도 불림
• 인접 정점(adjacent Vertext) : 간선에 의해 직접 연결된 정점
• 그래프에서 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때 두 정점 Vi와 Vj를 인접(adjacent)한다 하고, 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 말함
• 그래프 G를 G = (V, E)로 정의하는데 V는 정점의 집합, E는 간선들의 집합을 의미
• 차수(Dgree) : 무방향 그래프에서 정점에 부속되어 있는 간선의 수
• 진입차수(in-degree) : 방향그래프에서 외부에서 들어오는 간선의 수
• 진출차수(out-degree) : 방향그래프에서 외부로 향하는 간선의 수
• 경로(Path) : 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
• 경로 길이(Path Length) : 경로를 구성하는 간선의 수
• 단순 경로(Simple Path) : 모두 다른 정점으로 구성된 경로(한붓그리기 처럼 같은곳을 지나지 않는 경로)
• 사이클(Cycle) : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경우

 

2. 그래프의 종류

1) 무방향 그래프

• 두 정점을 연결하는 간선에 방향이 없는 그래프
• 무방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi, Vj)로 표현
  • 이때 무방향 그래프에선 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미함
• V(G1) =
• E(G1) = {(A,B), (A,D), (B,C), (B,D), (C,D)}
  

2) 방향 그래프

• 간선에 방향이 있는 그래프, 간선의 방향으로만 이동할 수 있음
• 방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 <Vi, Vj>로 표현
• Vi를 꼬리(tail), Vj를 머리(head)라고 함
  • 이때 <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선임
• V(G2) =
• E(G2) = {<A,B>, <A,D>, <B,C>, <B,D>, <C,D>}
  

3) 완전 그래프(Complete Graph)

• 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프
• 정점이 N개인 완전그래프에서 무방향 그래프의 최대 간선수는 N(N-1) / 2이고 방향그래프의 최대 간선 수는 N(N-1)
  

4) 부분 그래프(Subgraph)

• 기존의 그래프에서 일부 정점이나 간선을 제외한 그래프
• 말 그대로 그래프의 일부분
  

5) 가중치 그래프(Weighted Graph)

• 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프, 두 점을 이동할 때 비용이 드는 그래프
  

6) 유향 비순환 그래프(DAG, Directed Acyclic Graph)

• 방향 그래프에서 사이클이 없는 그래프
  

7) 연결 그래프(Connected Graph)

• 무방향 그래프에 떨어져 있는 정점이 없어서 모든 정점쌍에 대해 항상 경로가 존재하는 그래프
• 트리(Tree)가 연결 그래프의 한 종류
  

8) 단절 그래프(Disconnected Graph)

• 무방향 그래프에서 연결되지 않은 정점이 있어서 특정 정점 사이에 경로가 존재하지 않는 그래프
  

9) 순환그래프(Cycle)

단순 경로에서 시작정점과 도착정점이 동일한 그래프(A에서 시작해서 A에서 끝나는게 가능한 그래프)

10) 비순환그래프(Acycliic Graph)

순환 그래프를 제외한 그래프로 사이클이 없는 그래프

 

3. 그래프 구현 방법

그래프 구현은 인접행렬과 인접리스트를 이용해 구현할 수 있음

1) 인접행렬로 그래프 구현

• 무방향 그래프를 인접행렬로 구현하면 아래 그림과 같음
• 정점들을 배열의 인덱스로 표현하고, 두 정점이 연결되어 있다면 1로, 연결되어 있지 않다면 0으로 표현
• 자기 자신으로 연결되는 loop가 없으므로 배열의 대각선은 모두 0이다. (예를 들어 A->A 연결 없음)
  
  
• 방향 그래프 인접행렬로 구현하면 아래 그림과 같음
  - 정점들을 배열의 인덱스로 표현하고, 해당 정점에서 다른 정점으로 가는 간선이 있다면 1로, 없다면 0으로 표현
• 방향을 주의해서 구현해야 함
  
  

2) 인접리스트로 그래프 구현

• 무방향 그래프를 인접리스트로 구현하면 아래 그림과 같음
• 각 정점을 head로 시작해 인접한 노드들을 전부 연결리스트로 연결해주면 됨
  
  
• 방향 그래프를 인접리스트로 구현하면 아래 그림과 같음
• 각각 정점을 head로 시작해 갈수있는 노드를 전부 연결리스트로 연결해주면 됨
  
  

3) 인접행렬 vs 인접리스트

그래프의 연결이 많지 않은 희소그래프인지, 빽빽하게 연결되어있는 밀집그래프인지에 따라 다름

희소 그래프(sparse graph)

• 정점은 1000개가 있는데 간선은 5개뿐인, 간선의 수가 적은 그래프
• 인접리스트로 구현한다면 1005개의 노드만 있으면 충분함
• 반면 인접행렬로 구현한다면 겨우 5개의 연결을 나타내려고 1000 * 1000 행렬을 사용해야 함

밀집 그래프(dense graph)

• 정점이 1000개 있는데 간선이 2000개 있는 그래프처럼 간선의 수가 많은 그래프
• 만약 밀집 그래프를 구현한다면 인접행렬이 더 유리함, 행렬의 인덱스로 O(1)시간에 접근이 가능하므로
• 반면 인접리스트로 구현한다면 해당 노드를 찾을때까지 탐색을 해야하므로 접근성이 좋지 않아짐

 

※ 데이터가 적다면 인접리스트로, 많다면 인접행렬로
코딩테스트같은 상황에서는 데이터 양이 많지 않기때문에 대부분 인접리스트로 해결
단, 애초에 문제가 인접배열식으로 구현되어 있다면 그땐 그대로 인접배열 방식으로 사용하면 됨

데이터가 아주많은 상용프로그램이라면 인접행렬 사용을 고려해야 함

 

4. 그래프 탐색

• 정점의 구성뿐 아니라 간선의 연결에도 규칙이 존재하지 않아서 탐색이 복잡함
• DFS와 BFS 두가지 방법 사용

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

• 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 다른 정점으로 계속 나아가는 방법
• 연결할 수 있는 정점이 있을때까지 계속 연결하다가 더 이상 연결된 정점이 없으면 바로 전단계 정점으로 돌아감

너비 우선 탐색(Breadth First Search : BFS)

• 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아감
• queue를 이용해 탐색순서를 설정할 수 있음

BFS와 DFS 알고리즘 : https://smallpants.tistory.com/88

 

 

 

 

※ 참고 문헌
https://leejinseop.tistory.com/43