2016-I

Grafos

COM11087-Tópicos Especiais em Programação IIedmar.kampke@ufes.br

Introdução

2016-I2

� Grafos são estruturas muito estudadas naCiência da Computação para modelagem deproblemas

� Euler (1736) em Königsberg (antiga Prússia),com o problema das 7 pontes sobre o Rio Pregel

� Definição: Um grafo G = (V,E) é formado por umconjunto V de vértices e um conjunto E depares (u,v), onde cada par representa umaaresta que liga os vértices u e v.

Introdução

2016-I3

� Exemplos:

1) Mapa rodoviário, as cidades seriam os vérticese as estradas as arestas

2) Rede social, ou para estudar osrelacionamentos humanos, as pessoas seriam osvértices e as relações interpessoais as arestas

3) Centro de Distribuição de Água, cada centro debombeamento é um vértice e as tubulações sãoas arestas

Conceitos

2016-I4

� Grau de vértice

� Grafo não direcionado / Grafo direcionado(Dígrafo)

� Ponderados / Não-Ponderado

� Trilha/Caminhos/Circuitos

� Cíclico / Acíclico

� Simples / Não-simples

Conceitos

2016-I5

� Planaridade

� Isomorfismo

� Subgrafo e Complemento

� Conexidade

� Árvores

� Grafo Completo

� Grafo k-partido

2016-I6

� Matriz de Incidência� Para todo grafo G existe uma matriz |V|×|A|chamada matriz de incidência

� Seja V = {v1,v2,...,vn} e A = {a1,a2,...,am}

� A matriz de incidência de G é a matriz M(G) =[mij], sendo mij o número de vezes (0, 1 ou 2) queo vértice vi e a aresta aj são incidentes

Representação Computacional

2016-I7

� Matriz de Incidência

Representação Computacional

2016-I8

� Matriz de Adjacência� Para todo grafo G existe uma matriz |V|×|V|chamada matriz de adjacência

� Seja V = {v1,v2,...,vn}

� A matriz de adjacência de G é a matriz A(G) =[aij], sendo aij o número de arestas unindo osvértices vi e vj

Representação Computacional

2016-I9

� Matriz de Adjacência

Representação Computacional

2016-I10

� A matriz de adjacência é geralmenteconsideravelmente menor que a matriz deincidência (por que?)

� Por isso a de adjacência é mais usada que a deincidência para armazenar grafos em computadores

Representação Computacional

2016-I11

� Lista de Adjacência� Simples� Lista de listas de vértices� Cada lista: formada por um vértice e seusadjacentes� Adequada na representação de grafos esparsos� Ineficiente na busca de uma aresta no grafo� A lista associada a um vértice pode ser vazia.� Em grafos não orientados, pode-se evitar arepetição na representação de arestas adotando-se algum critério de ordenação

Representação Computacional

2016-I12

� Lista de Adjacência

1

2 3

4

1 2 4 •

1

2 4

1 3

3 •

4 •

3 •

2

1

3

4

Representação Computacional

2016-I13

Matriz deIncidências

Matriz de Adjacências

Lista de Adjacências

Uso Memória O(nm) O(n2) O(n+m)

Procurar todos os vértices

adjacentes deum vértice v

O(nm) O(n) O(grau(v))

Verificar se dois vértices u e v são

adjacentesO(m) O(1) O(grau(u))

Visitar todas as arestas O(nm) O(n2) O(m)

Calcular o grau de um vértice u O(m) O(n) O(grau(u))

Note que para grafos completos, a estrutura mais eficiente é matriz deadjacências. Para grafos esparsos, a estrutura de listas de adjacências émais eficiente.

Representação Computacional

Código-fonte do Livro

2016-I14

� Representação através de vetorNúmero Máximo de Vértices e Número Máximo de grauMatriz de Adjacencias e Vetor de Grau’sNúmero de Arestas e Número de Vértices

� Grafo DirecionadoA aresta (x,y) será inserida colocando y na lista de

adjacências de x

� Leitura de um Grafo

� Inserindo Aresta

Busca em Profundidade

2016-I15

� Complexidade:

� Se o grafo tem mais arestas que vértices acomplexidade de tempo será O(m)� Caso contrário, temos a complexidade O(n)

Busca em Largura

2016-I16

� Para cada vértice do grafo visitam-se os vérticesadjacentes sempre que possível

� A Busca em Largura está intimamenterelacionada com o conceito de distância entrevértices. Quando aplicada a uma árvore, a buscafaz uma varredura “por níveis”

� Principal diferença entre Busca em Profundidadee Busca em Largura:� Busca em Profundidade usa Pilha (administrada pela recursão)� Busca em Largura usa Fila

Diferenças

2016-I17

� Outras diferenças entre os dois algoritmos debusca:� Na BP o próprio algoritmo escolhe o vértice inicial,enquanto que na BL o vértice inicial é escolhido pelousuário� A BP visita todos os vértices do grafo, enquanto que a BLvisita apenas os vértices que podem ser atingidos pelovértice inicial� BP é, usualmente, recursivo, enquanto a BL é iterativo

