Prim完成，未上传造价计算代码。附简易拓扑图，征队友。
import math
import turtle
import numpy as np
class Node:
x = y = 0
demand = 0
name = ''
father = None
next = None
e_length = 0
out_degree = 0
is_switch = False
state = True # True for work well
def __init__(self, x, y, name):
self.x = x
self.y = y
self.name = name
class Graph:
arc_node = list()
class Link:
head = None
tail = None
data = 1e05
next = None
def __init__(self, head=None, tail=None, data=1E05, nex=None):
self.head = head
self.tail = tail
self.data = data
self.next = nex
def copy1(self):
return Link(self.head, self.tail, self.data, None)
def distance(node1: Node, node2: Node): # calculate the distance of two nodes
return math.sqrt((node1.x - node2.x) ** 2 + (node1.y - node2.y) ** 2)
def draw(graph):
turtle.penup()
turtle.screensize(200, 200)
for node in graph:
turtle.goto(node.x / 4, node.y / 4)
turtle.pendown()
turtle.dot(10)
turtle.penup()
def draw_graph(T):
T1 = set()
turtle.penup()
turtle.screensize(2000, 2000)
for node in T:
node_p = node
turtle.goto(node_p.x, node_p.y)
turtle.pendown()
while node_p:
turtle.goto(node_p.x, node_p.y)
turtle.dot(40, "red")
if node_p in T1:
break
else:
T1.add(node_p)
node_p = node_p.father
turtle.penup()
turtle.done()
def creat_link(graph):
head = Link()
p = Link()
tail = p
for m in range(len(graph)):
for n in range(m + 1, len(graph)):
temp = Link(graph[m], graph[n], distance(graph[m], graph[n]), p)
p = temp
return p
def sort(head: Link):
start = Link()
p = start
p.data = 1.11
p2 = head
while p2:
p3 = head
temp = Link()
while p3:
if temp.data > p3.data > p.data:
temp = p3
p3 = p3.next
p.next = copy1(temp)
p = p.next
p2 = p2.next
return start
'''
def sort(head: Link):
p = last = head
while p:
p2 = last2 = head
while p2 != p:
if p2.data > p.data:
last.next = p.next
last2.next = p
p.next = p2
p = last.next
break
last2 = p2
p2 = p2.next
if p2 == p:
last = p
p = p.next
print(p.data)
print(p2.data)
print()
return head
'''
'''
def prim(graph, e_head: Link, num_v):
p = e_head.next
set1 = {p.head, p.tail}
turtle.screensize(2000, 2500)
turtle.penup()
turtle.goto(p.head.x, p.head.y)
turtle.pendown()
turtle.dot(40, "red")
turtle.goto(p.tail.x, p.tail.y)
turtle.dot(40, "red")
while len(set1) != num_v:
while p:
if p.tail in set1 and p.head not in set1
or p.tail not in set1 and p.head in set1:
head = p.head if p.head in set1 else p.tail # judge which is head node
tail = p.tail if head == p.head else p.head
head.next = tail
turtle.penup()
turtle.goto(head.x, head.y)
turtle.pendown()
turtle.goto(tail.x, tail.y)
turtle.dot(40, "red")
set1.add(tail)
p = e_head.next
break
p = p.next
#turtle.done()
'''
def prim(graph, e_head: Link, num_v):
p = e_head.next
set1 = {p.head, p.tail}
while len(set1) != num_v:
while p:
if p.tail in set1 and p.head not in set1
or p.tail not in set1 and p.head in set1:
head = p.head if p.head in set1 else p.tail # judge which is head node
tail = p.tail if head == p.head else p.head
tail.father = head
set1.add(tail)
p = e_head.next
break
p = p.next
def creat_T(graph):
T = set()
T1 = set()
for node in graph:
father = node.father
while father:
father = father.father
if father not in T1:
T1.add(father)
for node in graph:
if node not in T1 :
T.add(node)
return T
if __name__ == '__main__':
size = 48
X = np.zeros((size, 4))
t = range(len(X))
X[:, 0] = t
X[:, 1:] = np.random.rand(size, 3) * 1000
graph1 = list()
for k in range(len(X)):
graph1.append(Node(X[k, 1], X[k, 2], X[k, 0]))
l_head = creat_link(graph1)
l_head = sort(l_head)
prim(graph1, l_head, size)
T0 = creat_T(graph1)
draw_graph(T0)
