Grafos
1 - Definições Preliminares
2 - Formas de Representação
3 - Métodos de Passeio (Pesquisa)
4 - Aplicações
Definições preliminares
 Grafos são estruturas de dados largamente utilizadas na Ciência
da Computação, sendo fundamental seu estudo e dos algoritmos
para sua manipulação.
 Exemplos de aplicações:
– Modelagem de circuitos digitais;
– Representação de processos em um sistema paralelo ou distribuído;
– Representação de lista encadeada;
– Árvores de decisão;
– Diagramas E-R;
– Diagrama UML;
– Máquinas de estado finito;
– Derivação de palavras em linguagens formais;
Definições preliminares
Running
1
3
2
I/O
Ready
4
Os três estados que um processo pode
assumir num sistema operacional
Definições preliminares
nome
endereço
cidade
estado
pessoa
1
Um diagrama E-R
possui
n
animal
nome_animal
Tipo_animal
raça
Definições preliminares
Um exemplo de árvore de decisão: if (a > b)
v[i] = f(i);
else
if (b > c)
v[i] = g(i);
Assuma que os valores das expressões booleanas “(a > b)” e “(b >
c)” são independentes e que, na média, ”(a > b)” é executado 25% do
tempo e “(b > c)” 25% do tempo. Se o trecho de programa acima é
executado 10.000 vezes, quantas vezes se espera que as funções f e g
sejam executadas?
a>b
10.000 x 0,25= 2500 vezes
v[i]=f[i]
75.000 x 0,25 = 1875 vezes
v[i]=g[i]
75.000 vezes
b>c
Definições preliminares
Um exemplo de máquina de estado finito
1
0,1
S0
S1
0
1
0
S2
Definições preliminares
Um exemplo de rede neural artificial
Definições preliminares
Um exemplo de diagrama de classes
-possui
Population
EvolutionaryModel
-TargetSolution
1
*
-possui
1
-atua sobre
1..*
1
CrossOver
GeneticOperator
Selection
-gera
-avalia
Chromosome
FitnessScore
-Code
-Propability
+Apply()
*
*
1..*
1
*
+Evaluate()
-gera
Encoder
Mutation
-possui
1
*
Decoder
-decodifica
Gene
-Code
+Decode()
1
*
*
1
+Encode()
Definições preliminares
 Um grafo dirigido G é um par (N, A), onde N é um
conjunto finito e A é uma relação binária entre os
componentes de N. Assim:
– G = (N, A)
– N = conjunto de nós (ou vértices) de G
– A = conjunto de arcos (ou arestas) de G
 Em um grafo não-dirigido G = (N, A), o conjunto
de arcos A consiste de um conjunto desordenado
de pares de nós N.
Definições preliminares
1
2
3
1 - Grafo dirigido G1(N, A):
N = {1,2,3,4,5,6}
G1
4
5
6
A = {(1,2),(2,2),(2,4),(2,5),(4,1),
(4,5),(5,4),(6,3)}
1
2
3
2 - Grafo não-dirigido G2(N,A):
G2
4
5
6
N = {1,2,3,4,5,6}
A = {(1,2),(1,5),(2,5),(3,6)}
Definições preliminares
Relação de Incidência: É definida entre nós e arcos.
1
3 1 - Grafo dirigido G1(N,A):
2
- Os arcos (2,2); (2,4) e (2,5) são
G1
incidentes do nó 2 (saem de 2).
4
6 - Os arcos (1,2) e (2,2) são inciden-
5
tes para o nó 2 (chegam em 2).
1
2
3
G2
2 - Grafo não-dirigido G2(N,A):
- Os arcos incidentes no nó 2
são (1,2) e (2,5).
4
5
6
- O arco (3,6) é incidente nos
nós 3 e 6.
Definições preliminares
Relação de Adjacência:
um arco interligando-os.
1
2
Dois
3
nós
são
adjacentes
se
existe
1 - Grafo dirigido G1(N,A):
- O nó 2 é adjacente ao nó 1.
G1
- O nó 1 não é adjacente ao 2,
4
5
6
pois o arco (2,1)  ao grafo G1.
- O nó 5 é adjacente ao nó 2.
1
2
3
G2
2 - Grafo não-dirigido G2(N,A):
- Relação de adjacência é simétrica.
- O nó 2 é adjacente ao nó 1.
4
5
6
- O nó 1 é adjacente ao nó 2.
Definições preliminares
Grau de um nó: É medido pelo número de arcos incidentes.
1
2
3
1 - Grafo dirigido G1(N,A):
- Grau = Grau Saída + Grau Entrada
G1
4
5
6
- O nó 1 possui grau 2 (1 + 1).
- O nó 2 possui grau 5 (3 + 2).
1
2
3
G2
2 - Grafo não-dirigido G2(N,A):
- O nó 2 possui grau 4.
4
5
6
- O nó 6 possui grau 1.
- O nó 4 possui grau 0.
Definições preliminares
 Um caminho c de um nó u para um nó u’ em um grafo G = (N, A) é a
