그래프2 자료구조 그래프(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)와 그래프의 종류 알아보기 자료구조 그래프와 그래프의 종류 알아보기 그래프(Graph)는 무엇인가? 그래프는 노드와 간선(Edge) 의 집합이다. G = (V, E) 그래프는 비선형(non-linear) 자료구조이다. 트리와 그래프의 차이 트리의 특징 루트 노드가 존재한다 루트 노드를 제외한 데이터들은 서브 트리로 구분된다. 트리는 아래쪽으로 확장된다. 트리는 반드시 연결되어 있어야 한다. 루프를 포함하지 않는다. 그래프의 특징 그래프의 정점은 다른 다양한 다른 정점과 연결될 수 있다. 간선에 가중치를 설정할 수 있다. 간선은 방향을 가지거나 가지지 않을 수 있다. 그래프의 용어 정점 (Vertex) - 그래프에서 각각의 노드는 정점을 의미한다. 간선 (Edge) - 간선은 두 정점을 잇는 선을 의미한다. 인접 (Adjacency.. 2020. 6. 16. 이전 1 다음
