advertise laitec sharif univercity استخراج بیت کوین با کامپیوتر استخراج بیت کوین با کامپیوتر
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

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

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

4800 تومان
دانلود مجموعه 100 سورس ساده و ابتدایی با سی پلاس پلاس

دانلود مجموعه 100 سورس ساده و ابتدایی با سی پلاس پلاس

5000 تومان
دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

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

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

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

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