[Algorithm, JavaScript] 그래프(graph)

그래프 개요

그래프는 버텍스와 아크로 이루어져 있다.

그래프는 버텍스 간에 여러 개의 아크가 존재할 수 있는데, 다른 버텍스에서부터 오는 아크의 개수를 In-degree, 다른 버텍스로 가는 아크의 개수를 Out-degree라고 부른다. 이때 방향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로도 나뉜다.

방향 그래프와 무방향 그래프

뱡향 그래프는 무방향 그래프와 다르게 방향을 나타내는 화살표가 있다.

위 방향 그래프 그림에서 (C) 버택스는 (B)로 부터 오는 한 개의 In-degree와, (E), (D)로 가는 두 개의 Out-degree를 가지고 있다.

위 무방향 그래프 그림에서 (E) 버텍스는 (B), (D) 2개의 Degree가 있다.

 

그래프를 코드로 나타내기

 

그래프를 코드로 표현하는 방법엔 크게 두 가지가 있다.

하나는 이차원 배열을 사용하는 방법, 또 하나는 연결 리스트를 사용하는 방법인데, 서로 장단점이 있다.

 

	장점	단점
이차원 배열	구현이 간단함	공간을 많이 차지
연결 리스트	메모리를 적게 차지	구현이 복잡함

1. 이차원 배열로 나타낸 그래프

 

배열로 나타내면 다음과 같다

	A	B	C	D	E
A	0	1	0	0	0
B	1	0	0	1	1
C	0	0	0	0	1
D	0	1	0	0	1
E	0	1	1	1	0

 

 

2. 연결 리스트로 나타낸 그래프