advertise laitec sharif univercity استخراج بیت کوین با کامپیوتر استخراج بیت کوین با کامپیوتر
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

3000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

4800 تومان
دانلود پروژه وب سایت هتل با HTML و ASP.NET

دانلود پروژه وب سایت هتل با HTML و ASP.NET

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

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

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

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

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

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

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

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