전체 글
-
그래프(graph)의 구현 2가지Computer Science/Data_Structure 2020. 1. 4. 06:05
그래프를 구현하는 방법은 책을 보거나, 구글링을 해보아도 전부 인접행렬 or 인접리스트를 이용하여 구현을 한다. 상황에 맞게 시간복잡도를 고려하여 더 효율적인 것을 사용하면 된다. 그래서 각각의 장단점을 공부하려 글을 쓰려 한다. https://kosaf04pyh.tistory.com/131 [자료구조] 그래프(Graph) 이번시간에는 그래프에 대해 공부해 보겠습니다. 그래프란 ? 그래프는 정점(Vertex)간의 관계를 표현하는 자료구조 입니다. 그래프 G = (V,E)로 정의하는데, V(Vertex)는 그래프에 있는 정점들의 집합을 의미하고.. kosaf04pyh.tistory.com https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html ..
-
너비 우선 탐색(BFS) 란?Computer Science/Data_Structure 2020. 1. 4. 05:30
그래프 탐색에는 2가지가 있다고 했는데 그 중에 하나인 BFS 탐색에 대해서 정리하려고 한다. 너비 우선 탐색(breath first search : BFS) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 위와 같은 그래프에서 화살표의 방향대로 탐색을 한다. (시작 정점에서 가까운 노드부터 탐색하는 것을 알 수 있다) 너비 우선 탐색을 위해서는? 가까운 거리에 있는 정점들을 차례로 정한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요함 무조건 큐에서 정점을 꺼내서 정점을 반물하고 인접 정점들을 큐에 추가한다.(큐가 소진될 때 까지 반복) 너비 우선 탐색 과정 다시한번 정리하자면 다음과 같다. 위의 과정을 큐가 공백 상태가 될 때 까지 계속한다...
-
깊이 우선 탐색(DFS) 란?Computer Science/Data_Structure 2020. 1. 4. 00:36
그래프의 탐색 그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 그래프 탐색은 아주 중요하다 도시를 연결하는 그래프가 있을 때, 특정 도시에서 다른 도시로 갈 수 있는지 없는지는 탐색하여 체크 그래프의 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색의 두 가지가 있다. 이 글에서는 깊이 우선 탐색에 대하여 알아보겠다. 깊이 우선탐색(DFS : depth first search) 트리에서 생각하면 이해하기 쉽다(트리도 그래프의 일종이라는 점을 명심하자) 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사 위와 같은 그림의 그래..
-
그래프(Graph) 란?Computer Science/Data_Structure 2020. 1. 3. 21:49
그래프의 소개 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조다. (대표적인 예 : 지도) 지도를 그래프로 표현하면 지하철의 특정한 역에서 다른 역으로 가는 최단 경로를 쉽게 찾을 수 있다. 운영 체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무 등을 알아낼 수 있다. 그래프로 표현할 수 있는 것들 도로 미로 선수과목 1. 그래프의 정의와 용어 그래프의 정의 그래프는 정점(vertex)와 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V,E)와 같이 표시한다. V(G)는 그래프의 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합이다. 정점 : 여러 가지 특성을 가질 수 있는 객체 간선 : 이러한 정..