پیاده سازی پریم و کروسکال برای n=100 , 99<=m<=50(99) اجرا کنید و زمان اجرا را در فایل…
- User
پیاده سازی پریم و کروسکال برای n=100 , 99<=m<=50(99) اجرا کنید و زمان اجرا را در فایل ذخیره کنید.چک کنید خروجی دو الگوریتم یکسان باشد.نقطه ای مانند n پیدا کنید که زمان کروسکال بیشتر باشد
- Assistant
با توجه به دادههای ارائه شده، می توان پیادهسازی الگوریتم پریم و کروسکال را برای n=100 و 99≤m≤50(99) انجام داد. اما زمان اجرای الگوریتمها بستگی به ساختار دقیق گراف و حالت مسئله دارد و بر حسب نمونه دادهها نمی توان نقطهای مانند n را تعیین کرد که زمان کروسکال بیشتر باشد. زیرا زمان اجرای الگوریتمها بستگی به تعداد یالها و مدت زمانی که الگوریتم برای پیدا کردن یک یال مناسب برای اضافه کردن به درخت کمینه میباشد.
بیایید پیادهسازی این الگوریتمها در پایتون را بررسی کنیم:
الگوریتم پریم:
import sys class Prim: def __init__(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)] for row in range(vertices)] def printMST(self, parent): with open('output.txt', 'a') as f: f.write("Edge \t Weight\n") for i in range(1, self.V): f.write(str(parent[i]) + " - " + str(i) + "\t" + str(self.graph[i][parent[i]]) + "\n") def minKey(self, key, mstSet): min = sys.maxsize for v in range(self.V): if key[v] < min and mstSet[v] == False: min = key[v] min_index = v return min_index def primMST(self): key = [sys.maxsize] * self.V parent = [None] * self.V key[0] = 0 mstSet = [False] * self.V parent[0] = -1 for cout in range(self.V): u = self.minKey(key, mstSet) mstSet[u] = True for v in range(self.V): if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]: key[v] = self.graph[u][v] parent[v] = u self.printMST(parent)الگوریتم کروسکال:
class Kruskal: def __init__(self, vertices): self.V = vertices self.graph = [] def addEdge(self, u, v, w): self.graph.append([u, v, w]) def find(self, parent, i): if parent[i] == i: return i return self.find(parent, parent[i]) def union(self, parent, rank, x, y): xroot = self.find(parent, x) yroot = self.find(parent, y) if rank[xroot] < rank[yroot]: parent[xroot] = yroot elif rank[xroot] > rank[yroot]: parent[yroot] = xroot else: parent[yroot] = xroot rank[xroot] += 1 def kruskalMST(self): result = [] i = 0 e = 0 self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] for node in range(self.V): parent.append(node) rank.append(0) while e < self.V - 1: u, v, w = self.graph[i] i = i + 1 x = self.find(parent, u) y = self.find(parent, v) if x != y: e = e + 1 result.append([u, v, w]) self.union(parent, rank, x, y) with open('output.txt', 'a') as f: f.write("Edge \t Weight\n") for u, v, weight in result: f.write(str(u) + " - " + str(v) + "\t" + str(weight) + "\n")حال میتوانیم الگوریتم را با استفاده از دادههای ورودی مورد نظر اجرا کرده و زمان اجرا را در فایل ذخیره کنیم:
import time n = 100 m = 99 start = time.time() # ایجاد شیء از کلاس Prim و اجرای الگوریتم g1 = Prim(n) g1.primMST() end = time.time() execution_time = end - start with open('output.txt', 'a') as f: f.write("Prim Execution Time: " + str(execution_time) + "\n") start = time.time() # ایجاد شیء از کلاس Kruskal و اجرای الگوریتم g2 = Kruskal(n) for i in range(m): u, v, w = input().split() g2.addEdge(int(u), int(v), int(w)) g2.kruskalMST() end = time.time() execution_time = end - start with open('output.txt', 'a') as f: f.write("Kruskal Execution Time: " + str(execution_time) + "\n")در نهایت، زمان اجرای الگوریتمها در فایل output.txt ذخیره میشود و می توان آن را بررسی کرد.
- User
پیاده سازی پریم و کروسکال برای n=100 , 99<=m<=50(99) اجرا کنید و زمان اجرا را در فایل ذخیره کنید.چک کنید خروجی دو الگوریتم یکسان باشد.نقطه ای مانند n پیدا کنید که زمان کروسکال بیشتر باشد c++
- Assistant
با توجه به اینکه میخواهید پیادهسازی الگوریتمهای پریم و کروسکال را در C++ انجام دهید، در ادامه پیادهسازی الگوریتمهای مذکور در C++ را بررسی خواهیم کرد.
الگوریتم پریم:
#include<iostream> #include<vector> #include<climits> using namespace std; class Prim { private: int V; vector<vector<int>> graph; public: Prim(int vertices) { V = vertices; graph = vector<vector<int>>(vertices, vector<int>(vertices, 0)); } void printMST(vector<int>& parent) { ofstream outputFile; outputFile.open("output.txt", ios_base::app); outputFile << "Edge \t Weight\n"; for (int i = 1; i < V; i++) { outputFile << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl; } outputFile.close(); } int minKey(vector<int>& key, vector<bool>& mstSet) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) { if (mstSet[v] == false && key[v] < min) { min = key[v]; min_index = v; } } return min_index; } void primMST() { vector<int> key(V, INT_MAX); vector<int> parent(V, 0); vector<bool> mstSet(V, false); key[0] = 0; parent[0] = -1; for (int count = 0; count < V - 1; count++) { int u = minKey(key, mstSet); mstSet[u] = true; for (int v = 0; v < V; v++) { if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) { parent[v] = u; key[v] = graph[u][v]; } } } printMST(parent); } };الگوریتم کروسکال:
#include<iostream> #include<vector> #include<algorithm> #include<fstream> using namespace std; class Kruskal { private: int V; vector<vector<int>> graph; public: Kruskal(int vertices) { V = vertices; graph = vector<vector<int>>(); } void addEdge(int u, int v, int w) { graph.push_back({ u, v, w }); } int find(vector<int>& parent, int i) { if (parent[i] == i) return i; return find(parent, parent[i]); } void unionSet(vector<int>& parent, vector<int>& rank, int x, int y) { int xroot = find(parent, x); int yroot = find(parent, y); if (rank[xroot] < rank[yroot]) parent[xroot] = yroot; else if (rank[xroot] > rank[yroot]) parent[yroot] = xroot; else { parent[yroot] = xroot; rank[xroot]++; } } void kruskalMST() { ofstream outputFile; outputFile.open("output.txt", ios_base::app); vector<pair<int, pair<int, int>>> result; int i = 0, e = 0; sort(graph.begin(), graph.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; }); vector<int> parent(V), rank(V); for (int node = 0; node < V; node++) { parent[node] = node; rank[node] = 0; } while (e < V - 1 && i < graph.size()) { int u = graph[i][0]; int v = graph[i][1]; int w = graph[i][2]; i++; int x = find(parent, u); int y = find(parent, v); if (x != y) { e++; result.push_back({ u, {v, w} }); unionSet(parent, rank, x, y); } } outputFile << "Edge \t Weight\n"; for (i = 0; i < result.size(); i++) { int u = result[i].first; int v = result[i].second.first; int weight = result[i].second.second; outputFile << u << " - " << v << "\t" << weight << endl; } outputFile.close(); } };حال میتوانید این الگوریتمها را با استفاده از دادههای ورودی مورد نظر اجرا کرده و زمان اجرا را در فایل ذخیره کنید:
#include<iostream> #include<fstream> #include<chrono> using namespace std; using namespace std::chrono; int main() { int n = 100; int m = 99; auto start = high_resolution_clock::now(); // ایجاد شیء از کلاس Prim و اجرای الگوریتم Prim g1(n); g1.primMST(); auto end = high_resolution_clock::now(); auto execution_time = duration_cast<nanoseconds>(end - start).count(); ofstream outputFile; outputFile.open("output.txt", ios_base::app); outputFile << "Prim Execution Time: " << execution_time << " nanoseconds" << endl; outputFile.close(); start = high_resolution_clock::now(); // ایجاد شیء از کلاس Kruskal و اجرای الگوریتم Kruskal g2(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g2.addEdge(u, v, w); } g2.kruskalMST(); end = high_resolution_clock::now(); execution_time = duration_cast<nanoseconds>(end - start).count(); outputFile.open("output.txt", ios_base::app); outputFile << "Kruskal Execution Time: " << execution_time << " nanoseconds" << endl; outputFile.close(); return 0; }در نهایت، زمان اجرای الگوریتمها در فایل output.txt ذخیره میشود و می توان آن را بررسی کرد. لطفاً توجه داشته باشید که در الگوریتم پریم، باید یک فایل خروجی با نام "output.txt" ایجاد و در هر اجرای برنامه، از ابتدا به انتها باز شود.