Esercizi e sorgenti dei programmi

Algoritmo di Kruskal

Il seguente programmino Python è una codifica dell'algoritmo di Kruskal per il calcolo dell'albero ricoprente di costo minimo (MST - Minimum Spanning Tree) di un grafo non orientato con pesi non negativi assegnati agli spigoli.

Codifica in linguaggio Python 3.x

#
#   MST-Kruskal.py
#
#   Dato un grafo non orientato casuale con pesi posivi
#   assegnati agli spigoli, calcola l'albero ricoprente
#   di peso minimo usando l'algoritmo di Kruskal
#

import networkx as nx
import numpy    as np
from   random import *

def makeSet(x, s):
   s[x] = x
   return

def findSet(x, s):
   return(s[x])

def union(x, y, s):
   z = s[y]
   for i in range(len(s)):
      if s[i] == z: s[i] = s[x]
   return

def randomWeightedGraph(G, n, P, Wmax):
   for v in range(1,n+1):
      G.add_node(v)
   for u in range(1,n):
      for v in range(u+1,n+1):
         x = random()
         if x>0 and x<=P:
            w = randint(1,Wmax)
            G.add_edge(u,v,weight=w)
   return

#   Inizio del programma: genero il grafo casuale
g = nx.Graph()
n = int(input("Numero di vertici: "))
s = np.empty((n+1), dtype=int)
p = float(input("Probabilita': "))
peso = int(input("Peso massimo per gli spigoli: "))
randomWeightedGraph(g, n, p, peso)

#   PASSO 1: costruisco l'albero T = (V, E) con V(T) = V(G)
t = nx.Graph()
for v in g:
   t.add_node(v)

#   PASSO 2-4: creo l'insieme S[v] per ogni v vertice di G
for v in g:
   makeSet(v, s)

#   PASSO 5: costruisco l'insieme degli spigoli E(G) come
#      una matrice e ordino gli spigoli in base al peso crescente
e = g.number_of_edges()
print("numero di spigoli", e)
w = np.zeros((2*e, 3), dtype=int)
e = 0
for u in g:
   for v in g.neighbors(u):
      print(u, v, g[u][v]['weight'])
      w[e][0] = u
      w[e][1] = v
      w[e][2] = g[u][v]['weight']
      e = e + 1
w = w[w[:, 2].argsort()]

#   PASSO 4: seleziono gli spigoli (u,v) in ordine di peso crescente e
#      se u e v non appartengono allo stesso insieme unisco gli insiemi
#      s[i] e s[v] e aggiungo lo spigolo (u,v) all'abero T
for i in range(e):
   if findSet(w[i][0], s) != findSet(w[i][1], s):
      t.add_edge(w[i][0], w[i][1], weight=w[i][2])
      union(w[i][0], w[i][1], s)

print("\nAlbero ricoprente:")
for u in t:
   for v in t.neighbors(u):
      print(u, v, t[u][v]['weight'])