그래프: 객체 간의 연결을 시각적으로 나타내는 자료구조
그래프는 객체 간의 연결과 관계를 다양하게 나타낼 수 있는 자료 구조이다.
그래프 알고리즘(순회, 검색, 정렬 등)을 통해 두 그래프노드 간의 최단 경로를 찾는 등의 문제를 해결할 수 있다.
그래프를 적용한 사례는 다양한데 대표적으로 웹사이트, 지도, 회로, 소셜미디어, 전화 등이 있다.
적용 사례 | 항목 | 연결
-------------------------------
웹사이트 | 웹페이지 | 링크
지도 | 교차로 | 도로
회로 | 부품 | 배선
소셜미디어 | 사람 | 친구 맺기
전화 | 전화번호 | 전화선그래프 기본 개념
- 정점 vertex: 그래프 노드. 시각적으로 표기할 때 동그라미로 표현한다.
- 간선 edge: 그래프 노드 간의 연결. 시각적으로 표기할 때 선으로 표현한다.
- 정점 차수 degree of vertex: 노드에 연결된 간선 개수.
- 희소 그래프 sparse graph: 연결이 가능한 노드 중 일부만 간선이 존재할 때, 이 그래프를 희소 그래프라 한다.
- 밀집 그래프 dense graph: 노드 간 연결이 많을 때, 이 그래프를 밀집 그래프라 한다.
- 순환 그래프 cyclical graph: 한 노드에서 출발해 해당 노드로 돌아오는 경로가 있는 지향성 그래프를 순환 그래프라 한다.
- 가중치 weight: 간선에 대한 값이다. 문맥에 따라 다양한 것을 나타낼 수 있다.
1. 무지향성 그래프
무지향성 그래프 undirected graph: 노드 사이 간선에 방향이 없는 그래프.
무지향성 그래프에서 간선은 두 노드 간의 상호 연결을 뜻하며, 가중치는 가지는 반면 방향은 가지지 않는다.
무지향성 그래프는 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)를 통해 클래스로 표현될 수 있다.
인접 행렬은 스도쿠처럼 표시되며, 두 노드 간의 연결 여부를 나타낸다.
인접 리스트는 노드를 키로 가지고, 해당 노드의 이웃을 리스트 형식으로 저장한다.
2. 지향성 그래프
지향성 그래프 directed graph: 노드 사이 간선에 방향이 있는 그래프.
3. 그래프 순회
1) 너비 우선 검색
너비 우선 검색 BFS, breadth-first search: 루트 노드로부터의 높이 단위로(단계 별) 검색하는 알고리즘
너비 우선 검색은 이진 검색 트리의 차수 우선 순회와 비슷하게 루트 노드로부터의 높이 단위로 검색이 진행된다.
너비 우선 검색을 코드로 구현하기 위해서는 큐 자료구조를 사용한다.
루트 노드에서부터 각 노드에 연결된 노드를 큐에 추가한 다음, 큐의 각 항목을 방문하는 식으로 검색을 진행한다.
2) 깊이 우선 검색
깊이 우선 검색 DFS, depth-first search: 루트 노드로부터 하나의 연결을 깊게 파고들며 순회하는 검색 알고리즘
깊이 우선 검색은 트리의 후순위 순회와 비슷하게 동작한다.
루트 노드에서부터 연결된 노드를 깊게 파고들며, 이는 재귀를 이용하여 코드로 구현할 수 있다.
4. 가중치가 있는 그래프와 최단 경로
1) 가중치가 있는 간선을 지닌 그래프
간선에 가중치를 할당하여 정보를 나타낼 수 있다. 또한, 도표상에서 간선의 길이는 간선의 가중치와는 무관하다.
예를 들어 지도를 나타내는 그래프에서 '거리'를 가중치로 나타낼 수 있고, 이 거리가 할당된 간선의 길이는 거리(가중치)와는 관계가 없다.
가중치가 있는 간선 그래프에서 가장 중요한 점은 노드 간의 '가장 짧은 경로가 무엇인가'이다.
그래프의 최단 경로 알고리즘에는 여러 종류가 있는데, 이번엔 다익스트라 알고리즘을 알아보고자 한다.
2) 다익스트라의 알고리즘: 최단 경로
다익스트라 알고리즘 Dijkstra's algorithm: 목적지에 도달하기 위해 각 단계에서 최단 경로를 취하는 방식으로 동작한다.
- 다익스트라 1단계: 거리를 무한으로 표기 (일부 노드에 도달할 수 없을 수도 있기 때문에)
- 다익스트라 2단계: 각 루프 시마다 각 노드에 대한 최단 경로 선택
- 다익스트라 3단계: 모든 노드의 최단 경로 선택 완료
5. 위상 정렬
지향성 그래프를 적용할 때, 어떤 노드를 가장 먼저 처리해야 할 지 알아야 한다.
예를 들어 작업 스케줄러에서는 한 작업이 이전 작업의 수행 여부에 영향을 받는다. 또한, 자바스크립트 의존도 매니저를 예로 보면 import 를 수행할 때, 해당 라이브러리 전에 미리 가져와야 할 라이브러리가 무엇인지 알아야 한다.
위상 정렬 알고리즘은 깊이 우선 정렬 알고리즘으로, 순서를 기록함으로써 위에서 언급한 기능을 구현할 수 있다. 이 알고리즘은 어떤 노드로부터 깊이 우선 정렬을 수행해 해당 노드와 연결된 모든 노드를 재귀적으로 방문하면서, 해당 노드들을 스택에 추가하는 방식으로 동작한다. 재귀 호출의 끝에서 현재 노드 값을 스택에 추가함을 통해 시간순의 순서를 보장한다.
이런 알고리즘이 어디에 어떻게 사용될 수 있는지 잘 감이 오지 않아, 이번 회차는 잘 이해가 되지 않았다. 이런 알고리즘이 있구나를 알게 되었고, 추후 로직을 짜거나 구조를 설계할 때 이런 알고리즘도 염두할 수 있게 된 것에 의의를 두어야겠다.