seqüência de nós <n0, n1, n2, ... nk >, onde u = n0 e u’ = nk, e (ni-1, ni) 
A para i = 1, 2, ..., k.
 O tamanho de c é o número de arcos existentes em c.
 Um caminho c é composto pelos nós n0,n1,n2,... nk e pelos arcos (n0,
n1), (n1, n2), ..., (nk-1, nk).
- Quais os caminhos de 1 para 4 ?
1
2
3
G1
c1 = <1, 2, 5, 4> e c2 = <1, 2, 4>
- Quais os tamanhos de c1 e c2 ?
c1 = 3 e c2 = 2
4
5
6
- Quais são os arcos de c1 ?
<(1,2), (2,5), (5,4)>
Definições preliminares
 Um grafo G = (N, A) possui um ciclo se existir um caminho c = <n0, n1,
... nk >, onde n0 = nk. Se não existir, o grafo é dito acíclico.
 O caminho é simples se <n0, n1, ... nk > são diferentes.
1
2
3
4
5
6
G1
1
2
3
G2
4
5
1 - Grafo dirigido G1(N,A):
- Ciclos de G1:
<1,2,4,1>; <2,4,1,2>; <4,1,2,4>;
<1,2,4,5,4,1> (não simples) e
<2,2> (laço).
6
2 - Grafo não-dirigido G2(N,A):
- Ciclos de G2:
<1,2,5,1>; <2,5,1,2>; <5,1,2,5>
Definições preliminares
Grafos conectados: Um grafo não-dirigido G = (N, A) é
conectado se cada par de nós é conectado por um
caminho.
1
2
3
G2
1 - Grafo não-dirigido G2(N,A)
- Possui três componentes conectados:
4
5
6
{1, 2, 5}, {3, 6} e {4}
Um grafo não-dirigido é conectado se possuir
exatamente um componente conectado, ou seja, se
cada nó é alcançável a partir de cada um dos outros
nós. Logo, o grafo G2 não é conectado.
Definições preliminares
Grafos fortemente conectados: um grafo dirigido G =
(N, A) é fortemente conectado se cada dois nós são
alcançáveis (um a partir do outro).
1
2
3
G1
1 - Grafo dirigido G1(N,A)
- Possui três componentes fortemente
conectados:
4
5
6
{1, 2, 4, 5}, {3} e {6}
• Todos os pares em {1, 2, 4, 5} são mutuamente alcançáveis. Os nós {3, 6}
não formam um componente fortemente conectado, pois não é possível
chegar em 6 a partir de 3.
• Um grafo dirigido é fortemente conectado se possuir exatamente um
componente fortemente conectado. Logo, o grafo G1 não é fortemente
conectado.
Definições preliminares
Um grafo é planar quando este pode ser desenhado (em uma
folha de papel, isto é, em um plano) de forma que suas arestas
se interceptem apenas em vértices.
No século dezoito Leonhard Euler-Matemático suíço
(pronuncia-se “óiler”) observou que um grafo simples, conexo
e planar (sem interseção de arestas) divide o plano em um
número de regiões totalmente fechadas e uma região infinita
exterior. Daí observou uma relação entre o número de n de
vértices, o número a de arestas e o número r de regiões.
É a fórmula de Euler: n - a + r = 2
4-6+4=2
Definições preliminares
Grafos com valores: Quando os nós e/ou os arcos
possuem valores.
Ex.: Distâncias entre localidades.
Rio
890
Vit
2680
580
Spa
1710
1301
Sal
1325
Rec
1210
Nat
450
Formas de representação
 Existem basicamente duas formas para representar um
grafo G = (N, A):
– Por intermédio de uma Lista de Adjacências
É a mais utilizada, pois fornece uma representação mais compacta
de grafos esparsos ( |A| << |N|2 ).
– Por intermédio de uma Matriz de Adjacências
Utilizada quando o grafo é denso ( |A|  |N|2 ), ou quando é
necessário descobrir rapidamente se existe um arco conectando
dois nós pré-definidos.
Formas de representação
 Lista de adjacências para um grafo G = (N, A)
– Consiste em um vetor de |N| listas encadeadas, uma para cada
elemento de N.
– Para cada u  V , a lista de adjacências Adj[u] contém todos os nós v
para os quais existe um arco (u, v)  A.
 Primeiro caso: Grafo Não-Direcionado
1
2
3
5
4
1
2
5 /
2
1
5
3
2
4 /
4
2
5
3 /
5
4
1
2 /
3
4 /
Formas de representação
 Segundo caso: Grafo Direcionado
