Prim 알고리즘 Prim('프림') 알고리즘은 최소 비용 신장 트리를 만드는 방법 중 하나이다. Prim 알고리즘은 트리를 점점 확장시켜 최소 비용 신장트릴 만드는 방법이다. Krusal 알고리즘은 처음부터 모든 노드를 추가하고 시작했지만 prim 알고리즘의 시작노드는 1개이다. 또한 krusal 알고리즘은 모든 간선중 최소비용을 가지는 간선을 우선으로 고려했다면 prim 알고리즘은 현재 신장트리가 포함중인 노드에 부속된 간선들 중에서 최소 비용을 가지는 간선을 우선으로 고려한다는 차이점이 있다. 아래 표를 통해 자세히 알아보자 초기화 그래프 G에서의 임의의 시작 노드 r을 선택하여, 신장 트리 H를 초기화 V(H) = r E(H) = 0 (공집합) 루프 Step-1 V(H)와 부속된 간선들 중에서 (..

Kruskal 알고리즘 Kruskal('크루스칼') 알고리즘은 최소 비용 신장 트리를 만드는 방법 중 하나이다. Kruskal 알고리즘은 그래프의 모든 간선을 비용 순으로 정렬한 다음, 낮은 비용을 가지는 간선을 차례대로 선택하여 신장 트리를 완성해 가는 방법이다. 아래 표를 통해 자세히 알아보자 초기화 (1) 그래프 G의 최 소 비용 신장 트리 H를 다음과 같이 초기화한다. H= (V(G),E(H)) 단, (E(H))= 0 (공집합) (2) 그래프 G의 모든 간선을 가중치 값에 따라 오름차순으로 정렬한다. 루프 Step-1 정렬된 간선들 중에서 (1) 가장 가중치가 작으면서 (2) 순환을 발생시키지 않는 간선 e를 추출 Step-2 그래프 G의 모든 노드가 연결될 때까지 step-1 을 반복한다. 가장..

신장 트리(Spanning Tree)의 개념 앞서 그래프에 대한 내용을 다루었다. 내용을 살펴보면 그래프 G는 노드 V와 간선 E의 집합으로 정의된다는 것을 알 수 있다. 다시 정리하자면 그래프는 노드와 노드들을 연결하는 간선들의 집합으로 구성되어있고 그래프의 정의를 식으로 나타내면 G=(V,G)이다. 이번에 다룰 내용은 일반적인 그래프 G에 대한 신장 트리(Spanning Tree)에 관한 것이다. 여기서 ‘신장(spanning)’은 모든 노드를 포함한다는 뜻이다. 만약 노드가 5개인 그래프 G에 대해 신장트리를 만든다고 한다면 신장트리는 반드시 저 5개 노드를 포함하고 있어야 한다. 하지만 신장 트리도 엄연히 트리의 일종이기 때문에 그래프와 다른 트리의 특징인 순환 구조를 가지면 안된다. 정리하자면 ..

넓이-우선 탐색 넓이 우선 탐색은 현재 방문한 노드 이전 노드에 인접한 노드를 우선적으로 방문하는 탐색 알고리즘이다. 큐로 구현하는 넓이-우선 탐색 넓이 우선 탐색은 이전 노드를 기록을 가지고 있어야 하기 때문에 재귀적으로 동작하지 않는다. 우리는 넓이 우선 탐색을 구현하기 위해서 큐의 '선입선출' 특성을 이용할 것이다. 우리는 방문한 노드와 인접한 노드들을 큐에 추가할 것이고 큐는 '선입선출' 특성을 가지기 때문에 현재 노드와 인접한 노드보다 이전 노드와 인접한 노드들을 먼저 반환할 것이다. 아래는 큐를 이용한 BFS의 의사 코드이다. BFS(node v){ 큐 Q v (방문 처리); Q.enqueue(V) while(! is_Empty(Q)) u=Q.dequeue() for( all w (u의 인접 ..

그래프 탐색(Search 혹은 Traversal) 그래프의 탐색은 간선을 이용하여 그래프 상의 모든 노드를 한 번씩 방문하는 것을 말한다. 예를 들어 한 도시를 기점으로 모든 도시를 방문하고자 한다면 우리는 어떤 순서로 방문해야 모든 도시를 방문할 수 있을까? 이를 해결하기 위한 그패트의 탐색 방법으로 가장 대표적이고 기초적인 2가지 방법이 있다. 1) 깊이-우선 탐색(DFS: Depth-First Search) 2) 넓이-우선 탐색(BFS: Breadth-First Search) 깊이 우선 탐색은 현재 방문한 노드와 인접한 노드를 우선이 하는 탐색 방법이고 넓이 우선 탐색은 현재 방문한 노드보다 우선적으로 이전 노드에서 방문하지 않고 인접한 노드를 우선 탐색한다. 아래 그림을 통해 간단히 설명해보자. ..

dsbook.tistory.com/280 (이전글) C로 만드는 자료구조 - 그래프(Graph)란? 그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 dsbook.tistory.com 인접행렬을 이용한 그래프 구현 그래프 G의 각 도드 사이의 간선을 2차원 배열로 저장하는 것이다. 각 노드 사이에 간선이 존재할 경우 해당 배열의 값을 1로 없을때는 0으로 저장한다. 여기서 무방향 그래프라면 반대로 똑같이 1로 저장해주면 된다. 무방향 그래프의 이러한 성질을 대칭성(symmetry)라고 한다. 참고로 인접 행렬에서 각 노드의 차수를 구하고 싶다면 인접 행렬의 각 행 또..

dsbook.tistory.com/280 (이전글) C로 만드는 자료구조 - 그래프(Graph)란? 그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 dsbook.tistory.com 그래프 관련 용어들 그래프를 실제 규현하고 그래프 기반의 다양한 알고리즘을 살펴보기 전에 그래프와 관련된 용어들을 알아보자. 인접(Adjacent) 두 개의 노드를 연결하는 간선이 존재하는 경우 두 노드는 인접(Adjacent)되었다고 한다. 다음 그림을 통해 자세히 살펴보자. 부속(Incident) 두 개의 노드를 연결하는 간선이 존재하는 경우 이 간선은 두 노드에 각각 부속(Inci..

dsbook.tistory.com/280 (이전글) C로 만드는 자료구조 - 그래프(Graph)란? 그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 dsbook.tistory.com 이전 글에서 표로 정리한 그래프 종류에 대해 자세히 알아보자 구분 종류 설명 간선의 방향성 무방향 그래프 간선에 방향이 없는 그래프 방향 그래프 간선에 방향이 있는 그래프 간선의 가중치 가중 그래프 간선에 가중치가 할당된 그래프 구조적 특징 완전 그래프 연결가능한 최대 간선 수를 가진 그래프 부분 그래프 원래의 그래프에서 일분의 노드나 간선을 제외하여 만든 그래프 다중 그래프 중복된 간..

그래프(Graph)란? 그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다. 지금까지 설명한 자료구조 중에서 가장 현실 세계의 다양한 문제들을 효과적으로 모델링 할 수 있을 정도로 표현 능력이 매우 우수하다. 다음 그림은 우리나라의 고속도로 지도이다. 각 도시를 연결하는 고속도로를 자료구조로 나타낼 수 있을까? 앞서 소개한 자료구조 중에서 선형 자료인 리스트,스택,큐 같은 경우는 객체들의 선,후 관계 밖에 나타내지 못하기 때문에 1:1인 관계가 아닌 것이 존재하는 고속도로를 표현하기에는 적합하지 못하다. 하나의 객체가 여러개의 객체와의 관계를 나타낼 수 있는 자료구조인 트리는 부모 자식 간의 관계만 나타낼 수 있고 일반적인 관계는 나타내지 못한다는 한계가 있다. 각 도시를 연결하는 고속도로 같은 경우..

dsbook.tistory.com/270 C로 만드는 자료구조 - 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리 (Binary Search Tree)란? 이진 탐색 트리는 이진 트리에서 탐색(Search)란 단어가 들어가 있다. 탐색이 뜻하는 바와 같이 이진 트리에서 '자료의 검색'이 주된 기능이 된다. 이진 탐색 트 dsbook.tistory.com 연결 리스트를 이용한 이진 탐색 트리 구현 소스 파일 구성은 다음과 같다. 파일 이름 내용 binsearchtree.h 구조체 및 함수 선언 binsearchtree.cpp 함수 구현 binsearchtreemain.cpp main 함수 실행 1.binsearchtree.h 구현하기 앞서 힙의 추상자료형을 다시 한번 보자 이름 입력 출..