درخت پوشای کمینه: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز بحث:درخت پوشای بهینه به درخت پوشای بهینه منتقل شد |
بدون خلاصۀ ویرایش |
||
خط ۷:
در الگوریتم کراسکال , یالهای گراف را به ترتیب صعودی مرتب می کنیم . از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد . این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.
{{چپ چین}}
<source lang=cpp>
1 function Kruskal(G)
2 for each vertex v in G do
3 Define an elementary cluster C(v) ← {v}.
4 Initialize a priority queue Q to contain all edges in G, using the weights as keys.
5 Define a tree T ← Ø //T will ultimately contain the edges of the MST
6 // n is total number of vertices
7 while T has fewer than n-1 edges do
8 // edge u,v is the minimum weighted route from/to v
9 (u,v) ← Q.removeMin()
10 // prevent cycles in T. add u,v only if T does not already contain a path between u and v.
11 // Note that the cluster contains more than one vertex only if an edge containing a pair of
12 // the vertices has been added to the tree.
13 Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
14 if C(v) ≠ C(u) then
15 Add edge (v,u) to T.
16 Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
17 return tree T
</source>
{{پایان چپ چین}}
نحوه ی کار الگوریتم Kruskal به این صورت است که یک جنگل از درخت هارا به ترتیب با هم ادغام می کند تا به یک درخت واحد برسد.
سطر ۱۲ ⟵ ۳۳:
== الگوریتم prim ==
در این روش از یک رأس شروع می کنیم و کمترین یال(یال با کمترین وز ن ) که از آن می گذرد را انتخاب می کنیم . در مرحله بعد یالی انتخاب می شود که کمترین وزن را در بین یالهایی که از دو گره موجود می گذرد داشته باشیم . به همین ترتیب در م رحله بعد یالی انتخاب می گردد که کمترین وزن را در بین یالهایی که از سه گره موجود می گذرد داشته باشد . این روال را آنقدر تکرار می کنیم تا درخت پوشای بهینه حاصل شود . باید توجه کرد که یال انتخابی در هر مرحله در صورتی انتخاب می شود که در گراف دور ایجاد نکند . تفاوت روش پریم با روش کراسکال در این است که گراف حاصل در مراحل میانی تشکیل درخت پوشای بهینه در روش پریم همیشه متصل است ولی در الگوریتم کراسکال در آخرین مرحله قطعاً متصل است.
{{چپ چین}}
<source lang=cpp>
while latest_addition = remove minimum in Q
set is_in_Q of latest_addition to false
add latest_addition to (minimum_adjacency_list of (parent of latest_addition))
add (parent of latest_addition) to (minimum_adjacency_list of latest_addition)
for each adjacent of latest_addition
if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent) < min_distance of adjacent)
set parent of adjacent to latest_addition
set min_distance of adjacent to weight-function(latest_addition, adjacent)
update adjacent in Q, order by min_distance
</source>
{{پایان چپ چین}}
* ممکن است درختهایی که الگوریتم مذکور تولید می کنند، از لحاظ شکل ظاهری متفاوت باشند، ولی وزن همه ی درخت ها یکسان است.
سطر ۲۳ ⟵ ۵۷:
== الگوریتم دایکسترا (Dijkstra) ==
این الگوریتم بصورت حریصانه عمل نموده و بدنبال یافتن کوتاه ترین مسیر ممکن بین یک نود و هر نود دلخواه دیگر، در یک گراف وزن دار و جهت دار می باشد. ورودی این الگوریتم همیشه یک ماتریس دو بعدی است که همان ماتریس وزن گراف است.
{{چپ چین}}
<source lang=cpp>
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity // Unknown distance function from source to v
4 previous[v] := undefined // Previous node in optimal path from source
5 dist[source] := 0 // Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
7 while Q is not empty: // The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break // all remaining vertices are inaccessible
11 remove u from Q
12 for each neighbor v of u: // where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u, v)
14 if alt < dist[v]: // Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return previous[]
1 S := empty sequence
2 u := target
3 while previous[u] is defined:
4 insert u at the beginning of S
5 u := previous[u]
</source>
{{پایان چپ چین}}
== الگوریتم سولین ==
در الگوریتم سولین برای هر گره یال با کمترین هزینه که از آن ع بور می کند را رسم می کنیم . در مرحله بعد ، گراف به مؤلفه هایی تقسیم می شود و یالی انتخاب می گردد که با کمترین هزینه دو مؤلفه گراف را به همدیگر متصل نماید با شرط عدم وجود دور در گراف. آنقدر این مراحل را ادامه می دهیم تا درخت پوشای بهینه حاصل شود.
==منابع==
{{چپ‌چین}}
http://en.wikipedia.org/wiki/Kruskal_algorithm
http://en.wikipedia.org/wiki/Prim_algorithm
http://www.jozve-computer.blogfa.com
{{پایان چپ‌چین}}
| |||