图算法

最小生成树 using kruskal

我只用 kruskal 实现，因为 prim 我懒得写，应该没人拿我怎么样吧

graph = UnDirectedGraph(Char)
for ch in 'A':'F'
  insertVertex!(graph, ch)
end

insertEdge!(graph, 'A', 'B', 6)
insertEdge!(graph, 'A', 'D', 5)
insertEdge!(graph, 'A', 'C', 1)
insertEdge!(graph, 'B', 'C', 5)
insertEdge!(graph, 'D', 'C', 5)
insertEdge!(graph, 'B', 'E', 3)
insertEdge!(graph, 'C', 'E', 6)
insertEdge!(graph, 'C', 'F', 4)
insertEdge!(graph, 'D', 'F', 2)
insertEdge!(graph, 'E', 'F', 6)

mst = kruskalmst(graph)
println(mst)

A----|C 1 |  
B----|E 3 | C 5 |  
C----|A 1 | F 4 | B 5 |  
D----|F 2 |  
E----|B 3 |  
F----|D 2 | C 4 |

旅行商算法

@testset "test tsp" begin
  vertices = [
    TSPVertex(0, 2, 1),
    TSPVertex(0, 5, 2),
    TSPVertex(0, 1, 3),
    TSPVertex(0, 4, 3),
    TSPVertex(0, 6, 3),
    TSPVertex(0, 2, 4),
    TSPVertex(0, 5, 5),
  ]

  list = List(TSPVertex{Int})
  for vertex in vertices
    push!(list, vertex)
  end

  tour = tsp(list, vertices[1])
  for vertex in tour
    println(vertex.x, "\t", vertex.y)
  end
end

其中

mutable struct TSPVertex{T}
  data::T
  x::Number
  y::Number
  color::Color
end

TSPVertex(data::T, x::Number, y::Number) where T = TSPVertex{T}(data, x, y, White)