- 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조
- 오일러에 의해 착안
- 정점(vertex)과 정점간의 관계 간선(edge)로 표현
- 방향 그래프 vs 무방향 그래프
: 표현 (0, 1) vs <0,1>
: 무뱡향 그래프에서 차수(degree)는 하나의 정점에 인접한 정점의 수
: 방향 그래프에서 외부에서 오는 간선의 수를 진입 차수(in-degree), 외부로 향하는 간선의 수를 진출 차수(out-degree)
- 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크
- 경로 중에서 반복되는 간선이 없을 경우에 이러한 경로를 단순 경로, 단순경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클(cylcle)
- 모든 정점쌍에 대하여 하상 경로가 존재하면 연결 그래프, 모든 정점이 서로 연결되어 있는 그래프는 완전 그래프
'Major > Data structures' 카테고리의 다른 글
자료구조 - 해싱 (0) | 2015.11.14 |
---|---|
자료구조 - 신장 트리 (0) | 2015.11.13 |
자료구조 - 우선순위큐(힙) (0) | 2015.11.12 |
자료구조 - 이진트리 (0) | 2015.11.12 |
자료구조 - 트리 (0) | 2015.11.12 |