Algoritmos e Estruturas de Dados

LEEC
Teoria de Grafos e Algoritmos em Grafos – 2ª Parte
Grafos – DFS
 Notar que a estratégia de procura de Tremaux, mais não é que
procura em profundidade primeiro.
 O algoritmo procede sempre abrindo uma porta e afastando-
se da origem, até que chega a um ponto em que não pode
abrir mais portas, tendo então que recuar até ao último ponto
onde deixou, pelo menos, uma porta por abrir.
 Se ao recuar nunca encontrar portas por abrir, acabará
regressando ao ponto de partida, dado que o fio que
desenrolou no caminho descendente, lhe permite esse
regresso.

62 AED (IST/DEEC)
Grafos – Implementação de DFS
(matriz de adjacências)

#define dfsR search

void dfsR(Graph *G, Edge *e)

{
int t, w = e->w;
pre[w] = cnt++;
for (t = 0; t < G->V; t++)
if (G->adj[w][t] != 0)
if (pre[t] == -1)
dfsR(G, EDGE(w, t));
}
Função a ser chamada a
partir de uma função de
procura genérica (“ADT
style”) que inicializa o
contador cnt a zero e
todas as entradas da
tabela indexada pelos
vértices pre a –1.

63 AED (IST/DEEC)
Grafos – Descrição da Implementação
 A tabela pre está associada com as lâmpadas. Se pre[i]
valer –1, significa que a luz está apagada para esse vértice.
 Quando se encontra uma aresta para um vértice em que pre
não vale –1, um vértice já visitado, essa aresta não é seguida.
 Finalmente, a própria estrutura da recursão estabelece o
mecanismo equivalente a desenrolar o novelo de fio.
 Quando um vértice não possui mais vértices adjacentes com
pre igual a –1, a chamada recursiva termina, devolvendo o
controlo de execução para o vértice que o antecedeu na
recursão.
 O retorno da recursão é equivalente a voltar a enrolar o fio.

64 AED (IST/DEEC)
Grafos – Implementação de DFS
(lista de adjacências)

#define dfsR search

void dfsR(Graph *G, Edge *e)

{
int t,
link *t;
w int
= e->w;
w = e->w;
pre[w] = cnt++;
for (t = 0;
G->adj[w];
t < G->V;
t t++)
!= NULL; t = t->next)
if (pre[t->v]
(G->adj[w][t]
== !=
-1)0)
if (pre[t] == -1)
dfsR(G,
dfsR(G,
EDGE(w,
EDGE(w,
t->v));
t));
}

65 AED (IST/DEEC)
Grafos – Comparação
 Na implementação por matriz de adjacências, para cada vértice
examinam-se todos as arestas que lhe são incidentes por
ordem de numeração dos vértices de saída.
 Avança sempre pelo primeiro (de índex mais baixo) que não tenha sido
visitado e lhe é adjacente.
 Na implementação por listas de adjacências, são
imediatamente considerados os vértices adjacentes e a ordem
de inspecção pode não coincidir com a numeração.
 Avança sempre pelo primeiro da lista de adjacências que não tenha sido
ainda visitado.

66 AED (IST/DEEC)
Grafos – ADT para procura
static int cnt, pre[maxV]; GRAPHsearch é uma função ADT
para procura genérica em grafos,
void GRAPHsearch(Graph *G) realizando os seguintes passos:
{
int v; Encontra um vértice não
cnt = 0; marcado.
for (v = 0; v < G->V; v++)
pre[v] = -1; Visita (e marca como
for (v = 0; v < G->V; v++) visitados) todos os vértices
if (pre[v] == -1) no sub-grafo ligado a que o
search(G, EDGE(v, v)); primeiro vértice pertence.
}

A função de procura não é

especificada a este nível de
abstracção.

67 AED (IST/DEEC)
Grafos – Propriedades da procura
 Propriedade – Uma função de procura em grafos marca cada
vértice do grafo se e só se a função de procura que usa
marcar cada vértice do sub-grafo ligado que contiver o vértice
inicial.
 Demonstração trivial por indução no número de sub-grafos ligados
máximos.
 Propriedade – A DFS num grafo representado por matriz de
adjacências requer um tempo proporcional a 𝑉2.
 Cada entrada da matriz de adjacências é inspeccionada uma só vez.
 Propriedade – A DFS num grafo representado por listas de
adjacências requer um tempo proporcional a 𝑉 + 𝐸.
 Inicialização proporcional a V, após o que se fazem V chamadas
recursivas e cada elemento das listas de adjacências é inspeccionado
uma só vez.

68 AED (IST/DEEC)
Grafos – Tabelas indexadas por vértices
 Muitas funções sobre grafos requerem a existência, o uso ou
construção de tabelas indexadas pelos vértices dos grafos que
processam.
 Tais tabelas são incluídas em vários níveis de abstracção
 Como variáveis globais – ex: pre em DFS.
 Na representação do próprio grafo – ex: grau de um vértice
 Como parâmetros passados, fornecidos pelos próprios clientes – ex: ao
calcular alguma tabela que seja função dos vértices.
 A inicialização destas tabelas é tipicamente feita colocando
todas as entradas a –1, por forma a poderem paralelamente
ser usadas com a mesma utilidade da tabela pre, atrás
apresentada.

69 AED (IST/DEEC)
Grafos - BFS
 Se o objectivo for encontrar o caminho mais curto entre um
par de vértices, caso exista, a DFS não é muito útil.
 A DFS poderá encontrar um caminho, mas não dá garantias de
que seja o mais curto, a menos que se determinem todos
explicitamente para posterior avaliação.
 A procura em largura primeiro (“BFS – Breadth First Search”)
