자료구조2 그래프란 그래프란 노드(N : Node)와 그 노드를 연결하는 간선(E: Edge)을 하나로 모아 놓은 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다. ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들 그래프(Graph)와 관련된 용어 정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 진입 차수(in-degree): 방향 그래프에.. 2022. 4. 22. 힙(heap) 자료구조 힙(heap)이란 - 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. - 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. - 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 key(부모 노드) 2022. 3. 16. 이전 1 다음
