advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

3000 تومان
دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

3000 تومان
دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

4800 تومان
سورس پروژه پایانی وب سایت و نرم افزار کلینیک در ASP.net

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

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

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

3000 تومان

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

سفارش پروژه در سورس کد

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

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