é baseada exactamente nesse objectivo.
 Quando temos mais que uma aresta para percorrer,
escolhemos uma e guardamos as outras para explorar mais
tarde.
 Em DFS usamos uma pilha (LIFO) – avança para longe da entrada
enquanto puder.
 Em BFS usamos um fila (FIFO) – só avança para longe da entrada depois
de ter investigado todos corredores que dela saem.

70 AED (IST/DEEC)
Grafos – Implementação de BFS
(matriz de adjacências)
# define bfs search Cria uma fila (FIFO) com todas
void bfs(Graph *G, Edge *e) as arestas incidentes de vértices
{ visitados e de vértices ainda não
int v;
visitados.
QUEUEput(e);
while (!QUEUEempty())
if (pre[(e = QUEUEget())->w] == -1) Toma a primeira aresta da fila até
{ encontrar uma que aponte para
pre[e->w] = cnt++; um vértice não visitado.
st[e->w] = e->v;
for (v = 0; v < G->V; v++) Visita esse vértice, colocando na
if (G->adj[e->w][v] == 1)
fila todas as arestas que apontam
if (pre[v] == -1)
para vértices não visitados.
QUEUEput(EDGE(e->w, v));
}
} Tabela st guarda informação
sobre o vértice antecessor.

71 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

72 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

0 2

73 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

0 2

6
7

74 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

0 2

6
7

5 4

75 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

0 2

6
1 7

5 4

76 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

0 2

6
1 7

5 4

77 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

0 2

6
1 7

5 4

78 AED (IST/DEEC)
Grafos – Exemplo de execução (BFS)

0 2

6
1 7

5 4

79 AED (IST/DEEC)
Grafos – Propriedades da BFS (1)
 Propriedade – Durante a BFS, os vértices entram e saem da
fila FIFO por ordem crescente da sua distância ao vértice
inicial.
 Demonstração – Verifica-se uma propriedade mais forte: a fila
consiste sempre de zero ou mais vértices distando 𝑘 passos
do vértice inicial, seguidos de zero ou mais vértices distando
𝑘 + 1 passos dos vértice inicial, para algum valor de 𝑘.
 É fácil provar esta propriedade por indução.

81 AED (IST/DEEC)
Grafos – Propriedades da BFS (2)
 Propriedade – A BFS visita todos os vértices e arestas de um
grafo em tempo proporcional a 𝑉2 para a representação por
matriz de adjacências e proporcional a 𝑉 + 𝐸 para a
representação por listas de adjacências.

 Demonstração:
 Tal como em DFS, a implementação inspecciona completamente a linha
da matriz de adjacências ou a lista de pares adjacentes associada com
cada vértice visitado.
 Basta mostrar que todos os vértices são visitados.
 Todos os vértices que podem ser alcançados a partir do início estão
 (i) Na árvore criada pela procura, (ii) na fila, ou (iii) são alcançáveis a partir
dos vértices que estão na fila.
 Todos os vértices se deslocam de (iii) para (ii) e depois para (i), sendo que em
cada iteração do ciclo while (i) aumenta a sua cardinalidade.

82 AED (IST/DEEC)
Grafos – Implementação melhorada de
BFS – (matriz de adjacências)
void bfs(Graph *G, Edge *e)
{
int v, w;
QUEUEput(e);
pre[e->w] = cnt++;
while (!QUEUEempty())
{ Guarda apenas
e = QUEUEget();
w = e->w;
os vértices por
st[w] = e->v; visitar
for (v = 0; v < G->V; v++)
if ((G->adj[w][v] == 1) && (pre[v] == -1))
{
QUEUEput(EDGE(w, v));
pre[v] = cnt++;
}
}
}

83 AED (IST/DEEC)
Grafos – Problemas que BFS resolve
 Caminho mais curto entre v e w
 Tomar v como o vértice inicial e aplicar BFS até que pre[w] deixe de
ser –1.
 Caminhos mais curtos a partir de um vértice fonte
 Tomar o vértice fonte como inicial e executar a BFS até ao fim.
 Todos os caminhos mais curtos
 Como a BFS permite encontrar o caminho mais curto de um vértice
inicial para todos os outros, basta aplicar BFS para cada um dos vértices
do grafo dado como ponto de partida.
 A complexidade desta solução é cúbica no número de vértices para
representação por matrizes de adjacências.

84 AED (IST/DEEC)
Grafos – Procura generalizada (1)
 Tanto a DFS como a BFS são casos particulares de procura
generalizada em grafos.
 A implementação da BFS que se apresentou, introduz a pista
essencial de resolução de qualquer outro mecanismo de
procura.
 Isto é, tudo depende da forma como se inserem novos vértices na fila,
assumindo que se retira sempre o vértice que encabeça a fila.
 Substitua-se o conceito de fila pelo conceito de “franja”, ou
fronteira.
 Todos os vértices que estão na franja são os não visitados, candidatos à
próxima visita.

85 AED (IST/DEEC)
Grafos – Procura generalizada (GS) (2)
 Assim sendo, a estratégia genérica de procura em grafos é a
seguinte:
 Tomar um qualquer vértice como inicial e criar a “franja” colocando lá
esse vértice.
 Enquanto a “franja” não estiver vazia
 Mover ao longo de uma aresta a partir da “franja”.
 Se o vértice a que se chega não tiver sido visitado, visitá-lo a colocar na
“franja” todos os vértices não visitados que lhe são adjacentes.
 Esta estratégia garante que todos os vértices de um grafo
ligado serão visitados.
 Quando usamos uma pilha para modelar a “franja” temos DFS.
 Quando usamos uma fila, temos BFS.

86 AED (IST/DEEC)
Grafos – Implementação de procura
generalizada – (lista de adjacências)
#define pfs search

