🐢 6. Graphs

🫧 그래프

• 정점(V, vertex)과 정점들을 연결하는 간선(E, edge) 으로 이루어진 자료구조이다.
• 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조이다.
• 그래프는 여러개의 고립된 부분 그래프로 구성될 수 있다.
• 그래프는 G = (V,E) 로 표현한다.(V는 그래프에서 정점의 집합을 나타내고 E는 간선의 집합을 말한다.)
• 그래프는 네트워크 모델이다.
• 2개 이상의 경로가 가능하다.
  • 즉, 정점(노드)들 사이에 무방향/방향에서 양방향 경로를 가질수가 있다.
• self-loop뿐만 아니라 loop/circuit 모두 가능하다.
• 루트 노드라는 개념이 없다.
• 부모-자식관계라는 개념이 없다.
• 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
• 간선의 유무는 그래프에 따라 다르다.
• 그래프는 순환 혹은 비순환이다.

❤️ 1. 무방향 그래프

무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프 이며, 양 방향으로 이동이 가능하다.

아래 그림과 같은 무방향 그래프에서 정점 A와 B를 나타낼 때 (A,B) 또는 (B,A) 로 표현한다. 두 표현은 동일한 의미이다.

❤️ 2. 방향 그래프

두 정점을 연결하는 간선에 방향이 존재하는 그래프이며, 간선의 방향으로만 이동할 수 있다.

아래 그림같은 경우 A -> C 방향으로만 이동이 가능하다. 이런 그래프는 <A,C> 로 표현하는데 <C,A> 로 표현하면 C -> A 방향으로만 이동가능하다는 것으로 의미가 달라진다.

🫧 인접 리스트

그래프의 노드들을 리스트로 표현한것이다.

주로 정점의 리스트 배열을 만들어 관계를 설정하여 구현한다.

• 모든 정점을 인접리스트에 저장하고 각 정점(노드)에 인접한 정점들을 리스트로 만드는 방법이다.
• 공간은 간선의 개수만큼 필요하다.
  • 정점과 연결된 간선의 개수만큼 리스트요소들이 저장되기 때문이다. 위 그림에서 살펴보면 정점1과 정점 2와 5를 연결하는 간선의 개수만큼 요소가 저장되어 있는걸 확인할 수 있다.

🫧 인접 행렬

N x N 행렬로써 matrix[i][j] = 1이면 정점 i에서 j로 가는 간선이 존재하고 matrix[i][j] = 0이면 정점 i에서 j로 가는 간선이 존재하지 않는다는 의미이다.

단, 가중치 그래프의 경우 matrix[i][j] > 0이면 i에서 j로 가는 간선이 존재한다고 볼 수 있다.

• 인접 행렬은 boolean 타입의 행렬 또는 0과 1로 구성된 정수 타입의 행렬을 사용할 수 있다.
• 정점의 개수가 N인 그래프를 인접행렬로 표현시 간선의 수와 무관하게 n^2개의 메모리 공간이 필요하다.
• 무방향 그래프를 인접행렬로 표현한다면 이 행렬은 대칭 행렬이 된다. 물론 방향그래프는 대칭행렬이 되지 않을수도 있다.
• 인접리스트를 사용한 그래프 알고리즘(Ex. 너비 우선 탐색) 또한 인접행렬에서 사용이 가능하다. 하지만, 인접행렬은 효율성이 떨어진다.
  • 인접 리스트는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만 인접 행렬에서는 인접한 노드를 찾기 위해 모든 노드를 전부 순회해야 한다

🫧 그래프 탐색

❤️ 1. 깊이 우선 탐색(DFS, Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법이다.

• 넓게 탐색하기 전에 깊게 탐색하는 방법이다.
• 모든 노드들을 탐색해야하는 경우에 이 방법을 사용하는것이 좋다.
  • 너비 우선 탐색에 비해 상대적으로 간단하다.

❤️ 2. 방향 그래프

루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법

• 깊게 탐색하기 전에 넓게 탐색하는 탐색방법
• 두 노드사이의 최단경로 혹은 임의의 경로를 찾고 싶을때 사용한다