Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_spanning.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 1k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_spanning.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _spanning.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. /*******************************************************************************
  15. *                                                                              *
  16. *  SPANNING_TREE  (spanning tree)                                              *
  17. *                                                                              *
  18. *******************************************************************************/
  21. #include <LEDA/graph_alg.h>
  22. #include <LEDA/node_partition.h>
  25. list<edge> SPANNING_TREE(const graph& G)
  26. { node v,w;
  27.   edge e;
  28.   list<edge> EL;
  29.   node_partition P(G);
  31.   forall_edges(e,G)
  32.      { v = source(e);
  33.        w = target(e);
  34.        if (! P.same_block(v,w))
  35.         { EL.append(e);
  36.           P.union_blocks(v,w);
  37.          }
  38.       }
  40.   return EL;
  41. }