1    # ---------------------------------------------------------------------
2    #
3    # PRIM - algoritmus (mohó algoritmus)
4    #
5    # ---------------------------------------------------------------------
6    
7    graph = {0: [(1, 10), (2, 4), (4, 6), (5, 8)],
8             1: [(0, 10), (2, 5), (4, 6)],
9             2: [(0, 4), (1, 5), (3, 4), (4, 9), (7, 3)],
10            3: [(2, 4), (4, 6), (7, 4)],
11            4: [(0, 6), (1, 6), (2, 9), (3, 6), (5, 12), (6, 1), (7, 13)],
12            5: [(0, 8), (4, 12)],
13            6: [(4, 1), (7, 2)],
14            7: [(2, 3), (3, 4), (4, 13), (6, 2)]}
15   mátrix = []
16   csúcs = set()
17   for i in range(len(graph)):  # len(graph) most 8, mivel 8 bejegyzés van a szótárban
18       csúcs = csúcs | {i}
19       sor = [1000] * len(graph)  # sor feltöltése 8 ezressel
20   
21       for j in range(len(graph[i])):  # A szótár aktuális bejegyzésének feldolgozása
22           (p, e) = graph[i][j]  # A szótár i. bejegyzésének j. eleme egy számpár
23           sor[p] = e  # p a gráf egy pontja, e az él "súlya" - ezért célszerű a pontokat indexesen megadni (0,1,2...stb)
24       mátrix.append(sor)  # mátrix egy sora megvan
25   
26   print('Csúcsmátrix:')
27   for elem in mátrix:
28       print(elem)
29   
30   # halmazok előkészítése
31   V = csúcs
32   print('Csúcsok: ', V)
33   X = {0}  # X a feszítőfa csúcsait tartalmazza majd, kezdésként 0, a kiinduló pont van benne
34   Y = V - X  # Y a maradék pontok halmaza {1,2,3,4,5,6,7}
35   F = set()  # F a feszítőfa éleinek halmaza lesz, számpárok lesznek benne
36   print('KEZDŐÁLLAPOT')
37   print('Feszítőfa csúcsai:', X)
38   print('Feszítőfa éleinek halmaza: ', F)
39   print('"Maradék" csúcsok: ', Y)
40   print('---------------------------------')
41   
42   
43   def mini():
44       # EZ és AZ alkotta él benne van-e már F-ben?
45       def nincsbenne_F_ben(ez, az):
46           return ((ez, az) not in F) and ((az, ez) not in F)
47   
48       m = 1000
49   
50       X_TEMP = list(X)  # átmenetileg listává alakítom az X halmazt, mert halmazban nincs indexelés
51       Y_TEMP = list(Y)  # ugyanez a helyzet az Y halmazzal is
52       for i in X_TEMP:  # minimumkeresés a mátrixban, úgy hogy az egyik pont a feszítőfa csúcsai közül legyen,
53           for j in Y_TEMP:  # a másik pont a maradékból
54               if nincsbenne_F_ben(i, j) and mátrix[i][j] < m:
55                   # kizárjuk a már feldolgozott éleket (nincsbenne_F_ben(i,j))
56                   m = mátrix[i][j]  # ez az aktuális minimum
57                   kezdőpont = i  # és ez a kezdőpont X-ből
58                   végpont = j  # és ez a végpont Y-ból
59   
60       return (kezdőpont, végpont)
61   
62   
63   while X != V:  # addig tart az ismétlődés (ciklus), amíg minden csúcspontot nem érintettünk
64   
65       (x, y) = mini()
66   
67       X = X | {y}  # a megtalált új csúcspont elhelyezése X-ben (halmazművelet: UNIÓ)
68       print('Feszítőfa csúcsai:', X)
69       F = F | {(x, y)}  # él elhelyezése F-ben (halmazművelet: UNIÓ)
70       print('Feszítőfa éleinek halmaza: ', F)
71       Y = Y - {y}  # csúcspont törlése a maradékból (halmazművelet: KÜLÖNBSÉG)
72       print('"Maradék" csúcsok: ', Y)