الگوریتم های پیمایش گراف 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)
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) میشود.
