Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment