--- In netlogo-users%40yahoogroups.com">netlogo-users
yahoogroups.com, "James
Steiner" <gregortroll...> wrote:
>
> In kruskals algorithm for finding spanning trees of networks,
cycles /
> loops are detected and prevented automatically as the algorithm is
> applied.
>
> Here's the gist of it:
>
> First, assign each vertex a unique "subtree" value. The vertex
itself
> is a good value for this.
>
> ;; assumes vertices-own [ subtree ]
> ask vertices [ set subtree myself ]
>
> Next, mark all the edges as not in the spanning tree
>; ;; assumes edges-own [ in-tree? ]
> ask edges [ set in-tree? false ]
>
> Next, sort the edges by weight, low to high.
> let sorted-edges sort-by [ [ weight ] of ?1 < [ weight ] of ?2
] edges
>
> Next, process the edges, looking at the vertices of the edge.
>
> If the subtree values of the vertices are different, make them the
> same, and make the subtree of all vertices attached to these
vertices
> the same, too. This adds the edge to the spanning tree.
>
> ( If the subtree values of the vertices were the same, then the
edges
> attached to these vertices are already in the same sub-tree, so
adding
> this edge would create a loop, therefore, this edge must not be part
>; of the spanning tree. Skip it. )
>
> foreach sorted-edges
> [ ask ? ;; ? is the edge
>; [ ;; get subtrees of the endpoints
> let subtree-1 [subtree] of end1
>; let subtree-2 [subtree] of end2
>; ;; compare them. are they in different sub-trees?
> if subtree-1 != subtree-2
> [ ;; yes! (no loop is formed)
> set in-tree? true
>; ;; now merge the two subtrees
> ;; i.e. assiging subtree-1 to the subtree variable of all
> vertices in subtree-2.
> ask vertices with [ subtree = subtree-2 ] [ set subtree
subtree-1 ]
> ;; the above line may not the most efficient way to do it,
> but it is the simplest.
> ]
> ]
> ]
>
> At this point, the spanning tree is all edges with in-tree? equal
to TRUE.
>
> let spanning-tree edges with [ in-tree? = true ]
>
> This is a simplified version of the algorithm implemented in the
> Kruskals model on turtleZERO, here:
>
> http://www.turtlezero.com/models/models.php?model=kruskal
>
> I hope this helps!
>
> ~~James
> ______________________
> http://www.turtlezero.com
>
> On 8/2/07, neverlate19 < no_reply%40yahoogroups.com">no_replyyahoogroups.com> wrote:
> >
>; > when i add the edge to the minimum-spanning-tree,how do i
prevent the cycle(because cycle is error minimum-spanning-tree )and
>; > how do i use which method to detect the cycle?
>
Thanks your explaination for the question~!
i hava been solven the problem
This is simple and full-logic solution.
THX
.
