daily pastebin goal
74%
SHARE
TWEET

Untitled

a guest May 16th, 2018 112 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package prima
  2.  
  3. import "AaDSLab3/graph"
  4.  
  5. type Edge struct {
  6.     weight int
  7.     to int
  8. }
  9.  
  10. func (e *Edge)GetWeight() int{
  11.     return e.weight
  12. }
  13. func (e *Edge)GetTo() int{
  14.     return e.to
  15. }
  16.  
  17. func PrimaAlg(graph *graph.Graph) int{
  18.     w := graph.GetMatrix()
  19.     n := graph.GetVertexesCount()
  20.     cost:=0
  21.     const INF int = int(^(uint(0))>>1)
  22.     dist := make([]Edge, n)
  23.     used := make([]bool, n)
  24.     for i:=0; i<n; i++{
  25.         dist[i].weight = INF
  26.         used[i] = false
  27.     }
  28.     dist[0] = Edge{
  29.         weight:0,
  30.         to: 0,
  31.     }
  32.     for i:=0; i<n; i++{
  33.         minDist := INF
  34.         u := 0
  35.         changed:=false
  36.         for j:=0; j<n; j++{
  37.             if !used[j] && dist[j].weight < minDist{
  38.                 minDist = dist[j].weight
  39.                 u = j
  40.                 changed=true
  41.             }
  42.         }
  43.         if changed {
  44.             cost += minDist
  45.             used[u] = true
  46.             for v := 0; v < n; v++ {
  47.                 if w[u][v] < dist[v].weight && w[u][v] != 0 {
  48.                     dist[v].weight = w[u][v]
  49.                     dist[v].to = u
  50.                 }
  51.             }
  52.         }
  53.     }
  54.     return cost
  55. }
RAW Paste Data
Top