TIL : Graph 자료구조
Graph
- DFS 와 BFS에 쓰이는 걔...
- Vertex(정점) == Node, Edge(간선) 으로 표현한다.
- Node == Vertex : 위치
- Edge (간선) : 위치 간의 관계, 노드 간 연결된 선
- 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 노드
- 참고 :
- 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수 : 방향 그래프에서 외부로 향하는 간선의 수
- 경로 길이 : 경로를 구성하기 위해 사용된 간선의 수
- 단순 경로 : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없느 ㄴ경로
- 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
- 방향이 없는 그래프
- 간선을 통해 노드는 양방향으로 이동 가능
- 연결된 경우 (A, B) 혹은 (B, A) 로 표기한다
- 간선에 방향이 있는 그래프
- <A, B> 로 표기하지만, <B, A> 와는 다르다, 진출 진입 관련
- 간선에 비용 또는 가중치가 할당된 그래프
사이클과 비순환 그래프
- 사이클 : 단순 경로의 시작 노드와 종료 노드가 동일한 경우,
- 비순환 그래프 : 사이클이 없는 그래프
- 그래프의 모든 노드가 서로 연결되어 있는 그래프
- cf) 트리와 차이점
-.트리는 확정된 방향성이 있는 비순환, 비사이클 그래프
- 트리는 루트가 존재, 그래프 루트 X
- 트리 부모 자식 관계, 그래프 부모 자식 관계 X