그래프2 [알고리즘] Graph (2) - Depth-first search(DFS) [2. Depth-first search 깊이우선탐색] 1. 깊이우선탐색 - 무방향그래프 → 그래프의 탐색을 위해 Recursive call을 활용한다. → 가능한 연결되어 있는 노드들을 방문하며 → 방문 순서는 특별한 지시가 없을 경우 오름차순을 따른다. → 각 vertex v에서 탐색을 시작할 경우 → v는 이미 방문한 것으로 표시(visit[v]=1) → v에 연결된 vertex w중에서 아직 방문하지 않은(visit[w]=0인) vertex 방문 → 더이상 방문할 vertex가 없으면 직전 노드로 return Ex) 2. Spanning Tree (DFS Tree) → 주어진 그래프에서 방문되는 n-1개의 간선들로 모든 개체를 연결한 서브그래프 → DFS tree에서 root node에 다른 노드.. 2022. 11. 15. [알고리즘] Graph (1) - Prologue [1. Prologue 개요] 1. 그래프란? → Graph : 개체와 개체들 사이의 링크로 연결된 1:1 관계를 시각적으로 나타내는 수학적 표시, 개체와 그 개체를 연결하는 링크의 집합 → vertex : 개체 → edge : 개체를 연결하는 링크, 개체간 관계를 나타냄 → G = (V, E), 그래프는 두 개의 요소(개체, 관계)를 가짐 2. 그래프의 종류 → 방항성 : 링크의 방향이 정해진 그래프 / 방향이 정해지지 않은 그래프 → 가중치 : 링크의 가중치가 정해진 그래프 / 가중치가 정해지지 않은 그래프 → 방향x, 가중치x : 무방향 그래프 → 방향x, 가중치o : 가중치 그래프 → 방향o, 가중치x : 방향그래프 → 방향o, 가중치o : 방향가중치 그래프 3. 그래프의 표현 (1) Edge l.. 2022. 11. 8. 이전 1 다음
