Graph에 대해 알아보도록 하겠습니다.
Graph란 node와 node를 연결하는 간선을 하나로 모아놓은 Data Structure를 말합니다.
-
용어.
Vertex(정점) : 노드(node)와 같습니다.
Edge(간선) : 포인터와 같습니다.
degree(차수) : 무방향 그래프에서 인접한 정점의 수
in-degree(진입 차수) : 다른 정점에서 오는 간선의 개수
out-degree(차출 차수) : 다른 정점으로 가는 간선의 개수 -
특징
네트워크 모델
버텍스 사이에서 양쪽 방향으로 방향을 가질 수 있습니다.
Root / Leaf / 부모 / 자식 등이 없습니다. -
종류
무방향/방향 그래프 (Undirected/Directed Graph)
무방향 그래프는 아래의 그림처럼 그래프에 화살표가 없습니다!
그래서 각 간선은 양방향으로 갈 수 있습니다.
반대로 방향 그래프는 아래 그림에서 한쪽으로 화살표가 추가됩니다.
Graph의 실제 사용 예시
지하철 노선도
최단 거리
Graph Data structure의 methods
addVertex()
addEdge()
Graph Data structure의 property
Graph 이미지
Graph 구현 (이차원 배열을 사용 / 연결 리스트 사용)
pseudo code
- addVertex()
node객체를 생성자를 이용하여 만든다.
- addEdge()
연결할 node의 메모리 주소를 가리킨다.(양방향이든, 단방향이든)
command and obey