Data structure - Graph

마데슾 : My Dev Space·2019년 12월 9일
0

Graph

  • 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
  • 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.
    - 예시) 지도, 지하철 노선도의 최단 경로

Graph 종류

1. 방향 그래프

image.png

  • In-degree : 다른 버텍스에서부터 오는 아크의 개수
  • Out-degree : 다른 버텍스로 가는 아크의 개수

2. 무방향 그래프

image.png

  • Degree : 양쪽으로 모두 연결되어 있는 아크의 개수

Graph를 코드로 표현하는 방법

1. 이차원 배열

image.png
공간을 많이 차지하지만 간단하다.

2. 연결 리스트

image.png
공간은 적게 차지하지만 복잡하다.

profile
👩🏻‍💻 🚀

0개의 댓글