Programming 썸네일형 리스트형 HeapNode : 힙에 저장할 노드 클래스 / Kruskal의 최소 비용 신장 트리 프로그램을 위한 노드 클래스 #pragma once#ifndef ___HeapNode#define ___HeapNode//HeapNode : 힙에 저장할 노드 클래스//Kruskal의 최소 비용 신장 트리 프로그램을 위한 노드 클래스#include class HeapNode {int key;//key값int v1;//정점 1int v2;//정점 2public:HeapNode(int k = 0) : key(k) {}HeapNode(int k, int u, int v) : key(k), v1(u), v2(v) {}void setKey(int k) { key = k; }void setKey(int k, int u, int v) { key = k; v1 = u; v2 = v; }int getKey() { return key; }int ge.. 더보기 VertexSet.h : Union-Find 연산을 위한 정점 집합 클래스 구현 #pragma once#ifndef ___VertexSets#define ___VertexSets//VertexSet.h : Union-Find 연산을 위한 정점 집합 클래스 구현#define MAX_VTXS 256class VertexSets {int parent[MAX_VTXS];//부모 정점의 idint nSets;//집합의 개수public:VertexSets(int n) : nSets(n) {for (int i = 0; i < nSets; i++)parent[i] = -1;//모든 정점이 고유의 집합에 속함}bool isRoot(int i) { return parent[i] < 0; }int findSet(int v) {while (!isRoot(v)) v = parent[v];return v;}.. 더보기 WGraph.h : 가중치 그래프 클래스 #pragma once#ifndef ___WGraph#define ___WGraph//WGraph.h : 가중치 그래프 클래스#include "AdjMatGraph.h"#define INF 9999//값이 INF 이상이면 간선이 없음 //가중치 그래프를 표현하는 클래스class WGraph : public AdjMatGrapgh { //AdjMatGraph 클래스를 상속public:void insertEdge(int u, int v, int weight) {if (weight > INF) weight = INF;setEdge(w, v, weight);}bool hasEdge(int i, int j) { return getEdge(i, j) < INF; }void load(const char* filena.. 더보기 TopoSortGraph.h : 위상 정렬 기능이 추가된 인접 리스트 기반 그래프 #pragma once#ifndef ___TopoSort#define ___TopoSort//TopoSortGraph.h : 위상 정렬 기능이 추가된 인접 리스트 기반 그래프#include "AdjListGraph.h"#include "ArrayStack.h" class TopoSortGraph : public AdjListGraph {int inDeg[MAX_VTXS];//정점의 진입차수public:void insertDirEdge(int u, int v) {//방향성 간선 삽입 연산adj[u] = new Node(v, adj[u]);}// 위상정렬을 수행한다.void TopoSort() {//모든 정점의 진입 차수를 계산 for (int i = 0; i < size; i++)//초기화inDeg[i] .. 더보기 DataStructure - 신장 트리, Kruskal 의 MST 알고리즘, 위상 정렬 신장 트리 신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리다. 신장 트리도 트리의 일종이므로 모든 정점들이 연결되어 있고 사이클이 없어야 한다. 신장트리는 그래프에 있는 n개의 정점을 정확히(n-1)개의 간선으로 연결하게 된다. 신장 트리를 찾기위해 기피 우선 탐색이나 너비 우선 탐색을 이용할 수 있는데, 하나의 그래프에는 많은 신장 트리가 가능한 것에 유의하라. 신장트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선들만 모으면 만들 수 있다. 최소 비용 신장 트리 최소 비용 신장 트리(MST : minimum spanning tree) 란 어떤 그래프의 신장 트리들 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 최소 비용 신장 트리를 구하는 방법에는.. 더보기 SrchALGraph.h ; 탐색 기능이 추가된 인접 리스트 기반 그래프 클래스 #pragma once#ifndef ___SrchALGraph#define ___SrchALGraph//SrchALGraph.h ; 탐색 기능이 추가된 인접 리스트 기반 그래프 클래스#include "AdjListGraph.h"#include "CircularQueue.h" class SrchALGraph : public AdjListGraph {bool visited[MAX_VTXS];//정점의 방문 정보public:void resetVisited() {//모든 정점을 방문하지 않았다고 설정for (int i = 0; i .. 더보기 SrchAMGraph : 탐색 기능이 추가된 행렬 기반 그래프 클래스 #pragma once#ifndef ___SrchAMGragh#define ___SrchAMGraph//SrchAMGraph : 탐색 기능이 추가된 행렬 기반 그래프 클래스#include "AdjMatGraph.h"#include "CircularQueue.h"class SrchAMGraph : public AdjMatGrapgh {bool visited[MAX_VTXS];//정점의 방문 정보public:void resetVisited() {//모든 정점을 방문하지 않았다고 설정for (int i = 0; i < size; i++)visited[i] = false;}bool isLinked(int u, int v) { return getEdge(u, v) != 0; } //깊이 우선 탐색 함수void D.. 더보기 AdjListGraph.h : 인접 리스트를 이용한 그래프 클래스 #pragma once#ifndef ___AdjListGraph#define ___AdjListGraph//AdjListGraph.h : 인접 리스트를 이용한 그래프 클래스#include "Node_Adj.h"//연결 리스트를 위한 노드 그래프 클래스 포함#define MAX_VTXS256class AdjListGraph {protected:int size;//정점의 개수char vertices[MAX_VTXS];//정점 정보(응용에 따라 확장 필요)Node* adj[MAX_VTXS];//각 정점의 인접 리스트public:AdjListGraph() : size(0) {}~AdjListGraph() { reset(); }void reset(void) {for (int i = 0; i < size; i++).. 더보기 이전 1 ··· 13 14 15 16 17 18 19 ··· 38 다음