Thuật toán Kruskal – Cài đặt Kruskal algorithm sử dụng C/C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
// C++ implementation of Kruskal's Algorithm to find the Minimum Spanning tree for a weighted, connected and undirected graph. #include <iostream> #include <climits> #define n 6 int parent[n]; // Parent array to hold the parent nodes of each node in the graph using namespace std; void printMST(int a[n], int b[n], int weight[n]) // Printing the MST { int Minweight = 0; // Weight of Minimum spanning tree for (int i = 0; i < n - 1; i++) { cout << "Edge: " << a[i] << "-" << b[i] << " " << "cost: " << weight[i] << endl; Minweight += weight[i]; } cout << "Minimum Weight is " << Minweight << endl; // Printing the weight of MINIMUM SPANNING TREE } int findParent(int node) // Function to determine the parent node { while(parent[node] >= 0) node = parent[node]; return node; } /* "findParentPathCompression" is an alternative for "findParent" which is more efficient. * We use a technique called "path compression" here. * With path compression, we destroy the structure of the tree, and only focus on which group a node is in. */ int findParentPathCompression(int node) { if(node == parent[node]) return node; return parent[node] = findParentPathCompression(parent[node]); } void kruskal(int cost[n][n]) // Function performing Kruskal's algorithm { fill_n(parent, n, -1); int u, v, k = 0, count = 0; int firstNode, secondNode; int a[n]; // Array containing the first nodes of all the edges present in MST int b[n]; // Array containing the second nodes of all the edges present in MST int weight[n]; // Array containing the weights of the edges present in MST int minimum; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (cost[i][j] == 0) // If i and j nodes are not adjacent cost[i][j] = INT_MAX; // Then, initialize their weight as INFINITE while(count < n-1) { minimum = INT_MAX; // Initializing minimum as INFINITE for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (cost[i][j] < minimum) { minimum = cost[i][j]; // find the minimum cost edge firstNode = i; // First node of determined edge secondNode = j; // Second node of determined edge } } } u = findParent(firstNode); v = findParent(secondNode); if (u != v) // If parents of both the nodes are different, no circuit is being formed { parent[v] = u; a[k] = firstNode; // Store first node in array b[k] = secondNode; // Store second node in array weight[k] = cost[firstNode][secondNode]; // Store the determined edge's weight in array count++; k++; } cost[firstNode][secondNode] = cost[secondNode][firstNode] = INT_MAX; // Edges getting included in MST will be given the weight of INFINITE } printMST(a, b, weight); // Printing the MST } // Driver program to test above function int main() { /* Let the given graph is : (1)____1___(2) / \ / \ 3 4 4 6 / \ / \ / \ / \ (0)___5___(5)____5___(3) \ | / \ | / \ | / \ 2 / 6 | 8 \ | / \ | / \ | / \ | / (4) */ int cost[n][n] = { { 0, 3, 0, 0, 6, 5 }, { 3, 0, 1, 0, 0, 4 }, { 0, 1, 0, 6, 0, 4 }, { 0, 0, 6, 0, 8, 5 }, { 6, 0, 0, 8, 0, 2 }, { 5, 4, 4, 5, 2, 0 } }; kruskal(cost); return 0; } /* Output : Edge: 0-1 cost: 3 Edge: 1-2 cost: 1 Edge: 1-5 cost: 4 Edge: 5-4 cost: 2 Edge: 5-3 cost: 5 Minimum Weight is 15 */ |