LayZee
15/05/2008, 23:43
C++ da Baruvka'nın algoritmasını kodlamam gerekiyor, ama temel olarak ben algoritmayı tam olarak anlayamadım. Zaten bu konuda Türkçe olarak pek kaynak bulamadım. Bu algoritma sadece anladığım kısmıyla "minimum spanning tree" yi bulmaya yarıyor. Elimdeki algoritma İngilizce, ama yine de paylaşacağım.
Pseudocode of Boruvka’s Algorithm:
Ø Begin with a connected graph G containing edges of distinct
weight, and an empty set of edges T
Ø While the vertices of G connected by T are disjoint
§ Begin with an empty set of edges E
§ For each component
· Begins with an empty set of edges S
· For each vertex in the component
o Add the edge of minimum weight from the vertex in
the component to another vertex in a disjoint component to S
· Add the minimum weight edge in S to E
§ Add the resulting set of edges E to T.
Ø The resulting set of edges T is the minimum spanning
tree of G.
Algorithm of Boruvka:
1. Algorithm BoruvkaMST(G)
2. T ← V // the vertices of graph G
3. while T has fewer than n-1 edges do
4. for each connected component C in T do
5. let edge e be the minimum weight edge from C
to another component in T
6. if e is not already in C then
7. add edge e to T
8. return T
Biraz açıklayabilir ve yardımcı olabilir misiniz ?
Teşekkürler.
Pseudocode of Boruvka’s Algorithm:
Ø Begin with a connected graph G containing edges of distinct
weight, and an empty set of edges T
Ø While the vertices of G connected by T are disjoint
§ Begin with an empty set of edges E
§ For each component
· Begins with an empty set of edges S
· For each vertex in the component
o Add the edge of minimum weight from the vertex in
the component to another vertex in a disjoint component to S
· Add the minimum weight edge in S to E
§ Add the resulting set of edges E to T.
Ø The resulting set of edges T is the minimum spanning
tree of G.
Algorithm of Boruvka:
1. Algorithm BoruvkaMST(G)
2. T ← V // the vertices of graph G
3. while T has fewer than n-1 edges do
4. for each connected component C in T do
5. let edge e be the minimum weight edge from C
to another component in T
6. if e is not already in C then
7. add edge e to T
8. return T
Biraz açıklayabilir ve yardımcı olabilir misiniz ?
Teşekkürler.