1
4
2
5
3
6
1
2
2
5 /
3
6
4
2 /
5
4 /
6
6 /
4 /
5 /
Formas de representação
Variável externa G
V0
0
A(0,3)
A(1,2)
A(1,3)
1
V1
3
A(0,1)
2
V2
V3
A(3,1)
A(3,2)
Formas de representação
 Matriz de adjacências para um grafo G = (N, A)
– Assume-se que os nós são numerados da seguinte forma: 1, 2, 3, ..., |N|;
– A matriz de adjacências Adj para um grafo G = (N, A) possui dimensões |N|
x |N| e elementos ai,j , de forma que:
{
1 se (i, j)  A
ai,j =
0 caso contrário
Formas de representação
 Primeiro caso: Grafo Não-Direcionado
1
2
3
5
4
1
2
3
4
5
1 0
2 1
1
0
0
1
0
1
1
1
3 0
1
0
1
0
4 0
1
1
0
1
5 1
1
0
1
0
Tipos:
Adj = vetor[5] [5] de inteiros
 Para os grafos não-direcionados, os elementos da matriz
são simétricos: Adj [ i ] [ j ] = Adj [ j ] [ i ]. Assim, com fins de
economia de memória, pode-se armazenar apenas a matriz
triangular superior ou inferior.
Formas de representação
 Segundo caso: Grafo Direcionado
1
4
2
5
3
6
1
2
3
4
5 6
1 0
2 0
1
0
1
0 0
0
0
0
1 0
3 0
0
0
0
1 1
4 0
1
0
0
0 0
5 0
0
0
1
0 0
6 0
0
0
0
0 1
Tipos
Adj = vetor[6] [6] de inteiros
 Na matriz de adjacências para grafos direcionados, as
linhas representam os nós origem e as colunas, os nós
destino.
Formas de representação
• A matriz de adjacência é freqüentemente inadequada porque requer o
conhecimento prévio do número de nós
• Mesmo que a matriz de adjacência seja esparsa, deve-se reservar
espaço para todo possível arco entre dois nós. Se existir n nós,
precisará de n2 alocações
• Lista ligada é interessante porque só aloca o espaço necessário,
porém, a implementação é mais complexa porque não se pode prever o
número de nós adjacentes a determinado nó, ou seja, o número de
ponteiros é bastante variável
• Na representação de matriz está implícito a possibilidade de percorrer
uma linha ou coluna
• Percorrer em linha é identificar todos os arcos emanando de
determinado nó. Neste caso, a implementação ligada é mais eficiente
• Em coluna é identificar todos os arcos que terminam em determinado
nó: vantagem para a matriz, já que não existe um método simples
correspondente na implementação ligada
Métodos de passeio
 O objetivo dos métodos de passeio é explorar um grafo, de
forma sistemática, obtendo informações sobre sua
estrutura.
 Uma questão interessante diz respeito ao ponto de início do
passeio, pois não existe um referencial a ser considerado,
como por exemplo, a raiz nas árvores.
 Outra questão é relacionada às repetições nas visitas.
Como garantir que um nó já foi visitado? Solução: colocar
marcas nos nós já visitados.
 A seqüência de nós visitados depende da escolha dos nós
adjacentes. Para um determinado grafo podem existir
diversas seqüências de passeio.
Métodos de passeio
 Existem dois algoritmos principais para passeio em um
grafo G = (N, A):
– Largura (Breadth-first search)
Todos os nós localizados a uma distância k de um nó s, escolhido
arbitrariamente, são percorridos antes dos nós localizados a uma
distância k+1 de s.
– Profundidade (Depth-first search)
Para um nó s, escolhido arbitrariamente, um de seus nós adjacentes
é visitado, e para cada nó visitado, um dos nós adjacente a ele é
visitado, até que se encontre um nó sem adjacentes. Nesse instante
ocorre um “retorno” com o objetivo de visitar os nós restantes
adjacentes à s.
Métodos de passeio
 Largura (Breadth-first search)
1. Um nó, escolhido arbitrariamente, é visitado, marcado e
colocado em uma fila Q;
2. Enquanto a fila Q não estiver vazia:
2.1. Retira-se um nó N da fila Q;
2.2. Para cada nó M (não marcado) adjacente à N:
2.2.1. Visita-se o nó M;
2.2.2. Coloca-se o nó M na fila Q;
2.2.3. Marca-se o nó M.
Métodos de passeio
 Profundidade (Depth-first search)
1. Um nó, escolhido arbitrariamente, é visitado, marcado e
colocado em uma pilha S;
2. Enquanto a pilha S não estiver vazia:
2.1. Retira-se um nó N da pilha S;
2.2. Para cada nó M (não marcado) adjacente à N:
2.2.1. Visita-se o nó M;
2.2.2. Coloca-se o nó M na pilha S;
2.2.3. Marca-se o nó M.