[자료구조] Graph

Graph란??

그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.
-wikipedia

• 그래프는 트리와 비슷하게 정점과 간선으로 구성되어 있다.
• 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조
• 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다.
• 그래프는 노다 간에 여러 개의 간선이 존재할 수 있다.
• 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프( = 양방향 그래프)로 나눌 수 있다.

Vertex & Edge

Vertex(정점)

• 노드라고 불리며, 그래프를 형성하는 기본 단위이다.
• 정점은 분할할 수 없는 객체이자 "점"으로 표현되는 위치, 사람, 물건 등이 될 수 있다.

Edge(간선)

• 정점을 연결하는 선을 의미한다. 관계, 경로 등이 될 수 있다.
• 단방향 간선 : 순서가 정해진 두 정점의 쌍(Ex: 짝사랑, 한쪽으로 밖에 갈 수 없다, 나 혼자 인스타를 팔로우 한 상황)
• 양방향 간선 : 순서가 없는 두 정점의 쌍(Ex: 사랑, 양쪽에서 갈 수 있다, 맞팔을 한 상황)

Degree(차수)

• 정점에 연결된 간선의 개수를 의미한다.
• indegree(진입 차수) : 방향 그래프에서 한 정점을 기준으로 외부에서 들어오는 간선의 개수
• outdegree(진출 차수) : 방향 그래프에서 한 정점을 기준으로 외부로 나가는 간선의 개수

가중치

• 정점과 정점 사이에 드는 비용
• 간선에 표기된 숫자를 의미하며, 가중치가 없는 그래프일 경우 모두 동일한 가중치를 가진다.

 

참고

https://devel-yong.tistory.com/13

https://en.wikipedia.org/wiki/Graph_theory