그래프

- 그래프는 정점과 간선으로 이루어진 자료구조의 일종

- 정점 (Node, Vertex)

- 간선 (Edge) : 정점 간의 관계를 나타냄.

 

 

 

- 경로 : 정점 A에서 B로 가는 경로 

- e.g) A -> C -> D -> E -> B 

 

- 사이클 : 정점 A에서 다시 A로 돌아오는 경로

- e.g) A -> C -> B -> A

 

- 방향 있는 그래프

- 방향 없는 그래프 (양방향 그래프)

 

- 차수 : 정점과 연결되어 있는 간선의 개수

---

- 그래프 문제를 풀기 위해서는 문제에 나와있는 상황을 그래프로 모델링 후 여러가지 알고리즘을 수행해야함.

- 그래프를 저장한다는 것은 간선을 저장하는 것.

- 그래프를 저장하는 방법에는 2가지 방법이 있음.

1. 인접행렬
2. 인접리스트

- 이렇게 저장하므로써 한 정점 X와 연결된 간선을 효율적으로 찾을 수 있음.

 

1. 인접행렬

- 정점의 개수를 V라고 했을 때, V × V 크기의 이차원 배열을 이용.

- (가중치 없는 그래프인 경우) A[i][j] = 1 (i -> j 간선이 있을 때), 0 (없을 때)

- (가중치 있는 그래프인 경우) A[i][j] = w (i -> j 간선이 있을 때, 그 가중치), 0 (없을 때)

- 방향 없는 그래프 (양방향 그래프) 인 경우 양쪽 고려하여 저장.

- 공간복잡도 O(V^2)

- 시간복잡도 O(V)

 

2. 인접리스트

- 리스트를 이용해 구현

- 링크드 리스트나 길이를 동적으로 변경할 수 있는 배열을 사용.

- (가중치 없는 그래프인 경우) A[i] = i와 연결된 정점을 리스트로 포함하고 있음.

- (가중치 있는 그래프인 경우) A[i] = i와 연결된 정점과 그 간선의 가중치를 리스트로 포함하고 있음.

- 방향 없는 그래프 (양방향 그래프) 인 경우 양쪽 고려하여 저장.

- 공간복잡도 O(E)

- 시간복잡도 O(차수)

 

3. 간선리스트

- 배열을 이용해서 구현

- 간선을 모두 저장

- 라이브러리 사용 못할 때 사용하는 방식,, 거의 사용 X

---

- 그래프 탐색 방법은 2가지가 있음

1. DFS
2. BFS

1. DFS (깊이 우선 탐색)

- 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아감.

- 재귀 호출을 이용해서 구현할 수 있음.

- 인접행렬로 구현 시 시간복잡도 O(V^2)

- 인접리스트로 구현 시 시간복잡도 O(V+E)

 

2. BFS (너비 우선 탐색)

- 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식.

- 큐에 넣을 때 방문했다고 체크해야 함.

- BFS의 구현은 큐를 이용해서 할 수 있음.

- 인접행렬로 구현 시 시간복잡도 O(V^2)

- 인접리스트로 구현 시 시간복잡도 O(V+E)