Entrar Ainda não tem acesso?
Solucionado (ver solução)
Solucionado
(ver solução)
1
resposta

Adicionar ciclo ao kruskall

por Renan Tomazini
| 357.2k xp | 29 posts
Estágiario - Desenvolvedor de Software e Design na CCAC

Estou com uma duvida sobre como testar os ciclos de um grafo em python com o grafo sendo formado por letras. O codigo esta assim:

#pontos = [a,b,c,d]
grafos = {'a''b': 6,'a''c': 3, 'a''d' : 7,'b''c':5,'b''d': 1,'c''d': 4}
floresta = []

print(grafos)

def ciclo(ponto,floresta):






def kruskar(grafos):
  grafos_ord = sorted(grafos, key = grafos.get)
  print(grafos_ord)
  kruskal = []
  for ponto in grafos_ord:
    if (ciclo(ponto,floresta) == True):
      print(ponto)
    else:
      kruskal.append(ponto)
  print(kruskal)
  print

Para fazer o kruskall preciso montar as conexoes na floresta e ir juntando elas, eu pensei em fazer por lista mas estou achando um pouco complicado de implementar. Teria uma forma mais simples de fazer?

1 resposta
solução!
por Welton Vaz de Souza
| 240.5k xp | 321 posts
Analista de Desenvolvimento de Sistemas

Renan,

Da uma olha se ajuda, nesta Implementação ingênua do algoritmo

parent = dict()
rank = dict()

def make_set(vertice):
    parent[vertice] = vertice
    rank[vertice] = 0

def find(vertice):
    if parent[vertice] != vertice:
        parent[vertice] = find(parent[vertice])
    return parent[vertice]

def union(vertice1, vertice2):
    root1 = find(vertice1)
    root2 = find(vertice2)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
    else:
        parent[root1] = root2
    if rank[root1] == rank[root2]: rank[root2] += 1

def kruskal(graph):
    for vertice in graph['vertices']:
    make_set(vertice)
    minimum_spanning_tree = set()
    edges = list(graph['edges'])
    edges.sort()
    #print(edges)
    for edge in edges:
    weight, vertice1, vertice2 = edge
    if find(vertice1) != find(vertice2):
        union(vertice1, vertice2)
        minimum_spanning_tree.add(edge)

    return sorted(minimum_spanning_tree)

graph = {
'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
'edges': set([
(7, 'A', 'B'),
(5, 'A', 'D'),
(7, 'B', 'A'),
(8, 'B', 'C'),
(9, 'B', 'D'),
(7, 'B', 'E'),
(8, 'C', 'B'),
(5, 'C', 'E'),
(5, 'D', 'A'),
(9, 'D', 'B'),
(7, 'D', 'E'),
(6, 'D', 'F'),
(7, 'E', 'B'),
(5, 'E', 'C'),
(15, 'E', 'D'),
(8, 'E', 'F'),
(9, 'E', 'G'),
(6, 'F', 'D'),
(8, 'F', 'E'),
(11, 'F', 'G'),
(9, 'G', 'E'),
(11, 'G', 'F'),
])
}

print(kruskal(graph))