그래프 기초 — 표현, BFS, DFS

오늘은 그래프라는 자료구조를 배워보겠습니다.

그래프는 정점과 간선으로 이루어진 구조예요.

수학적으로 G = (V, E)로 표현하는데, V는 정점 집합, E는 간선 집합이에요.

왼쪽 그림을 보세요. 무방향 그래프에서는 A와 B 사이에 양방향 연결이 있어요.

이때 간선에 방향이 없으므로 A에서 B로, B에서 A로 모두 이동 가능합니다.

가운데 그림은 방향 그래프예요. 간선에 화살표가 있어서 A에서 B로만 갈 수 있죠.

방향 그래프에서는 A에서 B로 가는 것과 B에서 A로 가는 것이 다릅니다.

오른쪽의 가중 그래프를 보면, 간선마다 숫자가 적혀 있어요.

이 숫자를 가중치라고 하는데, 도로의 거리나 통신 비용을 나타낼 수 있어요.

하단의 용어 정리를 함께 보시죠.

정점은 노드라고도 부르고, 간선은 두 정점을 연결하는 선이에요.

차수는 한 정점에 연결된 간선의 수를 뜻합니다.

경로는 정점들을 간선으로 연속 연결한 것이고, 사이클은 시작점으로 돌아오는 경로예요.

그래프가 왜 이렇게 중요할까요?

소셜 네트워크에서 사용자가 정점, 친구 관계가 간선이에요.

내비게이션에서는 교차로가 정점, 도로가 간선, 거리가 가중치입니다.

웹 크롤링에서 페이지가 정점, 하이퍼링크가 간선이 되죠.

패키지 의존성에서는 모듈이 정점, import 관계가 방향 간선이에요.

이처럼 관계가 있는 데이터라면 거의 모두 그래프로 표현할 수 있어요.

배열이나 트리로는 표현하기 어려운 복잡한 관계를 그래프가 자연스럽게 담습니다.

자, 그럼 이 그래프를 컴퓨터에 어떻게 저장할지 알아볼까요?