سورس الگوریتم پریم با فایل به زبان C++

چهارشنبه ۲۳ بهمن ۱۳۹۸
بازدید ۱,۷۰۱ نفر
AmRo
(10 امتیاز از 2 رای)
Loading...

تصویر prims-algorithm-in-cpp_8191 سورس الگوریتم پریم با فایل به زبان C++

سورس الگوریتم پریم با فایل به زبان C++

در این بخش سورس الگوریتم پریم با فایل به زبان C++ را برای شما آماده کرده ایم که در محیط نرم افزار Code::Blocks و زبان برنامه نویسی سی پلاس پلاس نوشته شده است. در ادامه می توانید توضیحات، تصاویر و همچنین فیلمی از نحوه اجرا شدن پروژه را مشاهده کنید.

توضیحات پروژه

در این پروژه بعد از اجرا شدن برنامه، اطلاعات از فایلی که در کنار پروژه قرار داده شده است (dist.txt) خوانده شده و سپس یال های درخت پوشای کمینه و مجموع وزن آن ها را به نمایش در می آید.

الگوریتم پریم (Prim) یک الگوریتم در نظریه گراف ها است که به منظور پیدا کردن زیر درخت پوشای کمینه برای یک گراف همبند وزن دار استفاده می شود. به عبارت دیگر زیر مجموعه از یال ها را در آن گراف پیدا می کند که درختی تشکیل می دهند که همه رئوس را شامل می شود در حالی که وزن همه آن یال ها کمینه شده است.

الگوریتم پریم را به این صورت می توان بیان کرد: ابتدا گره ای به دلخواه انتخاب شود و سپس از بین یال های متصل به آن یالی با کمترین وزن انتخاب می شود به گونه ای که حلقه ایجاد نشود. در هر مرحله یالی انتخاب می شود که باید یکی از دو سرآن جزو مسیر جواب بوده و وزن حداقل داشته باشد. پس درالگوریتم پریم دو محدودیت در هر مرحله داریم یکی آن که جنگل ایجاد نشود و دوم آنکه حلقه پدید نیاید.

قسمت های از سورس کد

#include <iostream>
#include <cstdio>
#include <conio.h>
using namespace std;
int n;
int weight[100][100];
char inTree[100]={0};
int d[100];
int whoTo[100];
int main() {
    cout << "This program read data from <dist.txt>...nn";
    cout << "The result of PRIM algorithm is:nn";
    FILE *f = fopen("dist.txt", "r");
	int total,treeSize;
	fscanf(f, "%d", &n);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			fscanf(f, "%d", &weight[i][j]);
	fclose(f);
	/* Initialise d with infinity */
	for (int i = 0; i < n; ++i)
		d[i] = 100000;
	/* Add the first node to the tree */
	cout << "Adding node " << 0 + 'A' << endl;
	inTree[0] = 1;
	updateDistances(0);
	total = 0;
	for (treeSize = 1; treeSize < n; ++treeSize) {
		/* Find the node with the smallest distance to the tree */
		int min = -1;
		for (int i = 0; i < n; ++i)
      	if (!inTree[i])
         	if ((min == -1) || (d[min] > d[i]))
					min = i;
		/* And add it */
		cout << "Adding edge " << whoTo[min] + 'A' << " - " << min + 'A' << endl;
		inTree[min] = 1;
		total += d[min];
		updateDistances(min);
	}
	cout << "nTotal distance: " << total << endl;
   getch();
	return 0;
}