1/20 TIL | 그래프 알고리즘(Graph Algorithm)

오늘 코딩 도장 문제를 풀다가 접하게 된 그래프 알고리즘. 개념을 정리하고 넘어가 보자! 오늘도 역시나 ChatGPT에게 물어보았다.

그래프 알고리즘

그래도 내가 다시 한번 정리해 보자.

그래프 알고리즘이란?

정점(혹은 노드(Node)라고도 표현됨)과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조를 말한다. 정점(Vertex) 집합과 간선(Edge) 집합으로 표현 가능한데, 예를 들어 인물 관계도, 지하철 노선도, 페이지 링크 알고리즘 등이 있다.

정점은 여러 개의 간선을 가질 수 있는데, 이때 크게 방향 그래프와 무방향 그래프로 나누어진다.
1) 방향 그래프: 말 그대로 간선의 방향이 존재, 양방향으로 이동할 수 있더라도 A → B / B → A는 엄연히 다르다.
2) 무방향 그래프: 반대로 간선의 방향이 따로 존재하지 않음, 양방향으로 이동 가능하다(A → B / B → A).

또, 연결 그래프와 비연결 그래프로도 나누어진다.
1) 연결 그래프: 모든 정점이 이동할 수 있는 형태의 그래프
2) 비연결 그래프: 특정 점, 쌍 사이에 간선이 없는 형태의 그래프

연결/비연결 그래프

그래프의 모든 정점(노드)을 방문하는 것을 '순회'라고 표현하는데, 이때 가장 대표적인 방법으로 BFS(Breath-First Search, 너비 우선 순회), DFS(Depth-First Search, 깊이 우선 순회) 방식이 있다. BFS, DFS는 코딩 도장 문제 풀이와 함께 다른 포스팅으로 정리를 해보려고 한다.