그래프란?

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=591923&logNo=220911564679
[개념]
- 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
- 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등
그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있다.
[특징]
- 네트워크 모델이다
- 2개 이상의 경로가 가능하다(노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
- self-loop뿐 아니라 loop, circuit 모두 가능하다.
- root node X
- 부모-자식 관계 X
- 순회는 DFS / BFS로 이뤄짐
- Cyclic하거나 Acyclic하다고 크게 나눌 수 있다.
- 크게 방향그래프/무방향그래프로 나눌 수 있다 - 무방향 그래프는 노드간 양방향 이동이 가능하므로 양방향 그래프로도 불린다
- 간선의 유무는 그래프에 따라 다름
[용어]
- 정점(vertex): 위치라는 개념. (node 라고도 부름)
- 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
- 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
- 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수