درخواست کد پرایم و کراسکال

[hmn]

دوستان کسی الگوریتم پرایم و کراسکال رو به زبان سی داره؟

 

[bloody]

اگوریتم پریم در هر زمان یک یال از درخت پوشای حداقل هزینه رو میسازه.در تمام مراحل اجرای الگوریتم مجموعه یال های انتخاب شده یک درخت رو تشکیل میدن.این الگوریتم با یک درخت مانند t که تنها شامل یک راس هست کار خودشو شروع میکنه این راس میتونه یکی از راس های گراف اصلی باشه.بعدش یه یال با کمترین هزینه رو به t اضافه میکنه و این کار رو تا زمانی که T شامل n-1 یال باشه ادامه میده.
برای پیاده سازی این الگوریتم فرض میکنیم هر راس v که در TV قرار نداشته دارای یک راس مجاور مانند near(v) بوده وcost(v,w)=بینهایت هست.

//assume that G has at least one vertex.

TV={0};//start with 0 and no edges.
for (T=o;T contain fewer than n-1 edges;add(u,v) to T){
let (u,V) be a least-cost edge such that U anaclitic to TV and v not anaclitic to TV;
if(there is no such edge)break;
add v to TV;
}
if (T contains fewer than n-1 edges) cout<<"no spanning tree"<<endl;

 

[bloody]

الگوریتم کراسکال البته به c نیست

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 an edge consisting of u and v. 
         // Note that the cluster contains more than one vertex only if an edge containing a pair of
         // the vertices has been added to the tree.
 12      Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
13      if C(v) ≠ C(u) then
14        Add edge (v,u) to T.
15        Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
16    return tree T

 

[hmn]

ممنون ولی کاملشو برای پروژه میخوام. اگه کسی داره ممنون میشم

 

[P.I.T.A]

الگوریتم کراسکال :

void kruskal()
 {
  int i, m, V, E;
  struct edge
    { char v1, v2; int w; };
  struct edge e[maxE];
  PQ pq(maxE); EQ eq(maxE);
  cin >> V >> E;
  for (i = 1; i <= E; i++)
      cin >> e[i].v1 >> e[i].v2 >> e[i].w;
  for (i = 1; i <= E; i++)
      pq.insert(i, e[i].w);
  for (i = 0; i < V-1; )
    {
      if (pq.empty()) break; else m = pq.remove(); 
      if (eq.find(index(e[m].v1),index(e[m].v2),1))
        { cout << e[m].v1 << e[m].v2 << ' '; i++; };
    }
 }

صفحه اصلی

 

[P.I.T.A]

Minimum Cost Spanning Tree Problem

ALGO-11

A C++ Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST).
ALGO-12

A C++ Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics.
ALGO-13

A C++ Program to implement the Prim's Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics and with Mouse support.
ALGO-14

A C++ Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST).
ALGO-15

A C++ Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics.
ALGO-16

A C++ Program to implement the Kurskal's Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics with Mouse Support.


http://www.wol.net.pk/mtshome/cppAlgorithms.html​