잡동사니

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 그래프(graph)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 그래프는 노드와 엣지, 두 집합으로 구성된 자료구조입니다. 그래프의 종류에는 무방향 그래프, 방향 그래프, 가중치 그래프가 있습니다. 그래프는 인접 행렬과 인접 리스트로 표현 가능합니다. 인접 행렬은 n*n 크기의 2차원 행렬로 표현하는 방식으로 저장 공간은 O(n^2)의 크기를 가지고, 인접한 모든 노드를 찾는 시간은 O(n), 엣지의 존재 여부를 찾는 시간은 O(1)의 특성을 가집니다. 인접 리스트는 노드 집합을 표현하는 1차원 배열과 각 노드마다 인접한 노드들을 연결 리스트로 표현한 방식입니다. 저장 공간은 O(n+m)의 크기를 가..