자료구조 - 그래프
1. 그래프란? 그래프(Graph)는 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것이다. 수학정 정의 : 정점 집합 V = {v1, v2, v2, ..., vn} 이고, 정점간의 연결 관계들을 나타내는 간선 집합 E = {(vi, vj)/vi ∈ V, vj ∈ V} ⊆ V x V 일 때, 그래프 G = (V, E) 이다. 2. 그래프 용어 1) 무향 간선 (Undirected Edge) - 정점을 연결하는 간선에 방향이 존재하지 않는다. - 임의의 간선 (vi, vj)에 대해서 (vi, vj) = (vj, vi)이다. 2) 유향 간선 (Directed Edge) - 정점을 연결하는 간선에 방향이 존재한다. - 임의의 간선 (vi, vj)에 대해서 (vi, vj) ≠ (v..
2021. 2. 2.
알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search)
알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 미로에서 갈림길로 돌아가서 길을 찾는 것을 생각하면 된다. DFS를 설명하기 전에, 먼저 그래프의 기본 구조를 알아야 한다. https://jina-developer.tistory.com/108 자료구조 - 그래프 1. 그래프란? 그래프(Graph)는 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것이다. 수학정 정의 : 정점 집합 V = {v1, v2, v2, ..., vn} 이고, 정점간의 연결 관계들을 jina-developer.tistory.com 모든 노드를 ..
2021. 1. 27.
