-
Notifications
You must be signed in to change notification settings - Fork 0
/
pseudo_agm
46 lines (43 loc) · 1.79 KB
/
pseudo_agm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
L <- lista com as arestas do grafo ordenadas por w em ordem crescente => O( m log m )
A <- conjunto vazio de arestas
represent <- vetor [0,...,n-1] de inteiros
comp <- vetor [0,...,n-1] de nós
para u em V faça
comp[u].primeiro <- novo_nó(u, nulo)
// cria um novo no, onde aponta para o nulo.
comp[u].ultimo <- comp[u].primeiro
// liga o ultimo ao primeiro.
comp[u].tamanho <- 1
represent[u] <- u
// o representante de cada vertice, é o proprio vertice.
enquanto tamanho(A) != n-1 faça
// enquanto o tamanho nao for igual ao tamanho de uma arvore...
{u,v} <- L.remover_primeiro()
// removemos a primeira aresta
se represent[u] != represent[v] então
// se forem de componentes distintas, inserimos.
A.inserir({u,v})
x <- represent[u]
y <- represent[v]
se comp[x].tamanho < comp[y].tamanho então
// aqui fazemos uma troca, caso um seja maior que o outro.
aux <- x
x <- y
y <- aux
// aqui onde complica, mas criamos Z para manter os nós devidamente ligados.
// ou seja, o primeiro no aponta para Z.
z <- comp[y].primeiro
// Z aponta para o proximo do ultimo de X.
comp[x].ultimo.proximo <- z
// o ultimo da maior, aponta pro primeiro da menor, pq ai vai atualizando.
comp[x].ultimo <- comp[y].ultimo
// o ultimo de Y aponta para o ultimo de X.
comp[x].tamanho <- comp[x].tamanho + comp[y].tamanho
// unimos os conjuntos, ou seja, somamos os tamanhos.
enquanto z != nulo faça => O ( n log n )
// aqui finalizamos o nó de Z.
represent[z.elemento] <- x
// pra atualizar todos os representantes da menor, para a atual maior.
z <- z.proximo
retorne A
// retornamos o conjunto.