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

تخفیف برای خرید این پروژه: زیر دکمه خرید، در پایین همین صفحه

پیاده سازی

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

رشته :

کامپیوتر

نوع فایل:

,

توضیحات:


توضیحات :

پیاده سازی الگوریتم جستجوی اول عمق 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

== تصویری از محیط  فایل اجرایی این
DFS

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

#<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);
}

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


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

 

تخفیف بسیار ویژه ۳۰ درصدی : دوست عزیز سعی ما این بوده که پروژه ها را با کمترین قیمت ممکن (مقایسه کنید با قیمت سایر سایتها) در اختیار شما قرار دهیم اما اگر دوستی هست که واقعا این مبلغ نیز برایش مقدور نیست می توانید عنوان تحقیق یا پروژه مورد نظر، کلمه Takhfif و آدرس ایمیل خود را به شماره پشتیبانی سایت  ۰۹۳۹۲۷۶۱۶۳۰  پیامک کنید تا لینک تخفیف سریعا برای شما ارسال گردد .

خرید انواع تحقیق و پروژه های شما بصورت توافقی : ۰۹۳۹۲۷۶۱۶۳۰

Related posts

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Translate »