C31 [C] Prim Algorithm 코드 보완 2023.10.06 - [C/알고리즘] - [C] Prim Alogrithm [C] Prim Alogrithm 1. 신장트리 (Spanning Tree): n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 이루어진 트리 : 사이클 발생하면 안됨 사이클 없이 모든 정점 포함하는 트리 1-1. 최 growingupis.tistory.com PriorityQueue.h #include #include #include #include #define MAX_HEAP_SIZE 100 typedef struct _HEAP_NODE_ { int start; int end; int distance; }HEAP_NODE; typedef struct _HEAP_TREE_ { int n; .. 2024. 2. 13. [C] 정렬 알고리즘 1. Selection Sort #include #include #include #include #include #define DATASIZE 16 int* generateRand( int , int ); void selectionSort(int* data, int, int); void swap(int*, int*); int main() { int i; int* data = generateRand(100, DATASIZE); printf("\nBefor sorting array\n"); for (i = 0; i < DATASIZE; i++) { printf("%d ", data[i]); } printf("\n"); selectionSort(data, DATASIZE, 1); for (i = 0; i < .. 2024. 2. 12. [C] 이중 연결 리스트 #define _CRT_SECURE_NO_WARNINGS #include #include #include typedef struct _NODE_ { int data; struct _NODE_* llink; struct _NODE_* rlink; }NODE; typedef struct _LINKED_LIST_ { NODE* head; }LINKED_LIST; LINKED_LIST* createLinkedList() { LINKED_LIST* CL = (LINKED_LIST*)calloc(1, sizeof(LINKED_LIST)); assert(CL != NULL); return CL; } void insertFirstNode(LINKED_LIST* CL, int x) { NODE* newNode = (NO.. 2024. 2. 6. [C] Prim Alogrithm 1. 신장트리 (Spanning Tree): n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 이루어진 트리 : 사이클 발생하면 안됨 사이클 없이 모든 정점 포함하는 트리 1-1. 최소 비용 신장 트리 (MST, Minimum cost Spanning Tree): 무방향 가중치 그래프에서 신장 트리 구성하는 간선들의 가중치 합이 최소인 신장트리 ex) Kruskal Algorithm, Prim Algorithm 2. Prim Algorithm: 우선순위 큐를 이용하는 알고리즘 : 간선을 정렬하지않고 하나의 정점에서 트리를 확장해나가는 방법 2-1. 동작방식그래프 G에서 시작 정점 선택 ( 대부분의 경우 1로 설정)선택한 정점에 부속된 모든 간선 중 가장 낮은 간선 연결.. 2023. 10. 6. [C]수식 트리 - Evaluate Tree 1. 수식트리 : 산술식을 트리형태로 표현 : 컴파일러가 수식을 처리하는 방식 : 단말노드 => 피연산자, 비단말노드 => 연산자 2. 수식 트리 계산 중위 표기법 수식 -> 후위 표기법 수식 -> 수식 트리 -> 수식 트리 계산 중위 표기법 수식 -> 후위 표기법 수식 : 스택 이용 후위 표기법 수식 -> 수식 트리 : 스택 이용 수식 트리 -> 수식 트리 계산 : 후위순회 이용 2-1. 후위 표기법 수식 : 스택 이용 https://growingupis.tistory.com/32?category=1186559 스택 응용(수식 계산) 1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(po.. 2023. 9. 22. [C]트리 레벨 순회 - Level Order Traverse : 각 노드를 레벨 순으로 탐색하는 방법으로 큐 (너비우선탐색, BFS) 이용하여 구현 #define _CRT_SEUCRE_NO_WARNINGS #include #include #include #include #define SIZE 128 typedef struct _TREENODE_ { char data; struct _TREENODE_* left; struct _TREENODE_* right; }TREENODE; void deleteTree(TREENODE* node) { if (node == NULL) { return; } else { deleteTree(node->left); deleteTree(node->right); free(node); node = NULL; } } TREENODE* make.. 2023. 9. 22. 이전 1 2 3 4 ··· 6 다음
