[자료구조, 자바스크립트] 그래프

그래프

• 객체(노드)간의 연결을 시각적으로 표현한 것이다.
• 꼭 길찾기에 한정되는 것이 아니라 다양하게 적용된다.

 

용어 정리

그래프 들어가기 전에 용어 정리부터 하자

그래프

• 정점(vertex): 객체, 노드이다. 빅오 분석시 V로 표기한다. 그림의 동그라미 부분
• 간선(edge): 노드간의 연결을 의미한다. 빅오 분석시 E로 표기한다. 그림의 선 부분
• 정점차수(degree of vertext): 노드에 연결된 간선의 갯수이다.
• 가중치(weight): 간선에 대한 값을 의미한다. 표현이 조금 추상적인데 그 이유는 문맥에 따라 다양한 것을 표현하기 때문이다. 예를 들어 방향이 존재하는 간선의 경우 노드 A 부터 B까지 이동하는데 필요한 거리를 나타내는데 사용된다. 물론 방향이 존재하지 않는 경우에도 사용될 수 있다.

또 그래프에는 간선에 방향이 있는 그래프와 간선에 방향이 없는 그래프로 나뉜다. 다른 표현으로 무지향성 그래프 (undirected graph), 지향성 그래프(directed graph) 라고 부른다.

 

 

무지향성 그래프

• 무지향성 그래프(undirected graph): 간선에 방향이 없다. 방향없이 상호 연결을 암시하는 경우에 사용된다

지향성 그래프

• 지향성 그래프(directed graph): 간선에 방향이 있는 그래프다. 일방적인 연결이 있는 경우에 사용된다.

 

어디에 쓰일까

그럼 그래프는 어디에 쓰일까? 대표적으로 지도가 있고, 더 다양한 경우에 쓰인다. 위 용어를 기준으로 실제 적용사례를 간단히 살펴보자.

적용 사례	정점(Vertex, 노드)	간선(Edge, 연결)
웹사이트	웹 페이지	링크
지도	교차로	도로
회로	부품	배선
소셜미디어	사람	친구 맺기
전화	전화번호	전화선

 

그럼 위 용어정리 내용을 기준으로 간선의 방향이 있는 그래프와 간선의 방향이 없는 그래프의 예는 뭘까?

적용 사례	간선 방향	가중치
친구 맺기	없음	친밀도
지도	도로 방향	거리

 

 

코드

가장 흔한 방법으로 인접 행렬과 인접 리스트 방식을 사용할 수 있다. 코드는 인접리스트 형태로 구현한다.

• 인접리스트: 정점을 노드의 키로 사용하며 해당 노드의 이웃들을 리스트에 저장한다.
• 인접행렬: 행렬의 각 항목이 두 정점 간에 연결을 나타내는 V x V 행렬이다

인접 행렬

인접 리스트

무지향성 그래프(간선 방향 X)

무지향성 그래프 코드

지향성 그래프(간선 방향 O)