FilesExpand file tree

 master

/

prim_algorithm.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (32 loc) · 1.14 KB

 master

/

prim_algorithm.py

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (32 loc) · 1.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

#! /usr/bin/env python

#coding:utf-8

from collections import defaultdict

from heapq import *

def prim( vertexs, edges ):

adjacent_vertex = defaultdict(list)

for v1,v2,length in edges:

adjacent_vertex[v1].append((length, v1, v2))

adjacent_vertex[v2].append((length, v2, v1))

mst = []

chosed = set(vertexs[0])

adjacent_vertexs_edges = adjacent_vertex[vertexs[0]]

heapify(adjacent_vertexs_edges)

while adjacent_vertexs_edges:

w, v1, v2 = heappop(adjacent_vertexs_edges)

if v2 not in chosed:

chosed.add(v2)

mst.append((v1,v2,w))

for next_vertex in adjacent_vertex[v2]:

if next_vertex[2] not in chosed:

heappush( adjacent_vertexs_edges,next_vertex)

return mst

#test

vertexs = list("ABCDEFG")

edges = [ ("A", "B", 7), ("A", "D", 5),

("B", "C", 8), ("B", "D", 9),

("B", "E", 7), ("C", "E", 5),

("D", "E", 15), ("D", "F", 6),

("E", "F", 8), ("E", "G", 9),

("F", "G", 11)]

print "edges:",edges

print "prim:", prim( vertexs, edges )