Estruturas de Dados - Grafos (Parte 1)

Prévia do material em texto

Grafos
Estruturas de Dados
Profa. Carla Koike
   
Grafo
● Um grafo é constituído de um conjunto de 
vértices (ou nós) e um conjunto de arestas (ou 
arcos) conectando pares de vértices
● Um vértice é um objeto simples que pode ter 
nome e outros atributos
● Grafos são estruturas de dados bastantes 
genéricas, englobando todas as estruturas 
vistas anteriormente
   
Definindo um Grafo
N = {A,B,C,D,E,F} : Conjunto de vértices ou nós do Grafo
A = {(A,B);(B,A);(B,C);(B,D);(C,C);(D,A);(D,C);(E,F)} : Conjunto 
     de Arestas ou Arcos
A FEDCB
   
Definindo um Grafo
N = {A,B,C,D,E,F} : Conjunto de vértices ou nós do Grafo
A = {(A,B);(B,A);(B,C);(B,D);(C,C);(D,A);(D,C);(E,F)} : Conjunto 
     de Arestas ou Arcos
A F
E
D
C
B
   
Aplicações de Grafos
● Nós são cidades e arcos são estradas: os grafos 
auxiliam a traçar os caminhos e descobrir o caminho 
mais curto (ou mais longo) entre cidades
● Nós são terminais de dispositivos eletrônicos e arcos 
representam as conexões entre esses terminais
● Nós são tarefas em um projeto e arcos representam 
as dependências entre as tarefas
   
História dos 
Computadores
   
Rede de Computadores
Molécula Química
   
Conceitos e Definições
● Grafo direcionado: as arestas ou arcos são 
direcionados. A conexão (A,B) é diferente da 
conexão (B,A).
● Grafo não direcionado:  as arestas ou arcos 
não possuem direção e (A,B) é igual a (B,A). 
Self­loops (C,C) não são permitidos. 
   
Grafo Direcionado
A F
E
D
C
B
   
Grafo Não­direcionado
A F
E
D
C
B
   
Conceitos e Definições
● Vértices ou nós adjacentes: são nós ligados por 
um arco. Adjacência não é simétrica em grafos 
direcionados.
● Arco incidente: é um arco direcionado 
chegando em um nó. Ex. Arco incidente em D 
(C,D)
   
Conceitos e Definições
● Grau do nó v: número de arcos incidentes a v  
(nós adjacentes)
● Caminho: seqüência de arcos levando de um 
vértice a outro. O caminho entre nó C e nó A é 
{(C,B);(B,A)}
   
Conceitos e Definições
● Alcançável: um vértice x é alcançável a partir 
do vértice y se existe um caminho a partir de y 
até x
● Circuito: caminho que leva de um vértice a ele 
mesmo. {(B,D);(D,A);(A,B)}
● Laço: circuito de um único arco. {(C,C)}
● Grafo acíclico: é um grafo que não possui 
circuito
   
Conceitos e Definições
● Subgrafo: grafo formando por um subconjunto 
de vértices de outro grafo, contendo todos os 
arcos cujas extremidades são os vértices neste 
subconjunto 
● Grafo parcial: contém todos os nós de outro 
grafo mas apenas um subconjunto de seus 
arcos
   
Grafo
N = {A,B,C,D,E,F} 
A = {(A,B);(B,A);(B,C);(B,D);(C,C);(D,A);(D,C);(E,F)} 
A F
E
D
C
B
   
Subgrafo
N = {A,B,D} 
A = {(A,B);(B,A);(B,D);(D,A)} 
A D
B
   
Grafo parcial
N = {A,B,C,D,E,F} 
A = {(B,A);(B,C);(B,D);(E,F)} 
A F
E
D
C
B
   
Conceitos e Definições
● Grafo Conexo: grafo que possui pelo menos um 
nó a partir de qual existem caminhos para 
todos os outros nós
● Grafo fortemente Conexo: para todos os nós 
existem caminhos a partir de todos os outros 
nós
● Grafo valorado ou ponderado: os arcos 
possuem valores ou pesos associados
   
Grafos Conexos
   
Grafos Fortemente Conexos
   
TAD Grafo
● Estrutura composta de nós e arcos
● Operações possíveis:
– Cria grafo, contendo N nós 
– Inserir arco, com ou sem peso
– Obter lista de arcos adjacentes a um nó
– Retirar arco
– Obter caminho entre dois nós
– ...
   
Implementações TAD Grafo 1
● Por meio de matriz de adjacência
– cada posição na matriz é um arco
– linha indica o nó de saída do arco
– coluna indica o nó de chegada
– valor da posição indica a existência (true) ou não 
(false) do arco
– o valor da posição pode também indicar o peso 
associado ao arco
   
Matriz de Adjacência
   
