그래프
자료구조의 일종.
정점(Node, Vertex)
간선(Edge): 정점간의 관계를 나타냄.
G = (V,E)로 나타낸다.
-
경로 : 정점 A에서 B로 가는 경로.
연결되어 있는 간선을 통해서만 이동 가능함. -
사이클 : 시작 정점 == 도착 정점.
정점 A에서 다시 A로 돌아오는 경로를 말함. -
단순 경로와 단순 사이클
- 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클
- 특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 뜻한다.
방향 있는 그래프(Directed Graph)
- A -> C -> D
-> 여기서 A에서 C로 가는 간선은 있지만, C에서 A로 가는 간선은 없음.
방향 없는 그래프(Undirected Graph)
- A - C - D
-> A-C 간선에 방향이 없다. 양방향 그래프라고도 함.
A->C / C->A 둘다 가능함.
간선 여러개(Multiple Edge)
- 두 정점 사이에 간선이 여러 개 일수도 있다.
- 두 간선은 서로 다른 간선이다.
루프(Loop)
- 간선의 양 끝 점이 같은 경우.
- A -> A
- 자주 등장하지는 않음.
- 보통 문제의 상황을 그래프로 변환한 다음, 그래프 알고리즘을 적용함.
가중치(Weight)
- 간선에 가중치가 있는 경우에는 A에서 B로 이동하는 거리, 이동하는데 필요한 시간 등등...
A -> C -> D
5 3 - 매우 중요함.
- 가중치가 없는 경우에는 1이라고 생각하면 됨.
차수(Degree)
- 정점과 연결되어 있는 간선의 개수
최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.
#back_end #developer #🐥