그래프
특정 사물, 개념 혹은 데이터 간의 연결관게를 정점(vertex)과 간선(edge)로 표현한 것.
정점 = vertex = node 라고 이해하는 것이 간편하다.
수식으로 그래프는 G(V,E)로 표기 가능하며, 이때 V는 정점들의 집합{v1,v2 ... } , E는 간선들의 집합{e1,e2...}이다.
간선(edge)의 경우 시작점과 도착점으로 구성되어 있고, 방향이 있을 수도 있고 없을 수도 있다.
간선의 특징에 따라 그래프의 종류가 나뉜다.
- 간선방향이 있는경우 (Directed) - 시작점과 도착점이 있다. '시작 → 도착' 단일 방향으로 연결되어 있다.
- 간선의 방향이 없는 경우 (Undirected) - 두 노드의 시작, 도착노드가 별도 구분되어 있지않다. 즉 쌍방 통행이 가능함.
- 순환 구조가 있는 경우 (Cyclic) - 노드의 일부 구조상 시작점으로 다시 돌아올 수 있는 순환구조가 있는 경우. A, B, C노드가 간선 3개로 연결되어있는 경우를 상상하면 이해하기 쉽다.
- 순환 구조가 없는 경우 (Acyclic) - A, B, C가 간선 2개로 연결되어 있는 구조를 생각하면 이해하기 쉽다.
**위상정렬의 경우 Directed / Acyclic에서 가능하다. (관련 내용 하기 링크 참조)
https://campkim.tistory.com/10
위상 정렬 개념 & 알고리즘 문제풀이 (백준 2637 장난감 조립, 2252 줄세우기 [파이썬])
위상 정렬(topological) 유향 그래프에서 정점(vertex)를 간선(edge)의방향에 거스르지 않도록 나열하는 것을 의미함. 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따른 정렬에 사용될 수 있는
campkim.tistory.com
'자료구조 알고리즘 > 알고리즘' 카테고리의 다른 글
| [파이썬] 백준 11725 트리의 부모찾기 ( BFS, DFS 3가지 풀이 비교) (0) | 2021.08.25 |
|---|---|
| DFS / BFS 알고리즘과 예제풀이 ( 백준 바이러스, BFS 와 BFS 파이썬 ) (0) | 2021.08.25 |
| 위상 정렬 개념 & 알고리즘 문제풀이 (백준 2637 장난감 조립, 2252 줄세우기 [파이썬]) (2) | 2021.08.24 |
| [TIL] Call by value와 Call by reference (1) | 2021.08.22 |
| [TIL] 파이썬 객체와 변수 / mutable, immutable 자료형 (1) | 2021.08.21 |