TIL : Graph 자료구조

Graph 

 

- DFS 와 BFS에 쓰이는 걔...

- Vertex(정점) == Node, Edge(간선) 으로 표현한다.

- Node == Vertex : 위치

- Edge (간선) : 위치 간의 관계, 노드 간 연결된 선

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

 

- 참고 : 

  - 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

  - 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수

  - 진출 차수 : 방향 그래프에서 외부로 향하는 간선의 수

  - 경로 길이 : 경로를 구성하기 위해 사용된 간선의 수

  - 단순 경로 : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없느 ㄴ경로

  - 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

 

무방향 그래프

- 방향이 없는 그래프

- 간선을 통해 노드는 양방향으로 이동 가능

- 연결된 경우 (A, B) 혹은 (B, A) 로 표기한다

 

방향 그래프

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

- <A, B> 로 표기하지만, <B, A> 와는 다르다, 진출 진입 관련

 

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

 

비순환 그래프

사이클과 비순환 그래프 

  - 사이클 : 단순 경로의 시작 노드와 종료 노드가 동일한 경우,

  - 비순환 그래프 : 사이클이 없는 그래프

 

 

완전 그래프

- 그래프의 모든 노드가 서로 연결되어 있는 그래프

 

- cf) 트리와 차이점

 -.트리는 확정된 방향성이 있는 비순환, 비사이클 그래프

 - 트리는 루트가 존재, 그래프 루트 X

 - 트리 부모 자식 관계, 그래프 부모 자식 관계 X