void pfs(Graph *G, Edge *e)

{
link t;
int v, w;

GQput(e); pre[e->w] = cnt++;

while (!GQempty())
{
e = GQget();
w = e->w; st[w] = e->v;
for (t = G->adj[w]; t != NULL; t = t->next)
if (pre[v = t->v] == -1)
{
GQput(EDGE(w, v));
pre[v] = cnt++;
}
else if (st[v] == -1)
GQupdate(EDGE(w, v));
}
}

87 AED (IST/DEEC)
Grafos – Propriedade da GS
 Propriedade
 Procura generalizada em grafos visita todos os vértices e arestas de um
grafo num tempo proporcional a 𝑉2 para matrizes de adjacências e
proporcional a 𝑉 + 𝐸 para listas de adjacências;
 mais, no pior caso, o tempo necessário para 𝑉 inserções, 𝑉 remoções e
𝐸 actualizações numa fila generalizada de tamanho 𝑉.
 Demonstração
 A primeira parte não depende da implementação da fila generalizada,
pelo que se aplica trivialmente.
 O tempo extra explicitado decorre naturalmente da implementação de
uma fila generalizada.

88 AED (IST/DEEC)
Grafos – Síntese da aula 3
 Procura em grafos
 Analogia com a exploração de labirintos; Estratégia de Tremaux
 Procura em profundidade - DFS
 Exemplo de execução; Implementação para matrizes de adjacências e
por listas de adjacências; Comparação; Propriedades
 Procura em largura – BFS
 Implementação por matrizes de adjacências; Exemplo de execução;
Propriedades; Implementação alternativa para matrizes de adjacências
 Procura generalizada em grafos
 Descrição; Implementação; Propriedades

89 AED (IST/DEEC)
Grafos – Árvores mínimas de suporte
 Definição – Uma árvore mínima de suporte (MST) de um
grafo ponderado é o conjunto de arestas ligando todos os
vértices, tais que a soma dos pesos das arestas é, pelo menos,
tão baixa quanto a soma dos pesos de qualquer outro
conjunto de arestas ligando todos os vértices.

 Deverá ser evidente pela definição que estamos apenas interessados em

conjuntos de arestas que constituam uma árvore de suporte.
 Como se mostra que a definição assim o estabelece?

90 AED (IST/DEEC)
Grafos – Representação de grafos
ponderados (1)
 A representação dos pesos associados às arestas em grafos
ponderados pode ser feita por:
 A matriz de adjacências deixa de ser booleana, para passar a conter o
valor associado às arestas – requer sentinela para vértices não
adjacentes.
 Cada elemento da lista de adjacências passa a conter um campo
adicional com o peso da aresta, para além do campo identificador do
vértice.
 No caso da representação das arestas ter-se-á que adicionar um campo
para o peso.
 typedef struct {int v, int w, double wt;} Edge;
 Edge *EDGE(int, int, double);
 Estas definições são incluídas no par de ficheiros GRAPH.h/GRAPH.c (como
e o quê em cada?) anteriormente introduzido.

91 AED (IST/DEEC)
Grafos - Implementação de ADT
(matriz de adjacências)

#include <stdlib.h>
#include “GRAPH.h” Grafos Ponderados
struct graph {int V; int E; double **adj;};

Graph *GRAPHinit(int V)
{
Graph *G = malloc(sizeof (graph *));
G->V = V; G->E = 0;
G->adj = MATRIXdouble(V, V, maxWT);
return G;
}

void GRAPHinsertE(Graph *G, Edge *e)

{
if (G->adj[e->v][e->w] == maxWT) G->E++;
G->adj[e->v][e->w] = e->wt;
G->adj[e->w][e->v] = e->wt;
}

92 AED (IST/DEEC)
Grafos – Propriedades das MST (1)
 Propriedade 1 – Dada uma divisão de vértices de um grafo em
dois conjuntos, qualquer árvore mínima de suporte (MST)
desse grafo contém uma aresta de menor peso que liga um
vértice de um dos conjuntos a algum dos vértices do outro.
 Demonstração
 Por redução ao absurdo.
 Suponha-se que não há ou que não é de menor peso.
 Se não existir, não é uma árvore de suporte.
 Se não for de menor peso, então seja 𝑠 a aresta de menor peso que liga
vértices dos dois conjuntos. Esta aresta não pertence à MST.
 Adicione-se a aresta 𝑠. O grafo obtido possui agora um ciclo e esse ciclo
contém também a aresta 𝑡 que liga os dois conjuntos.
 Retirando a aresta 𝑡 obtém-se uma MST de menor peso. Não é?

93 AED (IST/DEEC)
Grafos – Exemplo (1)

G G
1 2 3 1 2 3

4 5 8 4 5 8

6 7 6 7

Aresta mais curta ligando

os vértices amarelos aos
verdes.

94 AED (IST/DEEC)
Grafos – Propriedades das MST (2)
 Propriedade 2 – Dado um grafo 𝐺, considere-se o grafo 𝐺’ que
se obtém adicionando uma aresta 𝑒 a 𝐺. Adicionar 𝑒 à MST de
𝐺 e retirar a maior aresta do ciclo assim criado, gera a MST de
𝐺’.
 Demonstração:
 Se 𝑒 é maior que todos as outras arestas do ciclo, não pode pertencer à
MST de 𝐺’ (ver propriedade anterior): retirando 𝑒 de tal MST partiria o
grafo em dois e 𝑒 não seria a mais curta aresta entre essas duas partes,
porque alguma outra aresta do ciclo faz essa ligação e possui menor
peso.
 Caso contrário, seja 𝑡 a maior aresta do ciclo criado com a adição de 𝑒.
