그래프(Graph)

그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용한다.

노드(Node) : 위치를 말한다. 정점(Vertex)이라고도 함.

간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨.(link or branch)

인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드)

 

무방향 그래프

; 방향이 없는 그래프

  간선을 통해 노드는 양방향으로 갈 수 있음

  보통 노드 A,B가 연결되어 있을 경우, (A, B) 또는 (B, A)로 표기

방향 그래프

; 간선에 방향이 있는 그래프

  보통 노드 A,B가 A->B로 가는 간선으로 연결되어 있을 경우, <A, B> 로 표기. <B, A> 는 B -> A로 가는 간선이 있을때에 표기.

가중치 그래프 또는 네트워크

; 간선에 비용 또는 가중치가 할당된 그래프

그래프와 트리의 차이

	그래프	트리
정의	노드와 노드를 연결하는 간선으로 표현되는 자료 구조	그래프의 한종류, 방향성이 있는 비순환 그래프
방향성	방향 그래프, 무방향 그래프 둘다 존재함	방향 그래프만 존재함
사이클	사이클 가능함, 순환 및 비순환 그래프 모두 존재함	비순환 그래프로 사이클이 존재하지 않음
루트 노드	루트 노드 존재하지 않음	루트 노드 존재함
부모/자식 관계	부모 자식 개념이 존재하지 않음	부모 자식 관계가 존재함