그래프 코드 구현
-
Data Structure - Graph(그래프)Programming/Data Structure(자료 구조) 2019. 4. 7. 18:17
- Graph(그래프) - Graph(그래프)의 정의 - 노드(node)와 그 노드의 연결선인 엣지(edge)를 모아 놓은 자료 구조 - 연결되어 있는 객체간의 관계를 표현하기 위한 자료 구조 - 계층 관계인 트리와는 다르게 네트워크 관계이다 Graph(그래프)와 Tree(트리)의 차이 Graph(그래프)의 특징 - 네트워크 모델이다 - 2개 이상의 경로가 가능하다 - 트리처럼 root라는 개념이 없다 - 부모 - 자식 관계가 없다 Graph(그래프)의 탐색 방법 1. DFS(깊이 우선 탐색) - 그래프의 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중 아직 방문하지 않은 정점 u를 선택한다. - 만약 그러한 정점이 없다면 탐색은 종료한다 - 만약 아직 방문하지..