Retirando 𝑡 à MST original gera duas partes em que todas as restantes
arestas são menores que 𝑡.
 Logo, a menor aresta que liga essas duas partes é a aresta 𝑒.

95 AED (IST/DEEC)
Grafos – Exemplo (2)

Nova aresta
Árvore Mínima de Suporte
G
2 G
1 3 2
1 3
8
4 5 8
4 5

6 7
6 7

Ciclo Maior aresta do ciclo

As arestas que não pertencem à árvore mínima de suporte

são as de maior peso em algum ciclo do grafo original.
96 AED (IST/DEEC)
Grafos – Uma solução para a MST
 Ideia 1 – Construir a árvore mínima de suporte adicionando
arestas, tais que cada aresta adicionada é a de menor peso de
todas as que ligam um vértice que já está na árvore a um
outro que ainda não esteja.
 Este método é conhecido como o Algoritmo de Prim.
 Propriedade – O algoritmo de Prim calcula correctamente a
MST.
 Demonstração – Aplicar a Propriedade1, usando os vértices já
na árvore parcial como o primeiro conjunto e os que não
pertencem a essa árvore como o segundo conjunto.

98 AED (IST/DEEC)
Grafos – Outra solução para a MST
 Ideia 2 – Construir a árvore mínima de suporte adicionando
arestas por ordem crescente do seu valor, desde que a nova
aresta não forme um ciclo, parando assim que se tiverem
adicionado 𝑉 − 1 arestas.
 Este método é conhecido com o Algoritmo de Kruskal.
 Propriedade – O algoritmo de Kruskal calcula correctamente
a MST.
 Demonstração (esboço)
 Mostra-se por indução que o método constrói uma floresta de sub-
MST’s.
 Sempre que se adiciona uma aresta que feche um ciclo, só pode ser a
maior desse ciclo – Propriedade 2.
 Caso contrário, a aresta adicionada liga duas árvores e é a menor a fazer
essa ligação – Propriedade1.

99 AED (IST/DEEC)
Grafos – Outra mais...
 Ideia 3 – Começar por ligar cada vértice ao seu vizinho mais
próximo, criando, no máximo, 𝑉/2 árvores. Depois, ligar cada
árvore à outra árvore que lhe estiver mais próxima. Etc.

 Este método é conhecido como o Algoritmo de Boruvka.

 Propriedade – O algoritmo de Boruvka calcula correctamente

a MST.
 Demonstração: Cada aresta escolhida é a mais pequena que
liga dois conjuntos disjuntos – Propriedade1.

100 AED (IST/DEEC)

Grafos – Alg. de Prim (1)
(Implementação)
 É o algoritmo mais simples de implementar e é a escolha
acertada para grafos densos.
 Constrói-se a árvore adicionando o vértice que estiver mais
próximo da árvore já construída.
 A definição do método aponta para uma implementação de
força bruta, que não é aconselhável para que seja eficiente.
 Através da definição de uma estrutura de dados
complementar adequada é possível evitar cálculos excessivos.
 Precisamos
 Indicação do vértice pai, para cada vértice já na árvore.
 Para cada vértice fora da árvore, indicação de qual o vértice na árvore
que lhe está mais próximo.
 Para cada vértice fora da árvore, qual a distância ao vértice da árvore
mais próximo.

101 AED (IST/DEEC)

Grafos – Alg. de Prim (2)
(Implementação)
 A implementação mais simples daquele conjunto de dados é
através de uma tabela indexada pelos vértices.
 Pode-se usar uma estrutura para representar toda a
informação identificada acima. Vamos usar tabelas
independentes para maior clareza e generalidade.
 Para determinar o próximo vértice a adicionar, inspeccionam-
se todos os vértices fora da árvore, usando cada um como um
índice para a terceira tabela com o objectivo de determinar a
sua distância à árvore e saber qual o mais próximo.
 Quando se adiciona um vértice, 𝑣, examina-se cada uma das
suas arestas 𝑣 ↔ 𝑤, e se 𝑤 não estiver na árvore actualiza-se a
sua distância à árvore, caso 𝑣 ↔ 𝑤 tenha um peso inferior à
presente distância de 𝑤 à árvore.

102 AED (IST/DEEC)

Grafos – Alg. de Prim (3)
(Implementação)

static int fr[maxV]; fr - frente (franja)

#define P G->adj[v][w] provisória de cada nó
void GRAPHmstV(Graph *G, int st[], double val[])
{ st - aresta final na MST
int v, w, min;

for (v = 0; v < G->V; v++)

val - distância provisória
{ do nó à MST
st[v] = -1; fr[v] = v; val[v] = maxWT;
}
min - nó à menor
min = 0; st[0] = 0; val[G->V] = maxWT; distância da MST
for (v = 0; min != G->V; st[v = min] = fr[v])
for (w = 0, min = G->V; w < G->V; w++)
if (st[w] == -1)
{
if (P < val[w])
{val[w] = P; fr[w] = v;}
if (val[w] < val[min]) min = w;
}
}

103 AED (IST/DEEC)

Grafos – Exemplo de execução (1)
val[*]  maxWT
Ciclo for interior:
v  0, st[0]  0
0-0 – min  V
G
4 1 st[0] == -1 X → já na árvore
0 2 0-1 –adj[0][1] < val[1] ✓
5 6 3 val[1]  4, fr[1]  0
3 val[1] < val[min] ✓
3 4 7 7 min  1
2
0-2 – adj[0][2] < val[2] X → não adjacentes
6 3
4 0-3 –adj[0][3] < val[3] ✓
5 7 6 val[3]  3, fr[3]  0
val[3] < val[min] ✓
min  3
0-4;5;6;7 – não adjacentes
v  min, st[3]  fr[3]

104 AED (IST/DEEC)

