最小生成树(Kruskal’s Minimum Spanning Tree)
#include#include #include typedef struct{ int src, dest, weight;}Edge;typedef struct{ int vertices, edges_n; Edge *edges;}Graph;typedef struct{ int parent; int rank;}Subset;Graph * createGraph(int vertices, int edges);int compare(const void *a, const void *b);int find(Subset *subsets, int n);void Union(Subset *subsets, int x, int y);void KruskalMST(Graph *graph);int main(void){ /* Let us create following weighted graph 10 0--------1 | \ | 6| 5\ |15 | \ | 2--------3 4 */ int vertices = 4; int edges_n = 5; Graph *graph = createGraph(vertices, edges_n); // add edge 0-1 graph->edges[0].src = 0; graph->edges[0].dest = 1; graph->edges[0].weight = 10; // add edge 0-2 graph->edges[1].src = 0; graph->edges[1].dest = 2; graph->edges[1].weight = 6; // add edge 0-3 graph->edges[2].src = 0; graph->edges[2].dest = 3; graph->edges[2].weight = 5; // add edge 1-3 graph->edges[3].src = 1; graph->edges[3].dest = 3; graph->edges[3].weight = 15; // add edge 2-3 graph->edges[4].src = 2; graph->edges[4].dest = 3; graph->edges[4].weight = 4; KruskalMST(graph); system("pause"); return 0;}Graph * createGraph(int vertices, int edges){ Graph *graph = (Graph *)calloc(1, sizeof(Graph)); graph->vertices = vertices; graph->edges_n = edges; graph->edges = (Edge *)calloc(edges, sizeof(Edge)); return graph;}int compare(const void * a, const void * b){ return ((Edge *)a)->weight > ((Edge *)b)->weight;}/* Find the root of which subset a particular element is in. Using path compression for optimization.*/int find(Subset * subsets, int n){ if (subsets[n].parent != n) { subsets[n].parent = find(subsets, subsets[n].parent); } return subsets[n].parent;}/* Join two subsets into a single subset. Uion by rank for optimization.*/void Union(Subset * subsets, int x, int y){ int x_root = find(subsets, x); int y_root = find(subsets, y); if (subsets[x_root].rank < subsets[y_root].rank) subsets[x_root].parent = y_root; else if (subsets[x_root].rank > subsets[y_root].rank) subsets[y_root].parent = x_root; else { subsets[y_root].parent = x_root; subsets[x_root].rank++; }}/* Using Kruskal's algorithm to find MST in the connected and undirected graph*/void KruskalMST(Graph * graph){ int vertices = graph->vertices; Subset *subsets; subsets = (Subset *)calloc(vertices, sizeof(Subset)); for (int i = 0; i < vertices; i++) { subsets[i].parent = i; } qsort(graph->edges, graph->edges_n, sizeof(Edge), compare); int e = 0, i = 0; Edge *result; result = (Edge *)calloc(vertices - 1, sizeof(Edge)); while (e < vertices - 1) { Edge next_edge = graph->edges[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); if (x != y) { result[e++] = next_edge; Union(subsets, x, y); } } printf("Edges in the constructed MST\n"); for (int i = 0; i < vertices - 1; i++) { printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight); } return;}
最小生成树(Prim’s Minimum Spanning Tree)
#include#include int minKey(int *key, bool *mst_set, int vertices);void primMST(int **graph, int vertices);void printMST(int *parent, int **graph, int vertices);int main(void){/* Let us create the following graph 2 3 (0)--(1)--(2) | / \ | 6| 8/ \5 |7 | / \ | (3)-------(4) 9 */ int vertices = 5; int **graph = NULL; int array[] = { 0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0 }; graph = (int **)calloc(vertices, sizeof(int *)); for (int i = 0; i < vertices; i++) { graph[i] = (int *)calloc(vertices, sizeof(int)); } int k = 0; for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { graph[i][j] = array[k++]; } } primMST(graph, vertices); system("pause"); return 0;}int minKey(int * key, bool * mst_set, int vertices){ int min = INT_MAX; int min_index; for (int i = 0; i < vertices; i++) { if (!mst_set[i] && key[i] < min) { min = key[i]; min_index = i; } } return min_index;}void primMST(int ** graph, int vertices){ int *parent, *key; bool *mst_set; parent = key = NULL; mst_set = NULL; parent = (int *)calloc(vertices, sizeof(int)); key = (int *)calloc(vertices, sizeof(int)); mst_set = (bool *)calloc(vertices, sizeof(bool)); for (int i = 0; i < vertices; i++) { key[i] = INT_MAX; } key[0] = 0; parent[0] = -1; for (int i = 0; i < vertices - 1; i++) { int n = minKey(key, mst_set, vertices); mst_set[n] = true; for (int j = 0; j < vertices; j++) { if (graph[n][j] && !mst_set[j] && graph[n][j] < key[j]) { key[j] = graph[n][j]; parent[j] = n; } } } printMST(parent, graph, vertices);}void printMST(int * parent, int ** graph, int vertices){ printf("edge\tweight\n"); for (int i = 1; i < vertices; i++) { printf("%d - %d\t%d\n", parent[i], i, graph[parent[i]][i]); }}
霍夫曼编码(Huffman Coding)
#include#include /* A Huffman tree node */typedef struct MinHeapNode{ char data; int frequency; struct MinHeapNode *left, *right;}MinHeapNode;/* A Min Heap */typedef struct{ int size; int capacity; MinHeapNode **array;}MinHeap;MinHeap * createMinHeap(int capacity);MinHeapNode * newNode(char data, int frequency);void swapMinHeapNode(MinHeapNode **a, MinHeapNode **b);void minHeapify(MinHeap *min_heap, int key);MinHeap * buildMinHeap(char *data, int *frequency, int size);MinHeapNode *extractMin(MinHeap *min_heap);void insertMinHeap(MinHeap *min_heap, MinHeapNode *min_heap_node);MinHeapNode * buildHuffmanTree(char *data, int *frequency, int size);void huffmanCoding(char *data, int *frequency, int size);void printCodes(MinHeapNode *root, char *codes, int depth);int main(void){ int n = 6; char array[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int frequency[] = { 5, 9, 12, 13, 16, 45 }; huffmanCoding(array, frequency, n); system("pause"); return 0;}/* Create a min heap whose size is zero */MinHeap * createMinHeap(int capacity){ MinHeap *min_heap = (MinHeap *)calloc(1, sizeof(MinHeap)); min_heap->size = 0; min_heap->capacity = capacity; min_heap->array = (MinHeapNode **)calloc(capacity, sizeof(MinHeapNode *)); return min_heap;}MinHeapNode * newNode(char data, int frequency){ MinHeapNode *node = (MinHeapNode *)calloc(1, sizeof(MinHeapNode)); node->left = node->right = NULL; node->data = data; node->frequency = frequency; return node;}void swapMinHeapNode(MinHeapNode ** a, MinHeapNode ** b){ MinHeapNode *temp = *a; *a = *b; *b = temp;}void minHeapify(MinHeap * min_heap, int key){ int left = (key << 1) + 1; int right = (key << 1) + 2; int smallest = key; if (left < min_heap->size && min_heap->array[left]->frequency < min_heap->array[smallest]->frequency) smallest = left; if (right < min_heap->size && min_heap->array[right]->frequency < min_heap->array[smallest]->frequency) smallest = right; if (smallest != key) { swapMinHeapNode(&min_heap->array[key], &min_heap->array[smallest]); minHeapify(min_heap, smallest); }}MinHeap * buildMinHeap(char * data, int * frequency, int size){ MinHeap *min_heap = createMinHeap(size); for (int i = 0; i < size; i++) { min_heap->array[i] = newNode(data[i], frequency[i]); } min_heap->size = size; for (int i = (size >> 1) - 1; i >= 0; i--) { minHeapify(min_heap, i); } return min_heap;}MinHeapNode * extractMin(MinHeap * min_heap){ MinHeapNode *min = min_heap->array[0]; min_heap->array[0] = min_heap->array[min_heap->size - 1]; min_heap->size--; minHeapify(min_heap, 0); return min;}void insertMinHeap(MinHeap * min_heap, MinHeapNode * min_heap_node){ int i = min_heap->size; min_heap->size++; while (i && min_heap_node->frequency < min_heap->array[(i - 1) >> 1]->frequency) { min_heap->array[i] = min_heap->array[(i - 1) >> 1]; i = (i - 1) >> 1; } min_heap->array[i] = min_heap_node;}MinHeapNode * buildHuffmanTree(char * data, int * frequency, int size){ MinHeap *min_heap = buildMinHeap(data, frequency, size); MinHeapNode *left, *right, *top; while (min_heap->size != 1) { left = extractMin(min_heap); right = extractMin(min_heap); top = newNode('$', left->frequency + right->frequency); top->left = left; top->right = right; insertMinHeap(min_heap, top); } return extractMin(min_heap);}void huffmanCoding(char * data, int * frequency, int size){ MinHeapNode *root = buildHuffmanTree(data, frequency, size); char codes[100] = { 0 }; printCodes(root, codes, 0);}void printCodes(MinHeapNode * root, char * codes, int depth){ if (root->left) { codes[depth] = '0'; printCodes(root->left, codes, depth + 1); } if (root->right) { codes[depth] = '1'; printCodes(root->right, codes, depth + 1); } if (!(root->left) && !(root->right)) { printf("%c: ", root->data); for (int i = 0; i <= depth; i++) { printf("%c", codes[i]); } printf("\n"); }}