Computer Science/Data Structure 자료구조11 자료구조 그래프(Graph) 의 탐색 방법 DFS 와 BFS 자료구조 그래프(Graph) 의 탐색 DFS 와 BFS 그래프(Graph) 탐색 방법 1. 깊이 우선 탐색 (DFS, Depth-First Search) 루트 노드부터 시작하여 그래프에서 깊이를 우선적으로 탐색한다. 스택 (Stack) 과 재귀 (Recursion)를 이용한다. 스택은 후입선출 (LIFO, Last In First Out) 스택은 수직 구조로 볼 수 있고, 수직 구조는 깊이를 가진다고 할 수 있다. 이웃한 노드들의 포인터를 저장하지 않아도 되기 때문에 BFS 보다 더 적은 메모리를 요구한다. 2. 너비 우선 탐색 (BFS, Breadth-First Search) 루트 노드부터 시작하여 그래프에서 너비를 우선적으로 탐색한다. 큐 (Queue) 를 이용한다. 큐는 선입선출 (FIFO, Fir.. 2020. 6. 20. 자료구조 그래프(Graph) 구현방법 자료구조 그래프의 구현방법 그래프의 추상 자료형 그래프 생성 - n 개의 노드를 가지는 빈 그래프를 만든다. 그래프 삭제 - 그래프 G의 모든 노드 V와 간선 E를 제거한후, 그래프를 제거한다. 간선 추가 - 그래프 G에 노드 u 와 노드 v를 연결하는 간선 e를 추가한다. 간선 제거 - 그래프 G의 간선 (u,v) 또는 (v,u)를 제거한다. 방향 그래프(Directed Graph) 라면 u->v 와 v->u는 서로 다른 간선이다. 그래프 구현 방법 1. 인접 행렬 (Adjacency matrix) 2차원 배열 (aka 행렬) 을 이용 두 개의 노드가 간선으로 연결되어 있다면 인접하다. 인접 행렬에 그래프의 간선 정보를 저장한다. 간선의 존재 유무 간선 (i, j) 가 존재: [i][j] = 1 간선 .. 2020. 6. 19. 자료구조 그래프(Graph)와 그래프의 종류 알아보기 자료구조 그래프와 그래프의 종류 알아보기 그래프(Graph)는 무엇인가? 그래프는 노드와 간선(Edge) 의 집합이다. G = (V, E) 그래프는 비선형(non-linear) 자료구조이다. 트리와 그래프의 차이 트리의 특징 루트 노드가 존재한다 루트 노드를 제외한 데이터들은 서브 트리로 구분된다. 트리는 아래쪽으로 확장된다. 트리는 반드시 연결되어 있어야 한다. 루프를 포함하지 않는다. 그래프의 특징 그래프의 정점은 다른 다양한 다른 정점과 연결될 수 있다. 간선에 가중치를 설정할 수 있다. 간선은 방향을 가지거나 가지지 않을 수 있다. 그래프의 용어 정점 (Vertex) - 그래프에서 각각의 노드는 정점을 의미한다. 간선 (Edge) - 간선은 두 정점을 잇는 선을 의미한다. 인접 (Adjacency.. 2020. 6. 16. 배열을 이용한 힙(Heap) 구현 배열을 이용한 힙(Heap) 구현 배열을 이용했을때의 특징 힙의 삽입 과 삭제 연산이 더 빠르다. 노드의 주솟값을 계산할 수 있어 원하는 노드에 빨리 접근할 수 있다. 힙은 완전 이진 트리(Complete binary tree)이기 때문에 낭비되는 빈 노드가 적어 공간의 낭비가 적다. 배열의 위치 인덱스와 히프 루트 노드의 위치 인덱스의 값은 1 노드 i 의 부모 노드 인덱스 = [i / 2] , i>1 일때 ex) [5 / 2] = [2.5] = 2 노드 i 의 왼쪽 자식 노드 인덱스 = 2 * i 노드 i의 오른쪽 자식 노드 인덱스 = (2 * i) + 1 Max Heap 에 데이터 삽입하기 기본 원리 새로운 노드를 마지막 노드 옆에 삽입한다. 새로운 노드의 값을 부모 노드의 값과 비교하여 위치를 이.. 2020. 6. 15. 이전 1 2 3 다음