� A BP e BL são diferentes e tem aplicações muitodiferentes

Busca em Largura

2016-I18

� Exemplo

� Ordem de visita dos vértices: 1,2,3,4,5,6,7,8,9,10,11,13,12

2016-I19

� Na Busca em Largura define-se uma fila F paraarmazenar os vértices adjacentes de um vértice jávisitado

� Usamos as seguintes operações de fila� F.InitFila(); //Inicializa a fila� F. FilaVazia();//Retorna true se a fila está vazia e false caso contrário� F.InsereNaFila(v);//Insere vértive v na fila� F.RemoveDaFila();//Retorna o vértive removido da fila

Algoritmo BL

Algoritmo BL

2016-I20

BLargura (G, v, Visit[]){

Fila F;cont � 0;Para cada vértice u do grafo faça

Visit[u] � -1;Visit[v] � ++cont;F.InitFila();F.InsereNaFila(v);Escreva(v);

Enquanto !F.FilaVazia() faça{

x � F.RemoveDaFila();Para cada vértice y adjacente a x

façaSe Visit[y] == -1 então{

F.InsereNaFila(y);Visit[y] � ++cont;Escreva(y);

}}

}

2016-I21

� Complexidade:

�Em relação ao tempo de execução a BL possui amesma complexidade que a BP.� Porém, em termos de memória, o desempenhoda BL é pior.

Busca em Largura

2016-I22

� Determinar o número de componentes conexasde um grafo

� Determinar um caminho entre dois vértices

� Determinar um ciclo de um grafo

� Determinar as pontes de um grafo

� Determinar as articulações de um grafo

� Determinar se um grafo é bipartido

Aplicações dos Algoritmos

2016-I23

� Determinar o número de componentes conexasde um grafo

�Além de contar o número de componentes dografo, o algoritmo deve atribuir um rótulo Visit[v] acada vértice v de tal modo que dois vérticestenham o mesmo rótulo se e somente se estão namesma componente.

Aplicações dos Algoritmos

2016-I24

BProfundidade (G){

cont � 0;Para cada vértice v do grafo faça

Visit[v] � -1;Para cada vértice v do grafo faça

Se Visit[v] == -1 então {cont++;

BP(G, v, Visit, cont);}

retorne cont;}BP (G, v, Visit[], &cont){

Visit[v] � cont;Para cada vértice u adjacente a v faça

Se Visit[u] == -1 entãoBP(G, u, Visit, cont);

}

Aplicações dos Algoritmos

2016-I25

� Exemplo

Aplicações dos Algoritmos

2016-I26

� Para este grafo, o algoritmo retorna 2 (númerode componentes do grafo)

� No início do algoritmo, o vetor Visit

� No fim do algoritmo, o vetor Visit

� Os vértices 0, 1, 5 e 6 estão na componente 1;os vértices 2, 3 e 4 estão na componente 2

Aplicações dos Algoritmos

-1 -1 -1 -1 -1 -1 -1

0 1 2 3 4 5 6

1 1 2 2 2 1 1

0 1 2 3 4 5 6

Código-fonte do Livro

2016-I27

� Encontrando Caminhos (somente no livro)

� Componentes Conexas

� Encontrando Ciclos

2016-I28

� DefiniçãoUm DAG (directed acyclic graph) é um grafodirigido sem ciclos direcionados� Cuidado! Não é necessariamente árvore nemconectado

Ordenação Topológica

2016-I29

� DefiniçãoUma ordenação topológica de um DAG é umasequência de vértices tal que não exista arco de umvértice a algum anterior na sequência� Busca em profundidade pode ser adaptada

Ordenação Topológica

2016-I30

� Construir a ordenação topológica s1s2...sn do DAG� Algoritmopara i = 1...n

si � algum vértice comD � D - v

Ordenação Topológica

Dv ∈ 0)( =−

vδ

2016-I31

� Construir a ordenação topológica s1s2...sn do DAG� Algoritmopara i = 1...n

si �algum vértice comD � D - v

� Note que só funciona em DAG� Se houver ciclo direcionado, faltará v com

Ordenação Topológica

Dv ∈ 0)( =−

vδ

0)( =−

vδ

2016-I32

� Construir a ordenação topológica s1s2...sn de umdígrafo� Algoritmopara i = 1...n

se não há vértice comErro! Não é DAG; break;si � algum vértice comD � D - v

Ordenação Topológica

Dv ∈ 0)( =−

vδ

Dv ∈ 0)( =−

vδ

Exercícios

2016-I33

• Bicoloring

• Playing With Wheels

• Slash Maze

• Hanoi Tower Troubles Again!

• The Tourist Guide

2016-I

Grafos

COM11087-Tópicos Especiais em Programação IIedmar.kampke@ufes.br