Graph

기존에 알던 그래프는 x축과 y축으로 정의된 공간에서 변수 값들의 모음이다. 자료 구조에서 그래프는 거미줄이다. 각 자료들이 기준을 가지고 연결되어 있는 것이 그래프다. 인터넷도 그래프의 한 종류라 할 수 있을 것이다. 각 사이트들이 하이퍼링크를 통해 서로 연결되어 있는 구조를 가지고 있다.

Vertex(정점) 과 Edge(간선)

네트워크를 머릿속으로 그려보자 각 사이트들은 하이퍼링크를 통해 연결되어 있다. 데이터 들이 담겨있는 사이트들이 각각의 정점이고, 그 사이트들을 이어주는 하이퍼링크가 바로 간선이다. 간결한 시각화를 위해 정점은 보통 부피가 있는 점(꽉 차 있는 원)으로 표현되며 간선은 각 원을 연결해주는 선으로 표현된다.

연결이 중요!

그래프 자료 구조형에서 중요한 것은 연결이다. 어떤 정점이 다른 정점과 연결되어 있는가? 연결 되어 있다면 단방향인가 양방향인가? 단방향 이라면 어디서 어디로 연결되는 것인가? 순서가 중요한 Stack과 Queue와 비교해 봤을때 그래프는 순서가 아닌 연결 여부가 중요한 자료 이기 때문에 비선형적 구조다. 구글에서 검색을 할때 검색결과를 클릭하여 해당 사이트로 이동하지 못하고 검색 결과만 순서대로 뜬다면 어떤 의미가 있을까?

무향 그래프(Undirected graph)

양방향 연결은 다시 말해 정해진 방향이 없다는 의미이다. 방향은 중요하지 않게 된다. 하지만 단방향 연결은 방향이 중요하다!

진입차수, 진출차수

정점은 여러개의 연결을 가질수 있다. 이 때 들어오는 간선의 갯수를 진입차수라 하며 나가는 간선의 갯수를 진출차수라 한다. 무향 그래프에선 구별할 수 없다. 이 때는 정점에 인접한 정점의 수를 가르켜 정점 차수라 말한다.

인접

간선으로 직접적으로 연결되어 있으면 인접한 정점이라 한다. 인접 정점을 건너 연결되면 간접적으로 연결된 것

자기 루프

정점에서 출발하는 간선이 바로 자기 자신에게 돌아온다. 이때 간선은 다른 정점을 거치지 않는다. 자기 루프의 대상인 정점이 선형 구조의 자료로 구성되어 있다면 의미가 있게 된다. 원형 queue로 이루어진 그래프를 생각해보면 분명하다.

사이클

한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 존재한다.

가중치

간선은 가중치를 가질 수 있다. 예를 들어 한 정점에서 출발하여 같은 정점에 도착하는 2개의 루트가 있다고 가정해 보자 간선의 가중치를 주어 간선을 통과하는데 걸리는 시간을 나타낸다면 최단 시간내의 도착하는 루트를 선택하기 위해선 이 가중치를 고려해야 할 것이다. 가중치는 여러 개념을 나타낼 수 있다.

그래프의 표현 방식

인접 행렬

그래프는 행렬로 나타낼수 있다. 자바스크립트에선 이차원 배열을 이용하게 된다. 배열은 정점의 수를 길이로 가지게 되며, 배열을 구성하는 각 인덱스의 내부 배열은 정점의 수를 길이로 가지며 0과 1로 구성된다.

//정점이 3개인 그래프의 인접 행렬
const matrixGraph = [ 
[0, 0, 1], 
[0 ,1, 0], 
[1, 0, 0]
]

0은 연결되지 않았다는 의미이고 1은 연결됬다는 의미이다. 그래프에서 순서는 큰 의미를 가지지 않는다. 다만 구분의 편의를 위해 인덱스 번호로 구분하도록 하자

• matrixGraph[0]의 2번 인덱스는 1이다. 이는 첫 번째 정점에서 3번째 정점 방향으로 간선이 연결되었다는 의미이다. 진출차수는 1개이다.
• matrixGraph[1]의 1번 인덱스는 1이다. 이는 두 번째 정점에서 2번째 정점 방향으로 간선이 연결되었다는 의미이다. 인접 행렬에선 자기 루프도 표현할 수 있다! 진출차수는 1개이다.
• matrixGraph[2]의 0번 인덱스는 1이다. 이는 세 번째 정점에서 1번째 정점 방향으로 간선이 연결되었다는 의미이다. 정점 1과 정점 3은 양방향으로 연결되어 있다. 진출차수는 1개이다.

인접 행렬은 정점간 관계를 파악하게 매우 용이하다는 장점이 있다.

인접 리스트

인접 행렬에서 사용한 예를 인접 리스트로 표현해 보도록 하자. (각 정점의 이름은 해당 정점의 배열내의 순서)

• 정점 1 → 정점 3 → 정점 1
• 정점 2 → 정점 2 → ...
• 정점 3 → 정점 1 → 정점 3

인접 리스트는 인접 행렬에 비해 메모리를 적게 사용한다. 인접 행렬은 연결 여부에 대해 모든 경우의 수를 저장하기 때문이다. 단순하게 생각해 보면 인접 행렬은 정점의 갯수의 제곱개의 메모리 공간을 요구한다. 또한 인접 리스트는 사이클을 파악하기 쉽다.

그래프의 탐색 방법은 대표적으로 BFS, DFS가 있다. 해당 탐색 방법은 트리 구조에서 자세히 알아보도록 하자.