그래프

지니씨·2021년 10월 2일
0

정의

정점(V)과 간선(E)으로 이루어진 자료구조

경로
정점 A에서 B로 가는 경로

사이클
시작점과 끝점이 동일한 경로

단순경로(사이클)
경로(사이클)에서 같은 정렬을 두 번 이상 방문하지 않는 경로(사이클)

가중치
간선을 사용할 때 드는 비용

차수(degree)
하나의 정점에 연결되 있는 간선의 수
간선에 방향이 있는 경우 in-degree 와 out-degree 를 나눠서 생각해야 함

저장

방향이 있는 경우 방향도 같이 저장해줘야 함

그래프 저장의 목적
: 하나의 정점과 연결된 간선을 빠르게 찾기 위함
: 전체 공간의 수를 적게 만들어야 함

1. 인접행렬
정점x정점 이차 배열에 간선의 유(1)/무(0) 또는 간선의 가중치를 저장

2. 인접리스트
정점 일차 배열에 각 정점과 연결된 정점들로 이루어진 배열을 값으로 가짐

3. 간선리스트

탐색

1. 깊이 우선 탐색(DFS)
Stack 사용

2. 너비 우선 탐색(BFS)
Queue 사용

참고
다익스트라 알고리즘

기타

연결요소
그래프의 모든 정점이 연결되어있지 않는 경우, 나누어진 각각의 그래프를 연결 요소라고 함

이분 그래프
그래프를 A/B 두 그룹으로 나눌 수 있고, 각 그룹안의 정점끼리 연결된 간선이 없는 경우
모든 간선의 한 끝점은 A 그룹, 다른 끝점은 B인 경우

플러드필
어떤 위치와 연결된 모든 위치를 찾는 알고리즘

profile
하루 모아 평생 🧚🏻

0개의 댓글