advertise laitec sharif univercity
دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

10000 تومان
دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

28000 تومان
دانلود سورس اپلیکیشن اندروید پیانو سنتی

دانلود سورس اپلیکیشن اندروید پیانو سنتی

14000 تومان
پروژه کامل مدیریت شرکت نرم افزاری با سی شارپ و SQL

پروژه کامل مدیریت شرکت نرم افزاری با سی شارپ و SQL

38000 تومان
دانلود سورس اپلیکیشن اندروید کتاب گرامر انگلیسی

دانلود سورس اپلیکیشن اندروید کتاب گرامر انگلیسی

10000 تومان

الگوریتم های پیمایش گراف Graph

گراف (G = (V, E را میتوان با لیست ها یا با ماتریس مجاورتی نمایش داد. در اینجا چند الگوریتم پیمایش گرافها را معرفی خواهیم کرد: BFS، DFS، KRUSKAL و PRIM.
الگوریتم های پیمایش گراف Graph

الگوریتم های پیمایش گراف Graph

گراف G = (V, E) چه جهتدار (digraph) و چه غیرجهتدار را میتوان با لیست های مجاورتی (Adjacency Lists) یا با ماتریس مجاورتی (Adjacency matrix) نمایش داد.

اگر فرض کنیم تعداد رئوس |V| = n و تعداد یالها |E| = e باشد، حافظه مصرفی لیست مجاورتی  θ(n + e) است و الگوریتم چاپ همه رئوس مجاور راس u از مرتبه θ(degree(u)) و تشخیص اینکه (u, v) ϵ E از مرتبه O(degree(u)) است. حافظه مصرفی ماتریس مجاورتی θ(n2) ، چاپ رئوس مجاور u از مرتبه θ(n) و تشخیص اینکه (u, v) ϵ E از مرتبه θ(1) است.

 

پیمایش سطحی گراف Breadth-first search

در این پیمایش گراف از راس گفته شده شروع میکنیم و همه رئوس مجاور آنرا ملاقات میکنیم. سپس این عمل را با راس ملاقات شده بعدی انجام می دهیم. BFS از یک صف استفاده میکند، ابتدا راس شروع (s) را در صف Q قرار میدهد و سپس در یک حلقه while عنصر سر صف را بر میدارد، ملاقات میکند و همه رئوس مجاور آن را به صف اضافه میکند، تا زمانیکه صف خالی شود:

الگوریتم پیمایش BFS بصورت زیر میباشد:

BFS(s)

for  each  u ϵ V – {s}

            do  d[u] <-- ∞   

d[s] <-- o , Q <-- ф

addq(Q , s)

while  Q ≠ ф

              do  { u <-- delq(Q)

                         for  each  v ϵ Adj[u]

                                     do if  d[v] = ∞

                                                then  d[v] <-- d[u] + 1 , addq(Q , v)    }

 

الگوریتم BFS طول کوتاهترین مسیر از نظر تعداد یال از راس شروع S به همه رئوس را مشخص میکند که با D نشان داده شده است.

اگر گراف با لیست مجاورتی نمایش داده شود، مرتبه بی اف اس، O(n + e) است چون هر راس یک بار به صف اضافه میشود. (O(n)) و هر راس مثلا u یکبار از صف خارج میشود که آنگاه یال (u , v) بررسی میشود، بنابراین هر یال در گراف جهتدار حداکثر یک بار و در غیر جهتدار حداکثر دوبار بررسی میشود (O(e)) .

 

پیمایش عمقی گراف Depth-first search

در این روش پیمایش گراف، از یک راس شروع میکنیم  و یکی از رئوس مجاورش را ملاقات میکنیم، حال این عمل را با راس جدید انجام میدهیم. واضح است که نتیجه DFS نیز منحصر به فرد نیست.

ممکن است با شروع از یک راس همه رئوس ملاقات نشوند. بنابراین الگوریتم DFS را به ازای هر راسی که هنوز ملاقات نشده فراخوانی میکنیم یعنی نتیجه کل پیمایش یک جنگل پوشاست و نه لزوما یک درخت پوشا. برای پیاده سازی DFS به هر راس یک رنگ نسبت میدهید: سفید (white) یعنی راسی که هنوز بررسی نشده، خاکستری (gray) یعنی راسی که دیده شده ولی هنوز تمام نشده، سیاه (black) یعنی تمام شده، یعنی هر راسی که از آن قابل دسترسی بوده، پیدا شده است.

الگوریتم پیمایش DFS بصورت زیر میباشد:

DFS(G)

for  each  u ϵ V  do  color[u] <-- WHITE

time <-- 0

for  each  u ϵ V  do  if  color[u] = WHITE  then  DFS-VISIT(u)

DFS-VISIT(u)

color[u] <-- GRAY , time <-- time+1 , d[u] <-- time

for  each  v ϵ Adj[u]  do  color[v] = WHITE  then  DFS-VISIT(v)

color[u] <-- BLACK , time <-- time+1 , f[u] <-- time

 

 

time یک متغیر global است. برای هر متغیر مثل u، d[u] زمانی را نشان میدهد که u برای اولین بار کشف شده است (discovery time) و خاکستری است. f[u]  (finishing time) زمانی را ثبت میکند که بررسی لیست u تمام شده و u سیاه است.

اگر گراف با لیست مجاورتی پیاده شود، مرتبه دی اف اس، O(n + e) است.

 

الگوریتم کراسکال kruskal

الگوریتم کراسکال، یک الگوریتم حریصانه پیمایش گراف است که در آن یالها به ترتیب صعودی وزنشان مرتب میشوند سپس به ترتیب، یالها بررسی میشوند و اگر سیکل تشکیل نشود (اگر یال safe باشد)، انتخاب میشود در غیر اینصورت آن یال صرفنظر (reject) میشود.

الگوریتم کراسکال را میتوان بصورت زیر نوشت:

KRUSKAL (G , W)

A <-- ф

for  each  vertex  v ϵ V

             do  MAKE-SET(v)      //   هر عضو یک مجموعه مجزاست.

Sort   E  into  nondecreasing  order  by  weight  w

for  each  (u,v) ϵ E  taken  from  the  sorted  list

               do  if  FIND-SET(u) ≠ FIND-SET(v)

                                then  A <-- A U { (u ,v) } , UNION(u , v)

return  A

 

 

در این الگوریتم FIND-SET(u) مجموعه ای که u عضو آن است را برمیگرداند.

مرتبه کراسکال O(e.Lge) است (بخاطر مرتب سازی یال ها) و چون e < n2 ، مرتیه کراسکال را میتوان O(e.Lgn) نوشت. البته اگر یالها از قبل مرتب باشند مرتبه کراسکال O(eα(n)) میباشد. α(n) یک عدد با رشد بسیار ناچیز است.

 

الگوریتم پریم Prim

این الگوریتم گراف نیز حریصانه است. روش آن بدین صورت ایت که از راس گفته شده شروع میکنیم، راسی را ملاقات میکنیم که با راس شروع مجاور است و وزن یالشمینیمم است. در مرحله بعدی راسی را ملاقات میکنیم که با حداقل یکی از رئوس ملاقات شده مجاور است و وزن یالش مینیمم است، به همین ترتیب در هر مرحله یک راس ملاقات نشده را ملاقات میکنیم.

شبه کد الگوریتم پریم بصورت زیر است:

PRIM(G,w,r)

 for  each  u ϵ V

           do  key[u] <-- ∞ , π[u] <-- NIL     //                          

key[r] <-- 0 , Q <-- V

while  Q ≠ ф

           do  u <-- EXTRACT-MIN(Q)

                      for   each  v ϵ Adj[u]

                                do  if  v ϵ Q  and  w(u ,v) < key[v]

                                               then     π[v] <-- u , key[v] <-- w(u ,v)

 

 

در این الگوریتم Q یک صف اولویت است که ابتدا همه رئوس در آن قرار میگیرند. کلید هر راس در این صف به جز کلید r ابتدا برابر ∞ میشود و کلید r برابر صفر میشود. در حلقه while ابتدا تابع  EXTRACT-MIN ، راس r را از صف برداشته و به u منتقل میکند و سپس کلید همه رئوسی که با u مجاور هستند را برابر وزن یالشان به u قرار میدهد و پدرشان را در u قرار میدهد  (π[v] یعنی پدر راس v که اگر u ملاقات شده باشد و u با v مجاور باشد، پدر راس v راس u است.)

به همین ترتیب  در حلقه while هر بار راسی از صف انتخاب میشود که کلیدش (وزن یالش) مینیمم باشد و با یکی از رئوس قبلا اتخاب شده مجاور باشد.

مرتبه پریم بستگی به پیاده سازی صف اولویت دارد. اگر صف اولویت را با binary minHeap پیاده سازی کنیم، مرتبه پریم O(n Lgn + e Lgn) = O(e Lgn) است که از نظر مجانبی با کراسکال یکسان است. اگر از هیپ فیبوناچی برای پیاده سازی صف اولویت استفاده شود، مرتبه پریم O(e + n Lgn) میشود.

 

                                                  



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
آموزش bfsمرتبه اجرایی الگوریتم های پیمایش گرافیپیمایش گراف چگونه است؟آشنایی با انواع الگوریتم های گرافالگوریتم پیمایش BFSالگوریتم Kruskal در پیمایش گرافروشهای پیمایش Graph کدامند؟شبه کد الگوریتم Primروش Breadth-first searchالگوریتم Depth-first searchآشنایی با الگوریتم کراسکالآموزش الگوریتم های پیمایش Graphمعرفی الگوریتم پریمالگوریتم پیمایش سطحی گرافچگونگی الگوریتم پیمایش DFSپیمایش عمقی گراف چیست؟معرفی الگوریتم های پیمایش گرافهاآشنایی با DFS لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php