پیاده سازی الگوریتم DFS با سی پلاس و سورس کامل برنامه

نویسنده : نیکوسرشت جمعه , ۲۹ فروردین , ۱۳۹۳ پروژه های سی پلاس پلاس c++ بدون نظر

قیمت : ۵۲۰۰ تومان ( پنج هزار و دویست تومان)

رشته :	کامپیوتر
نوع فایل:	CPP , EXE
توضیحات:	–

توضیحات :

پیاده سازی الگوریتم جستجوی اول عمق DFS با سی پلاس

در نظریه‌ٔگراف، جستجوی عمق اول (به انگلیسی: Depth-first Search، به‌اختصار DFS) یک الگوریتم پیمایشگرافاست که برای پیمایش یا جستجوی یک درخت یا یک گراف به کار می‌رود.

استراتژی جستجوی عمق اول برای پیمایش گراف، همانطور که از نامش پیداست “جستجوی عمیق‌تر در گراف تا زمانی که امکان دارد” است.

پیمایش با انتخاب رأس $r$ به عنوان ریشه آغاز می‌شود. $r$ به عنوان یک رأس دیده شده برچسب می‌خورد. رأس دلخواه $r_1$ از همسایگان $r$ انتخاب شده و الگوریتم به صورت بازگشتی از $r_1$ به عنوان ریشه ادامه می‌یابد.از این پس در هر مرحله وقتی در رأسی مانند $v$ قرار گرفتیم که همهٔ همسایگانش دیده شده‌اند، اجرای الگوریتم را برای آن رأس خاتمه می‌دهیم. حال اگر بعد از اجرای الگوریتم با ریشهٔ $r_1$ همهٔ همسایگان $r$ برچسب خورده باشند، الگوریتم پایان می‌یابد. در غیر این صورت رأس دلخواه $r_2$ از همسایگان $r$ را که هنوز برچسب نخورده انتخاب می‌کنیم و جستجو را به صورت بازگشتی از $r_2$ به عنوان ریشه ادامه می‌دهیم. این روند تامادامیکه همهٔ همسایگان $r$ برچسب نخورده‌اند ادامه می‌یابد.

البته پیمایش گراف برای تأمین هدفی صورت می‌گیرد. بر این اساس برای انعطاف پذیر ساختن الگوریتم در قبال کاربردهای مختلف، دو نوع عملیات preWORK و postWORK را به همراهِ بازدید از هر رأس یا یال انجام می‌دهیم، که preWORK در زمان برچسب خوردنِ رأسِ در حال بازدید، و postWORK بعد از بررسی هر یالِ خروجی از رأسِ در حال بازدید انجام خواهد شد. هر دوی این عملیات وابسته به هدفِ استفاده از الگوریتم، مشخص خواهند شد.

الگوریتم بازگشتی جستجوی اول عمق به صورت زیر است. آرایه یک بعدی Visited تعیین می کند آیا راسی قبلاً ملاقات شده است یا خیر. اگر راس vi ملاقات شود Visited[i] برابر با یک می شود.

پیچیدگی زمانی

مشخص است که الگوریتم، هر یال در گراف بدون جهت رادقیقاً دوبار (یک بار به بهنگام بررسی هر یک از دو انتها) و هر یال در گراف جهت‌دار را دقیقاً یک بار پیمایش می‌کند. همچنین هر رأس قابل دسترسی از ریشه دقیقاً یک بار بازدید خواهد شد. پس با فرض همبند بودن گراف و اینکه preWORK و postWORK در (۱)O انجام شوند، پیچیدگیزمانی جستجوی عمق اول (|O(|V|+|E خواهد بود

پیاده سازی الگوریتم جستجوی اول عمق DFS با سورس کامل برنامه

همراه با فایلهای EXE , CPP

== تصویری از محیط فایل اجرایی این پروژه :

مشاهده بخشهایی از سورس کد این پروژه :

#include<stdio.h>
#include<conio.h>

void initialization(void);
void DFS_VISIT(int u);
void output(void);

int time,visit[50],parent[50],adj[50][50],d[50],f[50],N,E;

main()
{
int i;
clrscr();
initialization();
printf(“DIscovering Sequence:\n”);

for(i=1;i<=N;++i)
{
if(visit[i]==0)
DFS_VISIT(i);
}
output();
}

void initialization(void)
{
int i,S,D,j;
FILE *fp;
fp=fopen(“dfsin.txt”,”r”);
fscanf(fp,”%d %d”,&N,&E);

for(i=1;i<=E;++i)
{
fscanf(fp,”%d %d”,&S,&D);
adj[S][D]=1;
}

for(i=1;i<=N;++i)
{
visit[i]=0;
parent[i]=0;
}
time=0;
}

void DFS_VISIT(int u)
{
int v;
visit[u]=1;
d[u]=++time;
printf(“%d “,u);
for(v=1;v<=N;++v)
{
if(adj[u][v]==1)
{
if(visit[v]==0)
{
parent[v]=u;
DFS_VISIT(v);
}
}
}
f[u]=++time;
}
void output(void)
{
int i;
printf(“\n\nSelected Edges:\n”);
for(i=1;i<=N;++i)
{
if(parent[i]!=0)
printf(“%d -> %d\n”,parent[i],i);
}

دانلود کامل پروژه همراه با فایل سورس کد و فایل اجرایی آن
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه

5200 تومان خريد

پذیرش و انجام سفارشات پروژه های شما
شماره تماس پشتیبانی سایت : ۰۹۳۹۲۷۶۱۶۳۰

توجه مهم :

*دوست عزیز در صورت نداشتن رمز پویا یا قطع بودن درگاه بانکی ، لطفا نام پروژه درخواستی خود را جهت هماهنگی برای دریافت شماره کارت واریزی و دریافت لینک دانلود، به واتساپ پشتیبانی سایت ۰۹۳۹۲۷۶۱۶۳۰ ارسال کنید *(از ساعت ۸ الی ۲۳)

Tags: پروژه های سی پلاس پلاس c++

c++, cp, CPP, exe, include, iostream.h, void main, آموزش ++c, الگوریتم DFS, الگوریتم DFS با سی پلاس و سورس کامل برنامه, برنامه نویسی, به زبان C, پروژه, پروژه #C, پروژه دانشجویی, پروژه رایگان, پروژه سی, پروژه سی پلاس پلاس, پروژه های دانشجویی, پروژه های سی پلاس, پیاده سازی الگوریتم DFS با سی پلاس سورس کامل برنامه, تحت سی, دانلود پروژه های ++C, دانلود رایگان, دانلود رایگان پروژه سی پلاس, دانلود سورس پروژه, دانلود سورس پروژه به زبان سی پلاس پلاس, دانلود سورس سی, دانلود نرم افزار, سورس پروژه, سورس کد های سی, سی, سی پلاس پلاس, کدهای سی پلاس پلاس, گرفتن اطلاعات و ذخيره در سی پلاس