언제나 휴일

[C언어 알고리즘] 7.3.3 프림 알고리즘 소스 코드다음은 C언어로 작성한 프림(Prim) 알고리즘 소스 코드입니다. 동적 배열과 정점과 간선을 이용한 그래프를 구현하여 사용하고 있습니다. //Array.h#pragma oncetypedef void * Element;typedef struct _Array Array;struct _Array{ Element *base; int capacity; int usage;};typedef Element *Iterator; Array *New_Array();void Delete_Array(Array *arr);void Array_SetSize(Array *arr,int capacity,Element data);void Array_PushBack(Array *arr..

[C언어 알고리즘] 7.3.2 프림 알고리즘 구현이제 프림 알고리즘을 구현해 보아요. 프림 알고리즘에서는 최소 비용의 정점을 선택하는 내부 알고리즘이 필요해요. 프림 알고리즘에서 정점을 선택해 나갈 때 현재까지 선택한 정점에서 갈 수 있는 정점 목록에서 최소 비용의 정점을 선택해야겠죠. 이를 위해 다음과 같은 논리가 필요해요. 정점선택알고리즘(mstree:최소신장트리,graph:원본 그래프) selectedge:= NULL으로 초기화 seek:= graph의 시작 정점 위치 end:= graph의 마지막 정점 위치 반복(seek가 end가 아닐 때) edge:=seek에 있는 간선 조건(edge가 mstree에 선택한 정점을 하나만 포함하고 있을 때) 조건(selectedge가 있다면) 조건(select..

[C언어 알고리즘] 7.3.1 프림 알고리즘에 맞게 그래프 소스 코드 수정이 책에서는 프림 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요. 프림 알고리즘을 구현하기 전에 그래프 알고리즘에 몇 가지 함수를 추가하기로 해요. 먼저 정점의 개수를 구하는 함수를 제공하기로 해요. int Graph_GetVtCnt(Graph *graph); 그리고 그래프의 맨 앞에 있는 정점을 구하는 함수도 제공해요. Vertex Graph_GetFront(Graph *graph); 마지막으로 간선에 특정 정점을 끝점으로 하는지 판별하는 함수를 제공하기로 해요. int Edge_Include(Ed..

[C언어 알고리즘] 7.3 프림(Prim) 알고리즘(최소신장트리 알고리즘) 신장트리는 비중있는 그래프 상에서 정점과 정점 사이에 경로를 단일화한 트리를 말합니다. 그리고 최소신장트리는 정점과 정점 사이의 경로의 합이 최소인 신장트리를 말합니다. 그래프에서 최소신장트리를 만드는 여러가지 방법 중에 가장 많이 알려진 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고 크루스칼 알고리즘은 간선을 추가하면서 최소신장트리를 만드는 방법입니다. 먼저 프림 알고리즘을 살펴봅시다. 프림 알고리즘(graph:원본 그래프) 하나의 정점을 선택한다. 반복(선택한 정점 개수가 graph의 정점 개수보다 작다면) 선택한 정점에서 갈 수 있는 모든 정점 중에 최소 ..

12.3.2 프림 알고리즘 소스 코드앞에서 작성한 프림 알고리즘 소스 코드입니다. //Edge.h#pragma once#include using namespace std;class Edge{ string vt1; string vt2; int weight;public: Edge(string vt1,string vt2,int height); bool Exist(string vt)const; bool Exist(string vt1, string vt2)const; string Other(string vt)const; void View()const; int GetWeight()const; string GetVt1()const; string GetVt2()const;}; //Edge.cpp#include "Edg..

12.3.1 프림 알고리즘 구현이제 프림 알고리즘을 구체적으로 구현해 보아요. 앞에서 작성했던 그래프 부분까지는 매우 비슷합니다. 먼저 간선을 정의합시다.class Edge{두 개의 정점과 간선의 비용이 필요하죠. string vt1; string vt2; int weight;public:생성자는 두 개의 정점과 간선의 비용을 입력 인자로 받습니다. Edge(string vt1,string vt2,int height);특정 정점이 존재하는지 판별하는 메서드를 제공하세요. bool Exist(string vt)const;두 개의 정점을 잇는 간선인지 판별하는 메서드를 제공하세요. bool Exist(string vt1, string vt2)const;하나의 정점을 입력 인자로 받아 다른 나머지 정점을 구하..

12.3 프림 알고리즘신장트리는 비중있는 그래프 상에서 정점과 정점 사이에 경로를 단일화한 트리를 말합니다. 그리고 최소신장트리는 정점과 정점 사이의 경로의 합이 최소인 신장트리를 말합니다. 그래프에서 최소신장트리를 만드는 여러가지 방법 중에 가장 많이 알려진 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있어요. 프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고 크루스칼 알고리즘은 간선을 추가하면서 최소신장트리를 만드는 방법이예요. 먼저 프림 알고리즘을 살펴볼게요.프림 알고리즘(graph:원본 그래프)하나의 정점을 선택한다.반복(선택한 정점 개수가 graph의 정점 개수보다 작다면) 선택한 정점에서 갈 수 있는 모든 정점 중에 최소 비중의 간선으로 이어지는 정점을 선택*정점을 선택할 때 이미 ..

디딤돌 자료구조와 알고리즘 C++ 책 소개 자료구조는 자료를 메모리에 표현하는 구조를 말하며 크게 선형 자료구조와 비 선형 자료구조로 나눠요. 선형 자료구조에는 같은 종류의 자료를 연속적인 메모리에 관리하는 배열과 데이터와 링크로 구성하는 노드들의 선형 집합인 연결리스트가 있어요. 그리고 임시적으로 자료를 보관하는 버퍼로 가장 최근에 보관한 자료를 꺼내주는 스택(Last In First Out)과 가장 먼저 보관한 자료를 꺼내주는 큐(First In First Out)도 선형 자료구조인 배열이나 연결리스트를 이용한 잘 알려진 버퍼입니다. 비 선형 자료구조에는 나무의 뿌리처럼 자료를 보관하는 모습을 계층적으로 표현할 수 있는 트리와 정점과 간선으로 표현하는 그래프 등이 있어요. 이 책에서는 이러한 자료구조..