'에지 리스트' 태그의 글 목록

Algorithm 공부 #13 - 그래프(그래프의 표현) 에지 리스트(edge list) ● 에지를 중심으로 그래프를 표현 ● 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현 ● 배열에 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현 인접 행렬(adjacency matrix) ● 2차원 배열을 자료구조를 이용하여 그래프를 표현 ● 노드를 중심으로 그래프를 표현 ● 노드와 관련되어 있는 에지를 탐색하기 위해서는 N번 접근해야 하므로 시간복잡도가 인접 리스트에 비해 느림 ● 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐 인접 리스트(adjacency list) ● 2차원 벡터로 그래프를 표현 ● 구현은 복잡하나 노드와 연결된 에지를 탐색하는 시간이 뛰어나며, 노드 개수가..