목록Graphs (2)

YYYEJI

[DS] 최소 신장 트리(Minimum Spanning Tree)란?

신장 트리(Spanning Tree) 란? 한 Graph의 모든 vertex를 연결하는 cycle이 없는 sub graph입니다. - 스패닝 트리는 (n-1)개의 edge를 가진다. - 스패닝 트리는 DFS, BFS 알고리즘을 이용해 찾을 수 있다. (움직인 edge를 연결하면 된다.) - Cycle이 있어서는 안된다. 아래와 같은 그래프가 존재할 때 DFS, BFS spanning tree를 만들어보면 ↓↓↓ DFS ↓↓↓ https://yyyeji.tistory.com/379 [DS] 깊이 우선 탐색(DFS)이란? 하나의 vertax로부터 모든 vertex를 한 번씩 방문하는 그래프 탐색이 있습니다. ↓↓↓ 그래프란? ↓↓↓ https://yyyeji.tistory.com/378 [DS] 그래프(Gr..
Data structure 2023. 1. 24. 18:26
[DS] 그래프(Graphs)의 종류와 관련 용어

그래프(Graphs)란? 객체 사이의 연결 관계를 나타낼 수 있는 자료 구조입니다. 그래프(graph)는 vertex의 집합과 edge의 집합으로 이루어집니다. - vertex = {a, b, c, d, e} - edge = {(a, b), (a, e), (b, c), (c, d), (c, e), (d, e)} 그래프(graph) 관련 용어(Terminology) Adjacent - 두 vertex 간의 edge가 존재함 Path - 두 vertax 간에 edge로서 연결되는 vertex의 sequence Length of a path - path를 구성하는 edge 개수 Connected - 두 vertex 간에 path가 존재함 Connected components - 연결된 원소의 그룹 Cycle ..
Data structure 2023. 1. 5. 18:26
이전 Prev 1 Next 다음