Graph

그래프는 저장된 자료들사이의 관계를 나타내기를 위한 구조.

 

정점(Vertex) : 자료를 나타내는 단위로 리스트나 트리의 노드와 같은 의미.

 

간선(Edge) : 정점을 연결하는 선을 의미하며 자료사이의 관계를 나타냄.

 

가중치(Weight) : 한 정점에서 다른 정점으로 이동하는데 필요한 자원을 나타냄. 즉, 간선의 값. 가중치를 표시하지 않는다면 1로 생각해도 무방.

 

차수(Degree): 그래프에 연걸된 간선 수. 노드사이의 모든 연결 간선수를 나타냄.

- 입력 차수 : 방향성 그래프일때 노드로 들어오는 간선수.

- 출력 차수 : 방향성 그래프일때 노드에서 나가는 간선수. 

 

단순 경로 : 그래프의 한 정점에서 다른 정점으로의 경로 중, 모든 정점을 단 한번씩만 방문하는 경로.

 

사이클(Cycle) : 단순 경로중 출발점과 도착점이 같은 경우.

 

인접 행렬 : N개의 정점을 가지는 그래프의 모든 간선을 N * N 행렬에 표시하는 방법. 정점 i 에서 정점 j로 가는 간선을 행렬 i,j 에 표시하는 방식으로 표현한다.

 

인접 리스트 : 연결리스트나 벡터를 이용해 각 정점의 연결을 표시하는 방법. 한 정점에서 연결된 모든 정점을 저장한다. 연결 정점을 나타내는 방법은 다양함. 직접적인 정점의 포인터로 나타낸 경우는 간선 가중치가 없는 경우 or 연결된 정점으로의 간선 정보로 나타내는 경우는 간선에 가중치가 있는 경우로 보면 되겠다.