Grafos – Exemplo de execução (2)

Ciclo for interior:

v  min = 3, st[3]  fr[3]
3-0 – min  V
G já na árvore
4 1 3-1 – adj[3][1] < val[1] X
0 2 val[1] < val[min] ✓
5 6 3 min  1
3
3-2 – adj[3][2] < val[2] ✓
3 4 7 7
2 val[2]  6, fr[2]  3
6 3 val[2] < val[min] X
4
5 7 6 3-3 – já na árvore
3-4 – adj[3][4] < val[4] ✓
val[4]  2, fr[4]  3
val[4] < val[min] ✓
min  4
3-5;6;7 – não adjacentes
v  min, st[4]  fr[4]

105 AED (IST/DEEC)

Grafos – Exemplo de execução (3)

G G G
1 4 1 1
4 4
0 2 0 2 0 2
5 6 3 5 6 3 5 6 3
3 3 3
3 4 7 7 3 4 7 7 3 4 7 7
2 2 2
6 3 6 3 6 3
4 4 4
5 7 5 7 6 5 7 6
6

G G
4 1 1
4
0 2 0 2
5 6 3 5 6 3
3 3
3 4 7 7 3 4 7 7
2 2
6 3 6 3
4 4
5 7 6 5 7 6
106 AED (IST/DEEC)
Grafos – Árvore de procura (Alg. Prim)

0
4
∞
G 1 ∞ 3 ∞
1 ∞ ∞ 7
4 2 3 6
4 5
0 2
5 6 3
3
3 4 7 7
2
6 3
4
5 7 6

108 AED (IST/DEEC)

Grafos – Árvore de procura (Alg. Prim)

0
4
∞
G 1 3 ∞
1 ∞ 7
4 3 6
5
0 2
5 6 3 6 2
3 2 4
3 4 7 7
2
6 3
4
5 7 6

109 AED (IST/DEEC)

Grafos – Árvore de procura (Alg. Prim)

0
4
∞
G 1 3
1 7
4 3
0 2
5 6 3 6 2
3 2 4
3 4 7 7
2 6 3
6 3
4 5 6
5 7 6

110 AED (IST/DEEC)

Grafos – Árvore de procura (Alg. Prim)

0
4
G 1 3
4 1
3
0 2
5 6 3 6 2
3 2 4
3 4 7 7
2 6 3
6 3
4 5 6
5 7 6
4
7

111 AED (IST/DEEC)

Grafos – Árvore de procura (Alg. Prim)

0
4
G 1 3
4 1
3
0 2
5 6 3 6 2
3 2 4
3 4 7 7
2 6 3
6 3
4 5 6
5 7 6
4
7

112 AED (IST/DEEC)

Grafos – Árvore de procura (Alg. Prim)

0
4
G 1 3
4 1
3
0 2
5 6 3 2
3 4
3 4 7 7
2 6 3
6 3
4 5 6
5 7 6
4
7
3
2

113 AED (IST/DEEC)

Grafos – Árvore de procura (Alg. Prim)

0
4
G 1 3
4 1
3
0 2
5 6 3 2
3 4
3 4 7 7
2 6 3
6 3
4 5 6
5 7 6
4
7
3
2

114 AED (IST/DEEC)

Grafos – Árvore de procura (Alg. Prim)

0
4
G 1 3
4 1
3
0 2
5 6 3 2
3 4
3 4 7 7
2 6 3
6 3
4 5 6
5 7 6
4
7
3
2

115 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2
5 6 3
3
3 4 7 7
2
6 3
4
5 7 6

116 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2 7 ∞/2 ∞/2 6/2 ∞/2 ∞/2 4/7
5 6 3
3
3 4 7 7
2
6 3
4
5 7 6

117 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2 7 ∞/2 ∞/2 6/2 ∞/2 ∞/2 4/7
5 6 3 6 ∞/2 ∞/2 6/2 3/6 7/6
3
3 4 7 7
2
6 3
4
5 7 6

118 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2 7 ∞/2 ∞/2 6/2 ∞/2 ∞/2 4/7
5 6 3 6 ∞/2 ∞/2 6/2 3/6 7/6
3
3 4 7 7 4 ∞/2 ∞/2 2/4 6/4
2
6 3
4
5 7 6

119 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2 7 ∞/2 ∞/2 6/2 ∞/2 ∞/2 4/7
5 6 3 6 ∞/2 ∞/2 6/2 3/6 7/6
3
3 4 7 7 4 ∞/2 ∞/2 2/4 6/4
2
6 3
4 3 3/3 5/3 6/4
5 7 6

120 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2 7 ∞/2 ∞/2 6/2 ∞/2 ∞/2 4/7
5 6 3 6 ∞/2 ∞/2 6/2 3/6 7/6
3
3 4 7 7 4 ∞/2 ∞/2 2/4 6/4
2
6 3
4 3 3/3 5/3 6/4
5 7 6 0 4/0 6/4

121 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2 7 ∞/2 ∞/2 6/2 ∞/2 ∞/2 4/7
5 6 3 6 ∞/2 ∞/2 6/2 3/6 7/6
3
3 4 7 7 4 ∞/2 ∞/2 2/4 6/4
2
6 3
4 3 3/3 5/3 6/4
5 7 6 0 4/0 6/4
1 6/4

122 AED (IST/DEEC)

Grafos – Exemplo com tabela
 Tomando o vértice 2 como ponto de partida
 Legenda – val/fr
0 1 2 3 4 5 6 7
G 2 ∞/2 ∞/2 6/2 ∞/2 ∞/2 7/2 3/2
4 1
0 2 7 ∞/2 ∞/2 6/2 ∞/2 ∞/2 4/7
5 6 3 6 ∞/2 ∞/2 6/2 3/6 7/6
3
3 4 7 7 4 ∞/2 ∞/2 2/4 6/4
2
6 3
4 3 3/3 5/3 6/4
5 7 6 0 4/0 6/4
1 6/4
5