Matriz de Adjacência
● Deve ser utilizada para grafos densos, onde o número de 
arcos |A| é próximo do número de vértices ao quadrado     
|V|2 
● O tempo necessário para acessar um elemento é 
independente de |V | ou |A|.
● É muito útil para algoritmos em que necessitamos saber 
com rapidez se existe uma aresta ligando dois vértices.
● A maior desvantagem é que a matriz necessita  (|V|Ω 2 ) de 
espaço. Ler ou examinar  a matriz tem complexidade de 
tempo O(|V|2 ).
   
Implementações TAD Grafo 2
● Lista de adjacência
● Lista encadeada dos nós presentes no grafo
● Cada elemento da lista acima possui um dos 
nós da lista
– Este elemento aponta para outra lista, dessa vez 
dos arcos saindo desse nó
– Cada elemento da lista de arcos aponta para o nó 
de chegada na lista de nós
   
Lista de Adjacência
   
Lista de Adjacência
● Os vértices de uma lista de adjacência são em geral 
armazenados em uma ordem arbitrária.
● Possui uma complexidade de espaço O(|V|+|A|)
● Indicada para grafos esparsos, onde |A| é muito menor do 
que |V|2 .
● É compacta e usualmente utilizada na maioria das 
aplicações.
● Tempo O(|V|) para determinar se existe uma aresta entre 
o vértice i e o vértice j, pois podem existir O(|V|) vértices 
na lista de adjacentes do vértice i.
   
Lista de Adjacência
Elemento da
Lista de Vértices
Elemento da
Lista de Arcos
   
Lista de Adjacência
struct adj_node  {
char vertex_val;
struct adj_node *adj_next; 
};
struct node{
char vertex_val;
struct adj_node *down;
struct node *next;  
};
   
Busca em Profundidade
● A busca em profundidade (depth­first search), é um algoritmo 
para caminhar no grafo.
● A estratégia é buscar o mais profundo no grafo sempre que 
possível.
● Os arcos são exploradas a partir do vértice v mais 
recentemente descoberto que ainda possui arestas não 
exploradas saindo dele.
● Quando todas as arestas adjacentes a v tiverem sido 
exploradas a busca anda para trás para explorar vértices que 
saem do vértice do qual v foi descoberto.
   
Busca em Profundidade ­ Ex
   
Busca em Profundidade Algoritmo
● enquanto a pilha não está vazia faça
– seja  v  o vértice no topo da pilha
– se A(v) (arcos de v) não está vazio
– então retire um arco (v,w) de A(v)
● se w não está marcado
● então então marque w
● coloque w na lista (árvore) de arcos visitados
– senão retire v do topo da pilha 
   
Busca em Profundidade Algoritmo
    dfs(vertex v)
    {
    visit(v);
    for each neighbor w of v
        if w is unvisited
        {
        dfs(w);
        add edge vw to tree T
        }
    }
   
Busca em Largura
● Expande a fronteira entre vértices descobertos 
e não descobertos uniformemente através da 
largura da fronteira.
● O algoritmo descobre todos os vértices a uma 
distância k do vértice origem antes de descobrir 
qualquer vértice a uma distância k + 1.
● O grafo G(V, A) pode ser direcionado ou não 
direcionado.
   
Busca em Largura
   
Busca em Largura ­ Ex.
   
Busca em Largura ­ Ex.
   
Busca em Largura ­ Algoritmo
1. Coloca o nó raiz na fila.
2.Retira um nó do início da fila e examina­o.
3.Se o elemento procurado está nesse nó, interrompe a 
busca e retorna o resultado.
4.Senão, coloca todos os sucessores desse nó, ainda não 
examinados, no final da lista.
5.Se a fila está vazia, cada nó no grafo já foi examinado: 
interrompe a busca e retorna “não encontrado”.
6.Repete passo 2
   
Análise de Complexidade
● Complexidade temporal de ambos os 
algoritmos de busca é O(Nv * Na), onde Nv é o 
número de vértices e Na é o número de arcos 
no grafo.
● Complexidade espacial DFS é O(h), onde h é o 
comprimento do mais longo caminho no grafo
● Complexidade espacial BFS é O(Nv* Na)
   
BFS X DFS
● A busca em largura é completa apenas se a árvore pesquisada 
tem um número finito de ramos 
● A busca em largura é ótima se o custo dos passos forem 
idênticos – o algoritmo encontrará a solução mais “rasa” de 
uma árvore de busca, não necessariamente a melhor. No caso 
em que os passos possuem custos diferentes, a solução mais 
“rasa” não é necessariamente a melhor.
● DFS é aplicado em vários algoritmos de ordenação em grafos 
como:
– ordenamento topológico
– encontrar componentes fortemente conectados
   
 Problema dos canibais e dos 
missionários
● http://www.inf.ufsc.br/grafos/temas/travessia/canibais­todos.htm
● www.plastelina.net/games/games3.html