Adjancência com código da Francyelle

adjacencia.py

import matplotlib.pyplot as plt
import numpy as np


# Calcula distância entre dois pontos
def distancia(a, b):
    dist = ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** (1 / 2)
    return dist


# Recebe um conjunto de pontos e acha a ávore geradora mínimia usando a ideia de Prim
def prim(pontos):
    menor = float('inf')
    escolhidos = [pontos[0]]
    arestas = []
    del pontos[0]
    n = 0
    final = len(pontos)
    while (n < final):
        menor = float('inf')
        for x in range(0, len(pontos)):
            for y in range(0, len(escolhidos)):
                if (distancia(pontos[x], escolhidos[y]) < menor):
                    menor = distancia(pontos[x], escolhidos[y])
                    aresta = escolhidos[y], pontos[x]
                    rponto = pontos[x]
        escolhidos.append(rponto)
        pontos.remove(rponto)
        arestas.append(aresta)
        n = n + 1
    return arestas


############ Imprime ###########
pontos = [(4, 2), (6, 4), (8, 6), (10, 8), (2, 12), (10, 12), (13, 18), (5, 9)]
tuples = [(4, 2), (6, 4), (8, 6), (10, 8), (2, 12), (10, 12), (13, 18), (5, 9)]
x, y = list(), list()

for t1, t2 in pontos:
    x.append(t1)
    y.append(t2)

    
#########################################################
###########  Começo da parte que você quer ##############
#########################################################

# Local onde você liga as arestas que você obtem.
arestas = prim(pontos)

# Criar gráfico que será aberto no final do programa
plt.scatter(x, y)
for (x1, y1), (x2, y2) in arestas:
    plt.plot((x1, x2), (y1, y2))

#Parte que acerta arestas para o programa funcionar
for i in arestas:
    arestas[arestas.index(i)] = list(i)
for i in arestas:
    for y in i:
        arestas[arestas.index(i)][i.index(y)] = list(y)

# Preparando itens que serão úteis depois.
vertices = []
nos = set()
adjacentes = []

# Isso tudo apenas prepara uma lista com apenas um de cada vértice.
for aresta in arestas:
    for p in range(2):
        a = tuple(aresta[p])
        vertices.append(a)

for vertice in vertices:
    nos.add(vertice)

nos = list(nos)

for no in nos:
    new_no = list(no)
    nos[nos.index(no)] = new_no

# Fim do preparo


# Indice inicial para contar a lista adjacente.
# Nesse programa pressupõe já que o índice do vértice único sendo analisado
# tem um número indice correspondente à sua posição na lista nos.... o que significa
# que i_ad não precisa existir, só preciso puxar nos.index(no)... hmm por isso que
# comentar é importante, vemos cada coisa que tava no subconsciente...
i_ad = 0

for no in nos:  # Tudo abaixo irá rodar pra cada vértice único existente.
    for p in range(2):  # Preparando pra testar ambos os vértices de cada aresta
        for aresta in arestas:  # Olhando em cada aresta, um vértice específico
            if no == aresta[p]:  # Comparando se o vértice é o atualmente sendo procurado
                # print("Inserindo valor...")    # no == aresta[p] então um valor será inserido.
                try:  # Verificando se existe uma lista de índice i_ad. Se resultar em erro
                    if adjacentes[i_ad][1] != no:  # significa que não tem e o except cria tal lista.
                        print("Nada vai printar, só preciso do erro")
                except:
                    adjacentes.append([i_ad, no])
                    # print("Iniciando lista de adjacência para",no,":", adjacentes)
                    # print("")
                if p == 0:
                    adjacentes[i_ad].append(aresta[1])  # Ao notar que na aresta existe o vértice sendo procurado
                else:  # colocamos o seu par na lista de adjacência. :)
                    adjacentes[i_ad].append(aresta[0])
    i_ad += 1  # Próximo indice.

print("Lista de Adjacência completa:")
# print('\n'.join(map(str, adjacentes)))    # Apresenta lista de adjacência de forma mais legível.

for i in adjacentes:  # O resultado sem o primeiro número.
    print(i[1:])

# mostrar plot
plt.show()