123 AED (IST/DEEC)

Grafos – Alg. de Prim (Propriedade)
 Propriedade – Com o algoritmo de Prim, pode-se determinar
a MST de um grafo denso em tempo linear.
 Demonstração:
 A simples observação do código permite concluir que o tempo de
execução é proporcional a 𝑉2, pelo que é linear para grafos densos.
 Cada vez que se visita um vértice, uma passagem pelos vértices fora da
árvore serve o objectivo duplo de actualizar a distância mínima de cada
vértice à árvore e de determinar qual está mais próximo. i.e., qual o
próximo a visitar.
 Descrição:
 Deslocar a aresta mais pequena da franja para a árvore.Visitar o vértice
a que conduz e colocar na franja todas as arestas que dele saem para
vértices não visitados, substituindo a aresta mais comprida quando duas
arestas da franja apontam para o mesmo vértice.

124 AED (IST/DEEC)

Grafos – Alg. de Kruskal (1)
(Implementação)
 O algoritmo de Prim adiciona uma aresta de cada vez a uma
única árvore em construção.

 O algoritmo de Kruskal também adiciona uma aresta de cada

vez, mas possui várias pequenas árvores que se vão agregando
à medida que a execução evolui.

 Tem início numa floresta de 𝑉 árvores – uma por vértice – e

termina quando apenas existe uma árvore – a árvore mínima
de suporte.

 Há que ordenar as arestas com um qualquer algoritmo de

ordenação e posteriormente utilizar um dos algoritmos
discutidos para o problema da conectividade.

125 AED (IST/DEEC)

Grafos – Alg. de Kruskal (1)
(Implementação)

void GRAPHmstE(Graph *G, Edge mst[])

{ 1. Ordenação do
int i, k;
Edge a[maxE]; vector de arestas, a.
int E = GRAPHedges(a, G);
2.Criação de 𝑉
sort(a, 0, E-1);
UFinit(G->V);
conjuntos com um
for (i = 0, k = 0; i < E && k < G->V-1; i++) vértice cada.
if (!UFfind(a[i].v, a[i].w))
{ 3. Se a menor
UFunion(a[i].v, a[i].w);
mst[k++] = a[i]; aresta ainda não
} incluída não ligar
} dois pares que já
estão ligados, inclui-
la na árvore.

126 AED (IST/DEEC)

Grafos – Exemplo de execução (1)

Ordenação das arestas:

<(3,4); (2,7); (0,3); (4,6); (0,1); (6,7);
(1,3); (2,3); (4,5); (5,6); (2,6)>
G
4 1 Partição inicial:
0 2 {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}}
5 6 3
3 i  0; k  0
3 4 7 7 a[i].v = 3; a[i].w = 4
2
6 3 {{0}, {1}, {2}, {3, 4}, {5}, {6}, {7}}
4
7 mst[k]  (3,4)
5 6
k  1
i  1
a[i].v = 2; a[i].w = 7
{{0}, {1}, {2, 7}, {3, 4}, {5}, {6}}
mst[k]  (2,7)
k  2

127 AED (IST/DEEC)

Grafos – Exemplo de execução (2)

G G G
4 1 1 4 1
4
0 2 0 2 0 2
5 6 3 5 6 3 5 6 3
3 3 3
3 4 7 7 3 4 7 7 3 4 7 7
2 2 2
6 3 6 3 6 3
4 4 4
5 7 6 5 7 6 5 7 6

G G
4 1 1
4
0 2 0 2
5 6 3 5 6 3
3 3
3 4 7 7 3 4 7 7
2 2
6 3 6 3
4 4
5 7 6 7
5 6
128 AED (IST/DEEC)
Grafos – Alg. de Kruskal
(Propriedade)
 Propriedade – O algoritmo de Kruskal calcula a MST de um
grafo num tempo proporcional a 𝐸 lg 𝐸.

 Demonstração
 Esta propriedade é consequência do facto de o tempo de execução
incluir uma ordenação de 𝐸 arestas seguida de 𝐸 operações procura e
𝑉 − 1 operações de união.
 PORQUÊ?
 Se utilizarmos os melhores algoritmos para cada uma das operações
identificadas, tais como “heapsort” para a ordenação e procura-união
ponderada com compressão de caminho para a conectividade, o custo
da ordenação domina.

129 AED (IST/DEEC)

Grafos – Alg. de Boruvka (1)
(Implementação)
 Tal como o algoritmo de Kruskal, este algoritmo constrói a
MST adicionando arestas a uma floresta de sub-árvores, todas
elas MST’s.
 A diferença reside no facto de a adição se processar em fases,
em que para cada fase se adicionam várias arestas.
 Em cada fase determinam-se as arestas mais curtas que ligam
cada sub-árvore com outra.
 Em seguida adicionam-se todas essas arestas.
 Mais uma vez, as funções elementares procura e união serão
cruciais para uma implementação eficiente.

130 AED (IST/DEEC)

Grafos – Alg. de Boruvka (2)
(Implementação)
 Torna-se necessário permitir que a função de procura seja
ligeiramente alterada para que associe um índice com cada
uma das sub-árvores.
 Assim sendo, mantém-se uma tabela indexada por vértices
indicando, para cada sub-árvore, qual a sua vizinha mais
próxima.
 De seguida executam-se as seguintes operações em cada
aresta do grafo:
 Se ligar dois vértices na mesma árvore, ignorá-la.
 Caso contrário, verificar as distâncias do vizinho mais próximo de cada
