그래프

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

그래프란?

노드(정점)와 간선(브랜치)으로 이루어진 자료구조이다.

 

그래프의 탐색이란?

하나의 노드를 시작으로 다수의 노드를 방문 하는 것을 말하며, 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다라고 표현한다.

간단하게 도시를 노드, 도로를 간선이라고 생각하면 이해하기 쉽다.

 

그래프의 종류

1. 방향 그래프

 -. 간선에 방향이 있는 그래프로 간선 그래프 방향으로만 갈 수 있다.

2. 무방향 그래프

 -. 간선에 방향이 없는 그래프로 노드는 양방향으로 갈 수 있다.

3. 가중치 그래프

 -. 노드를 이동할 때 드는 비용, 또는 가중치가 할당된 그래프

4. 완전 그래프

 -. 모든 노드가 간선으로 연결되어 있는 그래프

 

그래프의 표현

프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데, 코딩 테스트에는 아래 두 방식이 모두 필요하다.

 

1. 인접 행렬 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식

장점 - 구현이 비교적 간단하며 2차원 배열안에 모든 간선 정보를 담고 있기 때문에 배열의 위치를 확인하면 두 점의에 대한 연결 정보를 조회할 때 O(1)의 시간 복잡도를 가진다.

단점 - 모든 정점에 대한 간선 정보를 대입해야 하므로 O(n2)의 시간 복잡도 소요, 무조건 2차원 배열이 필요하므로 필요 이상 공간이 낭비된다.

 

2. 인접 리스트 - 리스트로 그래프의 연결 관계를 표현하는 방식

장점 - 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능하다. (n: 간선의 갯수), 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다.

단점 - 구현이 비교적 어려우며 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다.(배열보다 검색 속도 느림)

 

 

참고 자료

https://m.blog.naver.com/occidere/220923695595

[그래프] 쉽게 쓴 그래프 알고리즘 기초 (2018.03.06 수정완료)

https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?