MIS greedy.py

g = {}
g[1] = [2, 3, 5]
g[2] = [1, 6, 4]
g[3] = [1, 4, 7]
g[4] = [2, 3, 8]
g[5] = [1, 6, 7]
g[6] = [2, 5, 8]
g[7] = [3, 5, 8]
g[8] = [4, 6, 7]
removidos = [True] + 8 * [False]
def mínimo():
  m = removidos.index(False)
  for v in g:
    if removidos[v]: continue
    if len(g[v]) < len(g[m]):
      m = v
  print ('Mínimo:', m)
  return m

def remove_vizinhos(v):
  removidos[v] = True
  for x in g[v]:
    removidos[x] = True
    g[x] = []
    for y in g:
      if x in g[y]:
        g[y].remove(x)
  print ('G =', g)
  print ('Removidos =', removidos)
  
s = []
print ('G =', g)
while False in removidos:
  v = mínimo()
  s.append(v)
  remove_vizinhos(v)
  
print (s)