دانلود سورس الگوریتم پریم در سی پلاس پلاس
در این قسمت تیم کدگیت فایل دانلود سورس الگوریتم پریم در سی پلاس پلاس را آماده کرده است. برای اجرای پروژه، کافیست فایل دانلود شده را به پروژه خود اضافه و آن را اجرا کنید. پیشنهاد میشود قبل از دانلود، آموزشهای ابتدایی سی پلاس پلاس را بخوانید.
الگوریتم پریم
الگوریتم پریم، الگوریتمی در نظریه گرافها است که زیردرخت پوشای کمینه را برای یک گراف همبند وزن دار پیدا میکند یعنی زیرمجموعهای از یالها را در آن گراف مییابد که درختی را تشکیل میدهند که همه رئوس را شامل میشود در حالیکه مجموع وزن همه آن یالها کمینه شدهاست. این الگوریتم در سال ۱۹۳۰ توسط ریاضیدانی به نام جارنیک داده شد وسپس در سال ۱۹۵۷ پریم، دانشمند علوم کامپیوتر آن را مستقل از جارنیک کشف کرد و در سال ۱۹۵۹ دایکسترا دوباره به آن دست یافت. ازاین رو این الگوریتم گاهی با نام الگوریتم DJP نیز شناخته میشود که برگرفته از اسامی دایکسترا، جارنیک و پریم است.
یک نمونه خروجی برنامه به صورت زیر میباشد:
Edge Weight
0 – 1 2
1 – 2 3
0 – 3 6
1 – 4 5
قسمتی از کد برنامه به صورت زیر میباشد:
// Function to construct and print MST for a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V]) {
int parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
bool mstSet[V]; // To represent set of vertices not yet included in MST
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
// Always include first 1st vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum key vertex from the set of vertices
// not yet included in MST
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of the adjacent vertices of
// the picked vertex. Consider only those vertices which are not yet
// included in MST
for (int v = 0; v < V; v++)
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// print the constructed MST
printMST(parent, V, graph);
گراف ورودی برنامه در شکل زیر نمایش داده شده است
دانلود
زبان برنامهنویسی: سی پلاس پلاس
نوع فایل: Rar
حجم فایل: 2 کیلوبایت
Download “دانلود سورس کد الگوریتم پریم در سی پلاس پلاس”
Prime-Algorithm-Code-Cpp-www.CodeGate.ir_.rar – 302 بار دانلود شده است – 1,47 کیلوبایت پسورد: www.codegate.ir