언제나 휴일

12.4.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#incl..

12.4.1 크루스칼 알고리즘 구현간선은 프림 알고리즘에서 구현한 것과 차이가 없습니다. 그래프도 대부분 비슷합니다. 여기에서는 차이가 있는 부분만 설명할게요. 이번에는 간선을 선택할 때 간선의 비중이 같을 때 그래프에 먼저 추가한 간선을 선택하게 합시다. 이를 위해 Graph에 간선을 추가하는 부분을 수정할게요.bool Graph::AddEdge(string vt1, string vt2,int weight)//간선 추가{ if(Exist(vt1)&&Exist(vt2)) { if(Exist(vt1,vt2)) { return false; } CEIter seek = edges.begin(); CEIter last = edges.end(); for( ;seek != last; ++seek) {프림 알고리즘에..

12.4 크루스칼 알고리즘이번에는 크루스칼 알고리즘으로 최소신장트리를 만드는 방법을 알아봅시다. 프림 알고리즘은 최적의 정점을 선택하여 최소신장트리를 만드는 방법입니다. 반면 크루스칼 알고리즘은 최적의 간선을 선택하여 최소신장트리를 만드는 방법입니다. 크루스칼 알고리즘선택한 간선 0으로 설정원본 그래프의 간선 집합을 복제복제한 간선 집합을 비중 순으로 정렬반복(선택한 간선 개수가 graph의 정점 개수-1 보다 작다면) 조건(탐욕스런 간선을 선택이 실패 반복문 탈출 아니면 선택한 간선 개수 1 증가 최적의 간선은 비중이 작은 간선 중에 선택합니다. 그런데 선택한 간선을 현재까지 만들고 있는 그래프(최소신장트리)에 추가하였을 때 사이클이 발생하지 말아야 합니다. 이를 효과적으로 구현하기 위해 원본 그래프의..

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의 정점 개수보다 작다면) 선택한 정점에서 갈 수 있는 모든 정점 중에 최소 비중의 간선으로 이어지는 정점을 선택*정점을 선택할 때 이미 ..

그래프 그래프 정점(Vertex)와 간선(Edge)의 입합 트리는 사이클이 없는 그래프 차수: 하나의 정점과 연결한 간선의 수 진입차수(Indegree): 한 정점에 도착하는 간선의 수 진출차수(Outdegree): 한 정점에서 출발하는 간선의 수 경로(Path): 한 정점에서 다른 정점으로 가는 간선 집합 단순 경로(Simple Path): 같은 간선을 지나가지 않는 경로 사이클(Cycle): 시작과 끝이 같은 경로 최소신장트리(Minimal Spanning Tree) 그래프에서 정점과 정점사이의 경로를 최소 비용으로 구성한 트리 간선 작업(AOE, Activity On Edge) 네트워크 프로젝트를 수행하기 위한 작업 순서를 나타낸 방향있는 그래프 *자료구조와 알고리즘은 게시판으로 별도로 다루고 있습..