greedy_graph_alghoritm.py

# coding: utf-8

import unittest
from pprint import pprint

DEBUG = True

def greedy(g):
    vertices = []

    while g:
      if DEBUG:        
          print("Grafo: \n")
          pprint(g)
          print("\n")
      # encontra o menor vertice
      vertice_with_min_edges = min(g.items(), key=lambda x : len(x[1]))
      min_vertice, edges = vertice_with_min_edges

      if DEBUG:
          print("vertice escolhido foi %d \n" % min_vertice)

      # adiciona o menor vertices pra lista de vertices
      vertices.append(min_vertice)
      for edge in edges + vertices:
          if edge in g:
              g.pop(edge)
          for vertice in g:
              if edge in g[vertice]:
                  g[vertice].remove(edge)
    return vertices


class GreedyTests(unittest.TestCase):

    def test_empty(self):
        self.assertListEqual(greedy({}), [])

    def test_g(self):
        g = {
            5: [7],
            7: [5, 4, 3, 1, 2],
            4: [3, 7],
            3: [4, 7, 2, 6],
            1: [7, 6],
            2: [7, 3],
            6: [1, 3]
        }
        self.assertListEqual(greedy(g), [5, 1, 2, 4])

if __name__ == "__main__":
    # coloque como False se nao quiser ver o andamento do algoritmo
    # DEBUG = False
    unittest.main()