비선형 자료구조 - 그래프

N 대 M 대응 구조로 노드와 선분으로 구성되어있다. 트리와 다른점은 서로 사이클이 형성되는 경우를 그래프라고 표현한다. 주로 최단 거리 탐색, 전자 회로 분석, 통계학과 같은 분야에서 사용된다. 비방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph) 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph 라 하고, 간선에 방향성이 포함되어 있는 그래프를 Directed Graph 라고 한다. 그래프 탐색 너비 우선 탐색 (BFS) : 시작점에서 시작하여, 연결된 정점 끝까지 내려간다. 끝나는 지점을 만나게 되면 다시 되돌아와 그 옆부터 끝까지 검색한다. 밑 까지 검색하다 다시 되돌아가야 하니 stack과 같은 자료구조를 사용하면 된다. 깊..

2020.10.08