uma das árvores, actualizando-se se apropriado.

131 AED (IST/DEEC)

Grafos – Alg. de Boruvka (3)
(Implementação)
 Depois de fazer esta avaliação, a tabela dos vizinhos mais
próximos contém a informação necessária para ligar sub-
árvores.
 Para índice dos vértices faz-se uma união, ligando os seus
vizinhos mais próximos.
 Em seguida, retiram-se as arestas mais longas que ligam outros
pares de vértices nos pares de árvores MST ligadas.

132 AED (IST/DEEC)

Grafos – Alg. de Boruvka (4)
(Implementação)
Edge nn[maxV];

void GRAPHmstE(Graph *G, Edge mst[]) 1.Tabela dos vizinhos

{
int h, i, j, k, v, w, N;
mais próximos, nn.
Edge e, a[maxE];
int E = GRAPHedges(a, G); 2. Criação de tabela de
arestas, a.
for (UFinit(G->V); E != 0; E = N)
{ 3. Inicialização da
for (k = 0; k < G->V; k++)
nn[k] = EDGE(G->V, G->V, 1.0);
distância aos vizinhos.
for (h = 0, N = 0; h < E; h++)
{ 4. Determinação da
i = find(a[h].v); j = find(a[h].w); sub-árvore a que
if (i == j) continue;
if (a[h].wt < nn[i].wt) nn[i] = a[h];
pertencem as arestas.
if (a[h].wt < nn[j].wt) nn[j] = a[h];
...
5. Cálculo do vizinho
mais próximo.

133 AED (IST/DEEC)

Grafos – Alg. de Boruvka (5)
(Implementação)
...
a[N++] = a[h]; 6. Deita fora de a as
}
arestas que ligam
for (k = 0; k < G->V; k++) vértices na mesma
{ sub-árvore!!!
e = nn[k];
v = e.v; 7. Funde duas sub-
w = e.w;
if ((v != G->V) && !UFfind(v, w)) árvores, se ainda não
{ associadas, usando a
UFunion(v, w);
mst[k] = e; aresta mais curta, e.
}
}
}
}

134 AED (IST/DEEC)

Grafos – Exemplo de execução (1)
Chamada a GRAPHedges produz
a =[(0,1,4);(0,3,3);(1,3,5);(2,3,6);(2,6,7);
(2,7,3);(3,4,2);(4,5,6);(4,6,3);(5,6,7);
(6,7,4)]; E  11
G Ciclo for exterior
4 1
0 2 UFinit  [0, 1, 2, 3, 4, 5, 6, 7]
5 6 3 Primeiro ciclo for produz
3 nn  [8 vezes (8,8,7)] (custos não normalizados)
3 4 7 7 Segundo ciclo for
2
6 3 h  0; N  0
4 i  0; j  1 (diferentes conjuntos)
5 7 6 a[h].wt < nn[i].wt ✓
nn[0]  (0,1,4)
a[h].wt < nn[j].wt ✓
nn[1]  (0,1,4)
a[N]  a[h]; N  1
h  1

135 AED (IST/DEEC)

Grafos – Exemplo de execução (2)
h  1
i  0; j  3 (diferentes conjuntos)
a[h].wt < nn[i].wt ✓
G nn[0] (0,3,3)
4 1 a[h].wt < nn[j].wt ✓
0 2 nn[j] (0,3,3)
5 6 3 a[N]  a[h]; N  2
3 h  2
3 4 7 7 i  1; j  3 (diferentes conjuntos)
2
6 3 a[h].wt < nn[i].wt X
4
7 a[h].wt < nn[j].wt X
5 6
a[N]  a[h]; N  3
...
No final do segundo ciclo for tem-se
nn = [ (0,3,3);(0,1,4);(2,7,3);(3,4,2);
(3,4,2);(4,5,6);(4,6,3);(2,7,3)]
N = 11;

136 AED (IST/DEEC)

Grafos – Exemplo de execução (3)
Terceiro ciclo for
k  0
e  nn[k]; v  0; w  3
G v != 8 && !UFfind(0,3) ✓
4 1 UFunion(0,3); mst[k]  (0,3,3)
0 2 k  1
5 6 3 e  nn[k]; v  0; w  1
3 v != 8 && !UFfind(0,1) ✓
3 4 7 7 UFunion(0,1); mst[k]  (0,1,4)
2
6 3 k  2
4
7 e  nn[k]; v  2; w  7
5 6
v != 8 && !UFfind(2,7) ✓
UFunion(2,7); mst[k]  (2,7,3)
k  3
e  nn[k]; v  3; w  4
v != 8 && !UFfind(3,4) ✓
UFunion(3,4); mst[k]  (3,4,2)

137 AED (IST/DEEC)

Grafos – Exemplo de execução (4)
k  4
e  nn[k]; v  3; w  4
v != 8 && !UFfind(3,4) X
G k  5
4 1
e  nn[k]; v  4; w  5
0 2
5 v != 8 && !UFfind(4,5) ✓
6 3
3 UFunion(4,5); mst[k]  (4,5,6)
3 4 7 7 k  6
2
6 3 e  nn[k]; v  4; w  6
4
7 v != 8 && !UFfind(4,6) ✓
5 6
UFunion(4,6); mst[k]  (4,6,3)
k  7
e  nn[k]; v  2; w  7
v != 8 && !UFfind(2,7) X
Fim do 3º ciclo for - Retorno ao ciclo for externo

138 AED (IST/DEEC)

