07.Grafos - Aula sobre Grafos

Prévia do material em texto

Aula 07
Grafos
Rodolfo Carneiro Cavalcante
Universidade Federal de Alagoas – UFAL
Campus Arapiraca
5 de Novembro de 2015
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 1 / 79
Suma´rio
1 Introduc¸a˜o
2 Terminologia
3 Implementando um grafo
4 Percurso em Grafos
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 2 / 79
Suma´rio
Aulas anteriores...
Ja´ estudamos estruturas de dados lineares
Pilhas, filas, listas
Estudamos uma estrutura de dados na˜o linear onde cada elemento
pode ter mais de um sucessor
a´rvore
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 3 / 79
Suma´rio
Aulas anteriores...
A´rvores
Cada no´ tem apenas um predecessor, mas possui va´rios sucessores
E´ desenhada de cima para baixo, da raiz para as folhas
Apresentam uma estrutura hiera´rquica
Sa˜o estruturas de dados recursivas
Muitas func¸o˜es para manipulac¸a˜o de a´rvores sa˜o definidas como
func¸o˜es recursivas
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 4 / 79
Suma´rio
Terminologia
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 5 / 79
Introduc¸a˜o
Suma´rio
1 Introduc¸a˜o
2 Terminologia
3 Implementando um grafo
4 Percurso em Grafos
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 6 / 79
Introduc¸a˜o
Introduc¸a˜o
Limitac¸a˜o das a´rvores: cada item possui apenas um pai
Algumas aplicac¸o˜es demandam por uma estrutura sem essa limitac¸a˜o
Ou seja, um no´ pode ter va´rios antecessores e va´rios sucessores
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 7 / 79
Introduc¸a˜o
Introduc¸a˜o
Pre´-requisitos entre disciplinas
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 8 / 79
Introduc¸a˜o
Introduc¸a˜o
Representac¸a˜o uma rede de computadores
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 9 / 79
Introduc¸a˜o
Introduc¸a˜o
Redes Sociais
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 10 / 79
Introduc¸a˜o
Introduc¸a˜o
Roteamento de ve´ıculos entre cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 11 / 79
Introduc¸a˜o
Introduc¸a˜o
Caminho de menor custo entre duas cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 12 / 79
Introduc¸a˜o
Introduc¸a˜o
Caminho de menor custo entre duas cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 13 / 79
Introduc¸a˜o
Introduc¸a˜o
Caminho de menor custo entre duas cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 14 / 79
Introduc¸a˜o
Introduc¸a˜o
Caminho de menor custo entre duas cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 15 / 79
Introduc¸a˜o
Introduc¸a˜o
Caminho de menor custo entre duas cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 16 / 79
Introduc¸a˜o
Introduc¸a˜o
Caminho de menor custo entre duas cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 17 / 79
Introduc¸a˜o
Introduc¸a˜o
Caminho de menor custo entre duas cidades
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 18 / 79
Introduc¸a˜o
Introduc¸a˜o
Grafos e algoritmos de grafos sa˜o estudados muito antes dos
computadores serem inventados
Grafos sa˜o uteis na ana´lise de redes
Inicialmente para o sistema telefoˆnico
Hoje: Internet, mapa rodovia´rio, projeto de chips de computadores
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 19 / 79
Terminologia
Suma´rio
1 Introduc¸a˜o
2 Terminologia
3 Implementando um grafo
4 Percurso em Grafos
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 20 / 79
Terminologia
Terminologia
Grafo – estrutura de dados que consiste em dois objetos especiais
Ve´rtices – no´s do grafo
Arestas – caminhos, conexo˜es ou ligac¸o˜es entre os ve´rtices
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 21 / 79
Terminologia
Terminologia
Formalmente, um grafo G consiste de dois conjuntos finitos:
1 Ve´rtices V (G)
2 Arestas E (G)
Tipicamente, um grafo G e´ representado como G = (V ,E )
Cada aresta esta´ associada a um conjunto de um ou dois ve´rtices
Um lac¸o ou loop e´ uma aresta que conecta somente um no´ terminal
Dois ve´rtices que sa˜o conectados por uma aresta sa˜o ditos adjacentes
Uma aresta e´ dita ser incidente a cada um de seus no´s terminais
Um ve´rtice que na˜o possui nenhuma aresta incidente e´ chamado de
isolado
Arestas paralelas sa˜o arestas associadas ao mesmo conjunto de
ve´rtices
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 22 / 79
Terminologia
Terminologia
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 23 / 79
Terminologia
Terminologia
V = {v1, v2, v3, v4, v5, v6}
E = {e1, e2, e3, e4, e5, e6, e7}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 24 / 79
Terminologia
Terminologia
E´ importante notar que o desenho f´ısico do grafo na˜o e´ importante
Veja os grafos a seguir
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 25 / 79
Terminologia
Terminologia
Identificando os ve´rtices e arestas
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 26 / 79
Terminologia
Terminologia
Modelos usando grafos
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 27 / 79
Terminologia
Terminologia
Grafo simples – grafo que na˜o possui lac¸os nem arestas paralelas
Grafo orientado
tambe´m chamado de dirigido ou direcionado ou d´ıgrafo
arestas possuem um sentido
aplicac¸a˜o: ruas de ma˜o u´nica
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 28 / 79
Terminologia
Terminologia
Grafo ponderado
aresta possuem valores associados
valores sa˜o chamados de pesos
aplicac¸a˜o: distaˆncia entre cidades, custo de repasse em links de rede,
etc
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 29 / 79
Terminologia
Terminologia
Grafo completo
cada ve´rtice do grafo esta´ conectado com todos os outros
ou seja, ha´ uma aresta para cada par de ve´rtices distinto
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 30 / 79
Terminologia
Terminologia
Grafos e a´rvores
Podemos perceber que uma a´rvore e´ um tipo especial de grafo
Que tipo de grafo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 31 / 79
Terminologia
Terminologia
Grafos e a´rvores
Podemos perceber que uma a´rvore e´ um tipo especial de grafo
Que tipo de grafo?
Um grafo direcionado, conexo e ac´ıclico
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 32 / 79
Implementando um grafo
Suma´rio
1 Introduc¸a˜o
2 Terminologia
3 Implementando um grafo
4 Percurso em Grafos
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 33 / 79
Implementando um grafo
Implementac¸a˜o
Um grafo e´ um tipo abstrato de dados
Va´rias operac¸o˜es sa˜o definidas sobre esse TAD
Criar um grafo vazio
Inserir uma aresta no grafo
Verificar se existe uma aresta no grafo
Obter lista de ve´rtices adjacentes a determinado ve´rtice
Retirar uma aresta do grafo
Imprimir um grafo
Obter nu´mero de ve´rtices do grafo
...
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 34 / 79
Implementando um grafo
Implementac¸a˜o
Existem va´rias representac¸o˜es para implementac¸a˜o de grafos
As duas formas mais utilizadas sa˜o amatriz de adjaceˆncia e a lista de
adjaceˆncia
Estas sera˜o as formas vistas nesta disciplina
Em uma a´rvore, representa´vamos os filhos de um no´
A ideia das listas e matrizes de adjaceˆncia e´ representar os todos os
no´s adjacentes a um determinado no´
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 35 / 79
Implementando um grafo
Implementac¸a˜o
Matriz de Adjaceˆncia
Seja G = (V ,E ) um grafo com ve´rtices v1, v2, ..., vn
A matriz de adjaceˆncia de G e´ uma matriz An×n
Matriz bina´ria
uma posic¸a˜o A[i , j] tem valor 1 se existe um arco do ve´rtice i para o
ve´rtice j , ou 0, caso contra´rio
Para grafos ponderados, A[i , j] tem o valor do peso do arco que liga o
ve´rtice i ao ve´rtice j , ou 0, se na˜o ha´ ligac¸a˜o
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 36 / 79
Implementando um grafo
Implementac¸a˜o
Matriz de Adjaceˆncia
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 37 / 79
Implementando um grafo
Implementac¸a˜o
Matriz de Adjaceˆncia
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 38 / 79
Implementando um grafo
Implementac¸a˜o
Matriz de Adjaceˆncia
Como implementar um grafo utilizando matriz de adjaceˆncia?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 39 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 1: Grafo com matriz de adjaceˆncia
class Grafo{
public:
int** mat adj;
int numVertices;
Grafo(int NumVertices);
void insereAresta(int v1, int v2);
bool existeAresta(int v1, int v2);
bool vazio();
void retiraAresta(int v1, int v2);
void imprime();
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 40 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
A estrutura de dados utilizada por essa implementac¸a˜o e´ uma matriz
“mat adj”
Que sera´ inicializada dinamicamente no construtor da classe
Essa matriz ira´ guardar as informac¸o˜es das arestas existentes no grafo
O co´digo anterior mostrou tambe´m as assinaturas dos me´todos
implementados
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 41 / 79
Implementando um grafo
Implementac¸a˜o
Matriz de Adjaceˆncia
O que precisamos implementar para inicializar o grafo (o construtor)?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 42 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 2: Grafo com matriz de adjaceˆncia: construtor
Grafo::Grafo(int numVertices){
this->numVertices = NumVertices;
this->mat adj = new int*[numVertices];
for ( int i = 0; i < numVertices ; i ++)
this->mat adj[i] = new int[numVertices];
for(int i = 0; i< this->numVertices; i++)
for(int j = 0; j< this->numVertices; j++)
this->mat adj[i][j] = 0;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 43 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
O construtor inicializa a varia´vel “numVertices”
Em seguida, utiliza esse paraˆmetro para inicializar dinamicamente a
matriz de adjaceˆncia
Por fim, e´ preciso sinalizar que o grafo e´ vazio, colocando 0 nas
posic¸o˜es da matriz
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 44 / 79
Implementando um grafo
Implementac¸a˜o
Matriz de Adjaceˆncia
Como inserir uma aresta no grafo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 45 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 3: Grafo com matriz de adjaceˆncia: inserir aresta
void Grafo::insereAresta(int v1, int v2){
this->mat adj[v1][v2] = 1;
this->mat adj[v2][v1] = 1;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 46 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Para inserir uma aresta entre dois ve´rtices vi e vj , basta sinalizar
A[i , j] = 1
Se o grafo e´ na˜o-direcionado, enta˜o e´ necessa´rio fazer A[j , i ] = 1, pois
ha´ simetria
Se o grafo for ponderado, e´ preciso receber o peso da aresta durante a
inserc¸a˜o
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 47 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 4: Grafo com matriz de adjaceˆncia: inserir aresta
void Grafo::insereAresta(int v1, int v2, int peso){
this->mat adj[v1][v2] = peso;
this->mat adj[v2][v1] = peso;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 48 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 5: Grafo com matriz de adjaceˆncia: retirar aresta
void Grafo::retiraAresta(int v1, int v2){
this->mat adj[v1][v2] = 0;
this->mat adj[v2][v1] = 0;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 49 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Como verificar se existe uma aresta entre dois ve´rtices do grafo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 50 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 6: Grafo com matriz de adjaceˆncia: existe aresta?
bool Grafo::existeAresta(int v1, int v2){
return (this->mat adj[v1][v2]!=0);
}
Para verificar se existe uma aresta entre vi e vj , basta verificar se
A[i , j]! = 0
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 51 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Como verificar se o grafo esta´ vazio?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 52 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 7: Grafo com matriz de adjaceˆncia: verificar se esta vazio
bool Grafo::vazio(){
for(int i = 0; i< this->numVertices; i++)
for(int j = 0; j< this->numVertices; j++)
if (this->mat adj[i][j] != 0)
return false;
return true;
}
Para verificar se o grafo esta´ vazio, e´ preciso percorrer toda a matriz e
verifica se ha´ alguma aresta
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 53 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Como imprimir as arestas do grafo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 54 / 79
Implementando um grafo
Implementac¸a˜o com Matriz de Adjaceˆncia
Algoritmo 8: Grafo com matriz de adjaceˆncia: imprimir arestas
void Grafo::imprime(){
for(int i = 0; i< this->numVertices; i++){
cout<<i<<“-> ”;
for(int j = 0; j< this->numVertices; j++)
if (this->mat adj[i][j] != 0)
cout<<j<<“ ”;
cout<<endl;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 55 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
A representac¸a˜o de um grafo G = (V ,A) por lista de adjaceˆncia
consiste em utilizar uma lista de adjaceˆncia para cada no´ do grafo
Para cada u ∈ V , a lista de adjaceˆncia adj[u] conte´m todos os
ve´rtices v adjacentes a u
A lista de adjaceˆncia de cada ve´rtices pode ser implementada
utilizando arranjos ou estruturas auto-referenciadas
Vamos ver a implementac¸a˜o com estruturas auto-referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 56 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
Algoritmo 9: Grafo com lista de adjaceˆncia
class Grafo{
public:
Lista Enc<int> *listas adj;
int numVertices;
Grafo(int numVertices);
void insereAresta(int v1, int v2);
bool existeAresta(int v1, int v2);
bool vazio();
void retiraAresta(int v1, int v2);
void imprime();
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 57 / 79
Implementandoum grafo
Implementac¸a˜o com Lista de Adjaceˆncia
A definic¸a˜o da classe e´ praticamente a mesma
A diferenc¸a e´ que temos uma lista de adjaceˆncia para cada ve´rtice do
grafo
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 58 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
Algoritmo 10: Grafo com lista de adjaceˆncia: construtor da classe
Grafo::Grafo(int NumVertices){
this->numVertices = NumVertices;
this->listas adj = new Lista Enc<int>[this->numVertices];
}
Inicializa a varia´vel que conta o nu´mero de ve´rtices
Inicializa as listas de adjaceˆncia dos ve´rtices
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 59 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
Algoritmo 11: Grafo com lista de adjaceˆncia: adicionar aresta
void Grafo::insereAresta(int v1, int v2){
this->listas adj[v1].insere(v2);
this->listas adj[v2].insere(v1);
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 60 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
Algoritmo 12: Grafo com lista de adjaceˆncia: inserir aresta
void Grafo::retiraAresta(int v1, int v2){
this->listas adj[v1].retiraItem(v2);
this->listas adj[v2].retiraItem(v1);
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 61 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
Algoritmo 13: Grafo com lista de adjaceˆncia: verificar se existe aresta
bool Grafo::existeAresta(int v1, int v2){
return (this->listas adj[v1].pesquisa(v2)!=NULL);
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 62 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
Algoritmo 14: Grafo com lista de adjaceˆncia: verificar se esta´ vazio
bool Grafo::vazio(){
for(int vi = 0; vi¡this->numVertices;vi++)
if(!this->listas adj[vi].vazia())
return false;
return true;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 63 / 79
Implementando um grafo
Implementac¸a˜o com Lista de Adjaceˆncia
Algoritmo 15: Grafo com lista de adjaceˆncia: imprimir
void Grafo::imprime(){
for(int vi = 0; vi<numVertices;vi++){
cout<<vi<<“->”;
this->listas adj[vi].imprime();
cout<<endl;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 64 / 79
Implementando um grafo
Implementac¸a˜o
Considerac¸o˜es
Qual a implementac¸a˜o mais adequada:
matriz ou lista?
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 65 / 79
Implementando um grafo
Implementac¸a˜o
Considerac¸o˜es
Depende!
O uso de matrizes e´ mais adequado para grafos densos: muitas
arestas
como o grafo possui muitas arestas, enta˜o a matriz fica quase
completamente preenchida
na˜o ha´ desperd´ıcio de espac¸o
Uma vantagem desse tipo de implementac¸a˜o e´ o tempo de acesso a
uma aresta
esse tempo de acesso e´ constante
independe do nu´mero de ve´rtices no grafo
Ideal para aplicac¸o˜es que precisam testar a existeˆncia de arestas com
frequeˆncia
A maior desvantagem do uso de matrizes e´ que elas precisam de V 2
de espac¸o
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 66 / 79
Implementando um grafo
Implementac¸a˜o
Considerac¸o˜es
A implementac¸a˜o com listas de adjaceˆncia e´ ideal para grafos esparsos
possuem muito menos arestas do que ve´rtices
Usar uma matriz nestes casos causa desperd´ıcio de espac¸o
A maior desvantagem desse tipo de implementac¸a˜o e´ o custo de
acesso a uma aresta
e´ preciso buscar na lista de um ve´rtice se ha´ a adjaceˆncia
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 67 / 79
Percurso em Grafos
Suma´rio
1 Introduc¸a˜o
2 Terminologia
3 Implementando um grafo
4 Percurso em Grafos
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 68 / 79
Percurso em Grafos
Percurso em Grafos
O objetivo do percurso em grafos e´ percorrer sistematicamente cada
aresta e ve´rtice de um grafo
Va´rias aplicac¸o˜es na computac¸a˜o:
Computac¸a˜o gra´fica
Verificac¸a˜o formal
Compiladores
Resoluc¸a˜o de problemas
Inteligeˆncia Artificial
Vamos utilizar a implementac¸a˜o com lista de adjaceˆncia
Dois tipos de algoritmos de percurso em grafos muito utilizados:
busca em largura
busca em profundidade
Nesta disciplina, estudaremos apenas a busca em largura
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 69 / 79
Percurso em Grafos
Busca em Largura
Inicia o percurso a partir de um ve´rtice s
Produz uma a´rvore com raiz s e seus ve´rtices alcanc¸a´veis
Se v e´ um ve´rtice alcanc¸a´vel a partir de s, enta˜o o caminho entre s e
v na a´rvore corresponde ao caminho mais curto entre s e v no grafo
Estruturas de dados necessa´rias para implementac¸a˜o
vetor cor[n]: cada ve´rtice do grafo vai estar associado a uma cor
vetor dist[n]: distaˆncia de cada ve´rtice do grafo ao ve´rtice de partida
da busca s
uma estrutura de dados fila
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 70 / 79
Percurso em Grafos
Busca em Largura
Algoritmo 16: Busca em Largura
buscaLargura(s){
para cada vertice u do grafo{
cor[u] ← branco;
dist[u] ←∞;
}
cor[s] ← cinza;
dist[s] ← 0;
fila.enfileira(s);
...
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 71 / 79
Percurso em Grafos
Busca em Largura
Algoritmo 17: Busca em Largura
buscaLargura(s){
...
enquanto(!fila.vazia()){
u ← fila.desenfileira();
para cada vertice v ∈ listas adj[u]{
se (cor[v ] == branco){
cor[v ] ← cinza;
dist[v ] ← dist[u] + 1;
fila.enfileira(v);
}
}
cor[u] ← preto;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 72 / 79
Percurso em Grafos
Busca em Largura
As cores sa˜o utilizadas para auxiliar o algoritmo na expansa˜o de
ve´rtices
branco – o ve´rtice esta´ sendo visto pela primeira vez
cinza – o ve´rtice ja´ foi visto, mas na˜o foi expandido
preto – o ve´rtice ja´ foi visto e expandido
O primeiro lac¸o do algoritmo faz as inicializac¸o˜es de cor, distaˆncia e
antecedeˆncia de cada ve´rtice
Em seguida, faz as atribuic¸o˜es para o ve´rtice inicial da busca
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 73 / 79
Percurso em Grafos
Busca em Largura
o lac¸o “enquanto”, faz a expansa˜o de todos os ve´rtices do grafo
a cada iterac¸a˜o, o ve´rtice u que esta´ na frente da fila e´ recuperado
para expansa˜o
todos os ve´rtices v adjacentes a u ainda na˜o expandidos sa˜o
marcados como cinza, tem sua distaˆncia e seu antecedente
atualizados e sa˜o enfileirados para posterior expansa˜o
por fim, quanto todos os adjacentes de u sa˜o examinados, u e´
marcado como ja´ visitado e expandido (cor preta)
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 74 / 79
Percurso em Grafos
Busca em Profundidade
Inicia o percurso a partir de um ve´rtice s
Tambe´m produz uma a´rvore com raiz s e seus ve´rtices alcanc¸a´veis
Explora recursivamente os ve´rtices do grafo a partir de arestas na˜o
exploradas ainda, mais fundo no grafo quanto poss´ıvel
Processo continua ate´ que todos os ve´rtices alcanc¸a´veis a partir da
origem tenham sido descobertos
Estruturas de dados necessa´rias para implementac¸a˜o
vetor cor[n]: cada ve´rtice do grafo vai estar associada a uma cor
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 75 / 79
Percurso em Grafos
Busca em Profundidade
Algoritmo 18: Busca em Profundidade: inicializac¸a˜o
buscaProfundidade(s){
para cada vertice u do grafo{
cor[u] ← branco;
}
visite(s);
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 76 / 79
Percurso em GrafosBusca em Profundidade
Algoritmo 19: Busca em Profundidade: passo recursivo
visite(u){
cor[u] ← cinza;
para cada vertice v ∈ listas adj[u]{
se (cor[v ]) == branco
visite(v);
}
cor[u] ← preto;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 77 / 79
Percurso em Grafos
Busca em Profundidade
A primeira fase do algoritmo e´ a etapa de inicializac¸a˜o, onde cada
ve´rtice recebe a cor branca
A segunda fase do algoritmo e´ o passo recursivo, onde ocorre a busca
em profundidade efetivamente
Inicialmente o ve´rtice u que esta´ sendo visitado e´ marcado com a cor
cinza
Em seguida, a visita e´ chamada recursivamente para cada ve´rtice
adjacente ao ve´rtice u
Ao final, o ve´rtice u e´ marcado com a cor preta, indicando que a visita
para o ve´rtice esta´ finalizada
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 78 / 79
Percurso em Grafos
Du´vidas
Utilizem o ambiente para tirar du´vidas!
Rodolfo Carneiro Cavalcante (UFAL) Aula 07Grafos 5 de Novembro de 2015 79 / 79
	Introdução
	Terminologia
	Implementando um grafo
	Percurso em Grafos