프로그래밍/기본기ㆍ자료구조
2020. 4. 15.
Graph (그래프)
노드와 간선(노드와 노드를 잇는 선)으로 이루어진 자료구조이다. 트리와 그래프의 관계 - 큰 범위 안에서는 트리는 그래프의 일종이다. 트리 - 방향성이 있는 비순환 그래프 - 한 개의 루트 노드만이 존재 (자식 노드는 하나의 부모 노드만을 가진다.) - 전위, 중위, 후위 순회 및 계층 순회(level-Order) - 노드가 N개이면 항상 N-1개의 간선을 가짐 그래프 - 노드와 간선으로 이루어짐 - 방향성, 무방향성 그래프 모두 존재 - 루트 노드의 개념이 없다 - 깊이 우선 탐색(DFS : Depth First Search), 너비 우선 탐색(BFS :Breadth First Search) - 그래프에 따라 간선의 수가 다르다 그래프의 종류 a. 무방향 그래프(Undirected Graph..