Grafos – Exemplo de execução (5)
No final desta iteração existem 2 sub-árvores
Sejam 1* e 2* os seus identificadores
E  N == 11
G Primeiro ciclo for produz
4 1 nn  [8 vezes (8,8,7)] (custos não
0 2 normalizados)
5 6 3 Segundo ciclo for
3 N  0
3 4 7 7 h  0; i  1*; j  1* (mesmo conjunto)
2
6 3 h  1: i  1*; j  1* (mesmo conjunto)
4 h  2: i  1*; j  1* (mesmo conjunto)
5 7 6 h  3: i  2*; j  1* (diferentes conjuntos)
a[h].wt < nn[i].wt ✓
nn[2*] (2,3,6)
a[h].wt < nn[j].wt ✓
nn[1*] (2,3,6)
a[N]  a[h]; N  1 (arestas fora...)

139 AED (IST/DEEC)

Grafos – Exemplo de execução (6)
h  4: i  2*; j  1* (diferentes conjuntos)
a[h].wt < nn[i].wt X
a[h].wt < nn[j].wt X
G a[N]  a[h]; N  2
4 1
h  5: i  2*; j  2* (mesmo conjunto)
0 2
5 h  6: i  1*; j  1* (mesmo conjunto)
6 3
3 h  7: i  1*; j  1* (mesmo conjunto)
3 4 7 7 h  8: i  1*; j  1* (mesmo conjunto)
2
6 3 h  9: i  1*; j  1* (mesmo conjunto)
4
7 h  10: i  1*; j  2* (diferentes conjuntos)
5 6
a[h].wt < nn[i].wt ✓

nn[1*]  (6,7,4)
a[h].wt < nn[j].wt ✓
nn[2*]  (6,7,4)
a[N]  a[h]; N  3

140 AED (IST/DEEC)

Grafos – Exemplo de execução (7)
No final do segundo ciclo for tem-se
nn = [ 6 vezes (8,8,7) e 2 vezes (6,7,4)]
Porquê?...
a = [(2,3,6);(2,6,7);(6,7,4); ...]
G
4 1 Porquê?
0 2 N = 3
5 6 3 Terceiro ciclo for
3 k  para alguns valores
3 4 7 7 e  nn[k]; v  8; w  8
2
6 3 v != 8 && !UFfind(0,3) X
4
7 ...
5 6
k  para outro – qual?
e  nn[k]; v  6; w  7
v != 8 && !UFfind(6,7) ✓
UFunion(6,7); mst[k]  (6,7,4)
...

141 AED (IST/DEEC)

Grafos – Alg. de Boruvka
(Propriedade)
 Propriedade – O algoritmo de Boruvka calcula a MST de um
grafo num tempo inferior a 𝐸 lg 𝑉 lg ∗ 𝑉.

 Demonstração:
 Dado que o número de sub-árvores na floresta se reduz, pelo menos, a
metade em cada fase, o número de fases não é maior que lg 𝑉.
 O tempo de cada fase é, no máximo, proporcional ao custo de 𝐸
operações de procura.

 Observações:
 A expressão acima é bastante conservadora, na medida em que ignora a
redução de arestas ocorrida em cada fase.
 Concebido em 1926 e desde os anos 80 a base para o desenvolvimento
de algoritmos eficientes para MST’s, assim como para algoritmos
paralelos

142 AED (IST/DEEC)

Grafos – Comparação dos métodos (1)

Algoritmo Pior caso Comentário

Prim (padrão) 𝑉2 Óptimo para grafos densos
Prim (com PFS)* 𝐸 lg 𝑉 Pior caso conservador
Kruskal (padrão) 𝐸 lg 𝐸 Custo de ordenação domina
Kruskal (ord. parcial)** 𝐸 + 𝑋 lg 𝑉 Depende da aresta maior
Boruvka 𝐸 lg 𝑉 Pior caso muito conservador

Variantes não discutidas

*PFS – Priority-First Search
**ord. parcial – evitar ordenar todas as arestas, dado que podem
não ser necessárias (via heapsort, por exemplo).

143 AED (IST/DEEC)

Grafos – Comparação dos métodos (2)
E V H P K K* e/E B e/E
Densidade - 2 H: Prim – lista de
20000 10000 22 9 11 1.00 14 3.30 adjacências/Heapsort
50000 25000 69 24 31 1.00 38 3.30
100000 50000 169 49 66 1.00 89 3.80 P: Prim – matriz de
200000 100000 389 108 142 1.00 189 3.60
adjacências
Densidade - 20
20000 1000 5 20 6 5 0.20 9 4.20
50000 2500 12 130 16 15 0.28 25 4.60
K: Kruskal
100000 5000 27 34 31 0.30 55 4.60
200000 10000 61 73 68 0.35 123 5.00 K*: Kruskal – com
Densidade - 100 ordenação parcial
100000 1000 17 24 30 19 0.06 51 4.60
250000 2500 44 130 81 53 0.05 143 5.20 B: Boruvka
500000 5000 93 181 113 0.06 312 5,50
1000000 10000 204 377 218 0.06 658 5,60
e/E: arestas
Densidade – V/2.5
400000 1000 60 20 137 78 0.02 188 4.50
examinadas (uniões)
2500000 2500 409 128 1056 687 0.01 1472 5.50

144 AED (IST/DEEC)

Grafos – Síntese da aula 4
 Árvores de suporte mínimas – MST
 Representação e implementação de ADT para grafos ponderados;
Propriedades das MST’s – exemplos
 Árvores de suporte mínimas – MST
 Propostas de solução para cálculo de MST’s
 Algoritmo de Prim
 Descrição; Implementação; Exemplo de execução; Análise de eficiência
 Algoritmo de Kruskal
 Descrição; Implementação; Exemplo de execução; Análise de eficiência
 Algoritmo de Boruvka
 Descrição; Implementação; Exemplo de execução; Análise de eficiência
 Comparação dos três métodos

145 AED (IST/DEEC)