graph

Graph

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

    • 예시) 지도, 지하철 노선도의 최단 경로

Graph 종류

1. 방향 그래프

image.png

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

2. 무방향 그래프

image.png

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

Graph를 코드로 표현하는 방법

1. 이차원 배열

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

2. 연결 리스트

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

참고사이트


Written by@Heaeun
코드리뷰, TDD, 함께 자라기를 지향하는 프론트엔드 개발자입니다

GitHub