- 그래프(vertex, edge, node, arc)
- 종류: Undirected, Directed, Weighted Graph
- 표현방식: 인접행렬(Adjacency Matrix), 인접리스트(Adjacency List)
사물을 정점(vertex) 또는 노드(node) 와 간선(edge)로 표현하기 위해 사용
지하철노선도라고 생각 여러 경로가 있는데 그중 최단 거리를 알아내기 위해 사용
용어정리
노드 (node) : 위치를 말함 정점(vertex)라고도 함
엣지 (edge) : 노드를 연결한 선 (link 또는 branch 라고도 함)
인접 정접( adjacent vertex) : 간선으로 직접 연결된 정점(또는 노드)
vertex에는 degree (차수) 라는 게 존재한다. 무방향 정점에 인접한 정점의 수
in-degree / out-degree : 외부에서 오는 간선 / 내부에서 외부로 향하는간선의 수 (방향그래프)
path length : 경로를 구성하기 위해 사용된 간선의 수
simple path : 처음 정점과 끝정점을 제외하고 중복된 정점이 없는 경로
(ex. A-B-C / 단순 경로 ,, A-B-C-A-B-D 는 단순경로가 아님)
cycle : 시작정점 = 종료정점 (단순경로에서)
그래프의 종류
- 무방향 그래프
- 방향없음
- (A,B)로 표현
- 방향 그래프 (화살표가 있음)
- 방향있음
- <A,B>로 표현 A→B
- 가중치 그래프 (Weighted Graph) or Network
- 간선에 비용 또는 가중치가 할당된 그래프
- 연결 그래프
- 모든 경로가 존재
- 비연결 그래프
- 일부 노드는 접근 못함
- 사이클
- 순환 가능
- 비순환그래프
- 순환 불가
- 완전그래프
- 모든 버텍스가 엣지로 연결된 경우
트리 vs 그래프
- 트리는 그래프 중에 종류라고 볼 수 있음
- 트리는 방향성이 있는 비순환 그래프
- 트리는 방향그래프만 존재함
- 트리는 루트 노드가 존재함
- 트리는 부모 자식 관계가 존재함
