인접 리스트
-
[그래프 탐색] DFS와 BFS문제 풀이/Baekjoon Online Judge 2021. 1. 12. 20:31
1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 경우 방향을 가진 간선으로 나타낼 수 있다. 이때 이러한 그래프를 방향을 가진 그래프 혹은 Direct Graph 유향 그래프라고 한다. 반면 간선의 방향이 없는 그래프를 무방향 그래프 혹은 Undirected Graph 무향 그래프라고 한다. 2. 그래프의 표현 그래프의 표현 방법에는 행렬을 이용하는 방식과 리스트를 이용하는 방식이 있다. 2.1 인접 행렬 그래프 G = (V, E)에서 정점의 총 수를 n이라고 가정하자. 행렬의 크기는 n x n 행렬이 된다. 정점 i와 정점 j 사이에 간선이 존..