자료구조 중 그래프에 대해 알아보자
얻어갈 지식
- 그래프
그래프
그래프란 노드와 노드를 연결하는 간선으로 표현되는 자료 구조이다.
종류는 크게 3가지이다.
- 무방향 그래프( undirected graphs )
- 방향 그래프( directed graphs )
- 가중치 그래프( weighted graphs )
무방향 그래프( Undirected graphs )
- 두 노드 사이의 간선은 방향을 나타내지 않고 양쪽 모두를 오갈 수 있다.
양방향 그래프( Directed graphs )
- 두 노드 사이의 간선이 방향을 갖는다.
가중치 그래프 ( Weighted graphs )
- 연결마다 가중치를 갖는다.
- 가중치의 의미는 시간, 거리, 크기 등이 될 수 있다.
- 일상생활에서 가장 흔히 볼 수 있는 가중치 그래프는 아래와 같은 지도이다.
그래프의 용어와 정의
노드 : 위의 그림에서 동그라미로 표현된 것을 의미하며 노드, 정점, vertex라고도 한다.
간선 : 두 개의 노드를 잇는 선을 의미하며 edge라고도 한다.
path : 한 vertex에서 다른 vertex로 가는 순서를 의미한다. 그림 1)에서 A에서 C로 가는 경로는 [A, B, C] 또는 [A, G, B, C] 또는 [A, E, F, D, B, C]이다.
path length : path의 edge의 수이다. 그림 1)에서 A에서 C로가는 path length는 2, 3, 5이다.
Cycle : 시작점과 끝점이 같은 vertex인 경로를 뜻한다. 그림 1)에서 [A, B, D, F, E]가 하나의 cycle이고 [A, G, B]도 하나의 cycle이다.
Negative Weight Cycle : 가중치 그래프에서 한 사이클의 모든 가중치의 합이 음의 값인 것을 뜻한다.
https://leetcode.com/explore/learn/card/graph/
Explore - LeetCode
LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore.
leetcode.com
'알고리즘, 자료구조' 카테고리의 다른 글
| 멀쩡한 사각형( 파이썬 ) - 프로그래머스 (0) | 2022.06.24 |
|---|---|
| DFS와 BFS - 파이썬 구현 (0) | 2022.06.20 |
| 검색 알고리즘 (0) | 2022.06.20 |
| 계수 정렬 (0) | 2022.05.31 |
| 퀵 정렬 (0) | 2022.05.30 |