Graph

안녕하세요 〰️ 

사실 오늘은 자주 사용된다고 하는 알고리즘 중 하나인 BFS/DFS에 대해서 알아볼 예정이었는데요...

그 전에 그래프 자료구조를 잠깐 훑고 가려고 했다가,,,

제 욕심때문에 그래프 자료구조 포스팅이 되어버렸습니다 🤣

 

그래프를 순회하는 로직으로 BFS/DFS을 사용합니다.

반대로, BFS/DFS를 사용하는데에 있어서는 그래프 자료구조를 사용하죠.

그래서 BFS/DFS를 알아가기 전에, 그래프라는 자료구조를 선수로 알아가보는 단계로 준비해보았습니다 🔥

 

그래프 Graph ?

'노드node와 노드들을 연결하는 간선edge를 담고있는 자료구조'입니다.

따라서 그래프를 사용하면 연결되어 있는 객체 간의 관계를 표현할 수 있습니다.

이 때, 간선은 방향성이 있을 수도 있고, 없을 수도 있죠.

방향성을 갖는 그래프❓ 이해가 잘 안가시나요❓

아래 그림을 보면 이해에 도움이 될 것 같네요 〰️ 

 

 

그래프에서는 조금 낯선 용어들을 사용하는데요.

아래와 같이 정리를 해보았습니다.

 

✔️ 그래프 용어

node(vertex) 정점

데이터를 담는 객체 or 위치

 

edge 간선 

위치(객체)간의 관계

 

Adjacent Vertex  인접 정점 

간선으로 직접 연결되어 있는 정점

 

Cycle 사이클

단순 경로의 시작과 종료 정점이 동일한 경로

 

그래프는 실생활에서 지도나 지하철 노선도, 도로, 선수 과목 등과 매칭될 수 있습니다.

어떻게 매칭이 될지 한 번 생각해보세요 〰️ 

 

 

그래프 Graph 구현 ❗️

그래프는 아래와 같은 두 가지 방법을 통해 생성할 수 있습니다.

 

1. 인접 리스트 Adjacency list

2. 인접 행렬 Adjacency matrix

 

어떻게 구현하는지 하나씩 살펴보도록 할게요 〰️ 

 

✔️ 인접 리스트 Adjacency list

노드에 연결되어 있는 노드들을 리스트로 표현한 것입니다.

 

 

연결된 간선의 정보만을 저장 - O(E) : 공간 효율성 👍🏻

하지만, 연결되어 있는 지 확인하기 위해 O(v)의 시간을 요구합니다.

인접 리스트는 대체로 ArrayList나 LinkedList를 이용해서 표현하곤 합니다.

 

✔️ 인접 행렬 Adjacency Matrix

인접 행렬은 NxN의 크기를 같는 행렬입니다.

 

위와 같이 가중치가 없는 그래프라면 인접 행렬에 Boolean Type을 저장하게 됩니다.

0과 1의 규칙은 굉장히 간단한데요.

행(row)에 해당하는 노드가 열(column)에 해당하는 노드에 연결되어 있다면 1이라는 숫자를 저장하게 되는 것입니다.

 

 

이렇게 그래프라는 자료구조를 알아보았습니다. 

다음엔 BFS/DFS를 알아보는 시간을 갖겠습니다 〰️