[Data Structure] 그래프(Graph)

본 포스트는 데이터 구조 그래프(Graph)에 대해 공부한 내용을 정리한 것입니다.

 

그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 데이터 구조로,

아이템들과 이들 사이의 연결 관계를 표현하는 구조입니다.

 

그래프는 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현할 때 유용합니다!

 

그럼 본격적으로 그래프에 대해 알아보도록 하겠습니다.

---

그래프의 유형

무향 그래프 (Undirected Graph)

• 두 정점(노드) 사이의 간선(엣지)이 방향성을 가지지 않는 그래프
• 간선이 정점 A에서 B로 가는 것이 아니라, 정점 A와 정점 B가 단순히 연결만 되어 있는 것
  • ex) 친구 관계를 나타내는 그래프 (A와 B가 친구라면  B와 A도 친구)

무향 그래프

 

유향 그래프 (Directed Graph)

• 두 정점 사이의 간선에 방향이 있는 그래프
• 간선이 정점 A에서 정점 B로 향하거나 정점 B에서 정점 A로 향하는 것 
  • ex) 웹 페이지의 링크 구조 (A 페이지가 B 페이지로 링크를 거는 것)

유향 그래프

 

가중치 그래프 (Weighted Graph)

• 각 간선에 가중치(비용, 거리 등)가 부여된 그래프
• 가중치는 보통 간선의 값을 나타내며, 이 값은 그래프의 연산(예: 최단 경로 찾기)에 중요
  • 도로 네트워크에서 도로의 길이나 교통량을 나타내는 그래프 (도로의 길이가 가중치가 됨)

가중치 그래프

 

사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph)

• 유향 그래프의 일종으로, 순환 구조가 존재하지 않는 그래프
• 시작 정점에서 시작하여 다시 시작 정점으로 돌아오는 경로가 존재하지 않음 
  • ex) 작업의 의존성 관계를 나타내는 그래프 (특정 작업이 완료되어야만 다음 작업 시작 가능)

사이클 없는 방향 그래프

---

인접 리스트

그래프하면 인접 리스트를 빼놓을 수 없겠죠!

코딩 테스트 단골 손님인 만큼 저희는 인접리스트를 만들 일도 굉장히 많습니다.

 

그러나 코딩테스트에서 구현하는 인접 리스트와, 현업에서 구현하는 인접 리스트가 다르다는 사실을 알고 계셨나요?

그 차이를 한번 보도록 하죠!

 

코딩 테스트에서 사용되는 인접 리스트 (인접 행렬, 인접 리스트)

• 인접 행렬 : 2차원 배열을 이용해서 간선 정보를 저장
  • 장점: 연결 여부를 한번에 탐색 가능
  • 단점: 메모리 낭비가 심함

• 인접 리스트 : 각 정점마다 해당 정점으로 나가는 간선 정보를 저장
  • 장점: 메모리 활용이 효율적
  • 단점: 연결 정보 확인이 어려움

 

현업에서 사용되는 인접 리스트

현업에서는 링크드 리스트로 구현하는 것이 정석입니다.

WHY? 삽입, 삭제가 많기 때문!!

 

링크드 리스트의 삽입, 삭제에 대한 시간 복잡도는 모두 O(1)이므로 매우 유용한 것이죠~