ESCOLA DE ENGENHARIA
C++
Grafos e Árvores
Instalação Elétrica
5,00 m
Quadro
Tom A
L
Int
Tom B
5,00 m
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
Pontos,
conduítes e
fiação.
2/33
América do Sul
Fronteiras
entre os
países.
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
3/33
Herança
Animal
Mamífero
Leão
Homem
Relacionamento
de especialização.
C++ - Grafos e Árvores
Marinho
Peixe
Inseto
Mosca
Barata
Homosca
Prof. Lincoln Cesar Zamboni
4/33
Linguagem C++
1.1 x--;
1.2 if(x>0) x+= 2;
1
1.3 for(int k= 1; k<=x; k++){
1.3.1 y+= 3;
1.3.2 w--;
1.3.3 if(w<0) y--;
1.3.4 else y++;
}
1.4 y= sqr(x);
Indentação
das linhas do
programa.
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
5/33
Fluxograma ISO 5807
L(v) é a distância
mínima de u0 até v,  v  M
início
M = {u0}
L(u0) = 0
V
1
D=
F
L(v) = mín(L(v), L(ui)+W(ui , v))
vD
L(v) = 
vD
ui+1|L(ui+1)= mín({L(v)| v  D})
i=0
M = M  {ui+1}
1
i=i+1
C++ - Grafos e Árvores
fim
Prof. Lincoln Cesar Zamboni
Processos e
processos de
decisão.
6/33
Lista
Cabeça
Remove do começo
Insere no começo
Insere no começo
Remove do meio
Insere no fim
Remove do fim
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
7/33
Pilha
Cabeça
Empilha
Empilha
Desempilha
Desempilha
Empilha
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
8/33
Fila
Cabeça
Enfileira
Desenfileira
Desenfileira
Desenfileira
Enfileira
Enfileira
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
9/33
Grafos e Dígrafos (Graph, Digraph)
G = (V, E, Ψ)
Vértices
•
•
•
•
Arestas
ou Arcos
Função de
Incidência
Dirigido, Orientado
VØ
(Directed)
VE=Ø
Ψ : E  { {v, w} | v, w  V} (Grafo)
Ψ : E  { (v, w) | v, w  V} (Dígrafo)
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
10/33
C
Exemplo de Grafo
c
Lula = (Bar, Bu, Do)
Bar = {a, b, c, d, e}
Bu = {A, B, C, D, E,
D
C++ - Grafos e Árvores
E
d
F, G, H}
Do
Do(A) = {a, b}
B
b
G
e
F
A
H

Do(E) = {b, d}

Do(B) = {b, c}

Do(F) = {d, e}

Do(C) = {c, c} = {c}

Do(G) = {b, e}

Do(D) = {c, d}

Do(H) = {b, e}
Prof. Lincoln Cesar Zamboni
11/33
a
Outra Geometria do exemplo
mude a posição dos vértices
mude a posição dos arcos
a
D
c
B
d G
Os arcos
podem se
cruzar.
F
A
e
b
H
E
C
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
12/33
Exemplo de Dígrafo
c
Pico = (Lé, DeChu, Chu)
Lé = {a, b, c, d, e}
C
D
d
E
B
b
A
G
DeChu = {A, B, C, D,
F
e
E, F, G, H}
Chu
Chu(A) = (a, b)

Chu(E) = (b, d)

Chu(B) = (b, c)

Chu(F) = (d, e)

Chu(C) = (c, c)

Chu(G) = (b, e)

Chu(D) = (c, d)

Chu(H) = (b, e)
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
H
13/33
a
Grafo Simples
Não possui laços (loops)
X
X
X
X
Não possui arestas múltiplas
X
X
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
14/33
Vértices Adjacentes
Grafo:



C++ - Grafos e Árvores
A
a
o vértice a é adjacente ao vértice b;
o vértice b é adjacente ao vértice a.
Dígrafo:

b
b
A
a
o vértice a não é adjacente ao vértice b;
o vértice b é adjacente ao vértice a.
Prof. Lincoln Cesar Zamboni
15/33
Grafo e Matriz de Adjacência
cada elemento da matriz é a quantidade de
arestas que vão do vértice i ao vértice j e viceversa (são adjacentes).
C
simétrica
Exemplo
c
D
d
B
E
i
b
G
F
C++ - Grafos e Árvores
e
j

A
a
H
Prof. Lincoln Cesar Zamboni
a
b
b
c
d
e
a
0
1
0
0
0
b
1
0
1
1
2
2
c
0
1
1
1
0
d
0
1
1
0
1
e
e
0
2
2
0
1
0
16/33
Dígrafo e Matriz de Adjacência
cada elemento da matriz é a quantidade de
arestas que vão do vértice i ao vértice j (o j é
adjacente ao i).
ao
18/25 = 72%
j
de nulos

C
Exemplo
a b c d e
e
c
a
0
1
0
0
0
B
D
E
2
do i b
b 0 0 1 1 2
d
b A a
c 0 0 1 1 0
G
d 0 0 0 0 1
F
H
e 0 0 0 0 0
e
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
17/33
Rede ou Grafo Ponderado
R = (V, E, Ψ, ω)
Vértices
Arestas
ou Arcos
Função de
Incidência
Função
de Pesos
ω : E  R (número real)
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
18/33
Exemplo de Rede
8
c
Lu = (Isa, He, Le, Na)
Isa = {a, b, c, d, e}
He = {A, B, C, D, E,
7
d
5
6
b
6
4
F, G, H}
Le, Na
7
e
3

Le(A)={a, b}, Na(A)=6

Le(E) = {b, d}, Na(E)=6

Le(B)={b, c}, Na(B)=5

Le(F) = {d, e}, Na(F)=7

Le(C)={c}, Na(C)=8

Le(G) = {b, e}, Na(G)=4

Le(D)={c, d}, Na(D)=7

Le(H) = {b, e}, Na(H)=3
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
19/33
a
Passeio (Walk)
1
a
b
2
4
e
Seqüência não nula, finita e alternada de
vértices adjacentes e arestas incidentes.
W = v0e1 v1e2 v2e3 ... ekvk
onde:
• 1  k  n (nN*)
• (ek) = {vk-1, vk}
c
d
7
g
3
u 5
f
6
v
9
10
11
i
12
m
13
o
p
r
15
s
t
cucaracha
C++ - Grafos e Árvores
n
14
q
16
h
j
l
k
8
17
Exemplos:
• Antenas = 1a3c4b2
• Cabeça = 3c4e6f5d3 (fechado)
• W1 = 14t17r14n12n14m10
• W2 = 5f6v10h8h10m14
• W3 = 5i15o13l9u5 (fechado)
• W4 = 12n14
Prof. Lincoln Cesar Zamboni
20/33
Trajeto (Trail)
1
a
b
2
4
e
Passeio onde as arestas não se repetem.
c
d
7
3
5
u
g
f
6
v
9
10
11
i
12
m
13
o
p
• Cabeça = 3c4e6f5d3 (fechado)
• Patinha Direita Central = 12n14
r
15
s
C++ - Grafos e Árvores
n
14
q
16
h
j
l
k
Exemplos:
• Antenas = 1a3c4b2
8
• T1 = 2b4e6j15p14t17
• T2 = 2b4e6j15p14r17
t
cucaracha
• T3 = 11k13s16q13l9u5i15j6f5
17
Prof. Lincoln Cesar Zamboni
21/33
Caminho (Path)
Passeio onde os vértices não se repetem.
1
a
b
2
4
e
c
d
7
g
3
u 5
f
6
v
9
10
11
i
12
m
13
o
p
r
15
s
C++ - Grafos e Árvores
n
14
q
16
h
j
l
k
8
t
cucaracha
Exemplos:
• Antenas = 1a3c4b2
• Patinha Direita Central = 12n14
• P1 = 11k13o15j6v10m14t17
• P2 = 2b4e6j15p14t17
• P3 = 2b4e6j15p14r17
• P4 = 8h10m14
17
Prof. Lincoln Cesar Zamboni
22/33
Ciclo (Cycle)
1
a
b
2
4
e
Trajeto fechado (v0=vk).
c
d
7
g
3
5
u
f
6
v
9
10
11
i
12
m
n
o
q
p
r
15
s
t
cucaracha
C++ - Grafos e Árvores
• Asa Esquerda = 5i15o13l9u5 (fechado)
• Patona Direita = 14t17r14 (fechado)
14
13
16
h
j
l
k
Exemplos:
• Cabeça = 3c4e6f5d3 (fechado)
8
• C1 = 6v10m14t17r14p15j6 (fechado)
• C2 = 5f6v10m14p15o13l9u5 (fechado)
• C3 = 3c4e6v10m14p15o13l9u5d3 (fechado)
17
Prof. Lincoln Cesar Zamboni
23/33
DAG (Directed Acyclic Graph)
3
5
5
8
0
5
7
8
3
2
3
6
1
8
9
4
2
7
6
Redes PERT (Program Evaluation and Review Technique):
DAG ponderado onde os arcos representam atividades, os vértices representam
o início e o fim das atividade e os pesos representam intervalos de tempo.
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
24/33
Árvore (Tree)
Grafo acíclico (não possui ciclos) e conexo (existe um caminho
entre qualquer par de vértices distintos).
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
25/33
Grafos e Listas de Adjacência
A
3
1
1
2
0
A lista de adjacência
está em ordem
crescente de vértices
(do A até o E) de forma
a facilitar a
implementação.
B
0
1
C
1
1
B
0
A
D
3
0
C
E
0
0
E
D
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
26/33
Dígrafos e Listas de Adjacência
A
1
2
3
Lista de Adjacência
do vértice A
0
Lista de
Adjacência
do vértice B
B
1
C
1
D
0
1
Lista de
0
Adjacência
do vértice C
Lista de
Adjacência
do vértice D
B
A
C
E
0
3
1
0
0
E
Lista dos Vértices Lista de Adjacência do vértice E
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
D
27/33
Árvore
nível 0
A
nível 1
B
C
D
E
F
nível 2
G
H
I
J
K
L
M
nível 3
N
C++ - Grafos e Árvores
O
P
Prof. Lincoln Cesar Zamboni
Q
R
S
28/33
Árvore: Nó de uma Árvore
próximo irmão
primogênito
pai
informação
ponteiros
class TArvore
{
private:
TAlgumTipo inf;
TArvore *pai;
TArvore *prim;
TArvore *prox
// ...
public:
// ...
// operações em
// ...
};
//
//
//
//
informação
pai
primogênito
próximo irmão
uma árvore.
Não é imprescindível, mas pode ajudar na
implementação dos métodos.
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
29/33
Árvore: ligações
vai para A
vem de E
F
0
F
K
L
M
K
R
S
L
M
vem de Q
vai para Q
vem de Q
C++ - Grafos e Árvores
R
Prof. Lincoln Cesar Zamboni
0
S
00
30/33
00
Árvore: busca em largura e busca
em profundidade
nível 0
A
nível 1
B
C
D
nível 2
G
H
I
J
Profundidade
Largura
E
F
K
L
M
nível 3
N
C++ - Grafos e Árvores
O
P
Prof. Lincoln Cesar Zamboni
Q
R
S
31/33
Árvore: Busca em Largura
S
A
1
A
R
B
Q
C
2
B
3C
4
D
5
E
6
F
P
Fila
D
O
E
7
G
8
H
9
I
10
J
11
K
12
L
13
M
N
F
M
G
14
N
15
O
16
P
17
Q
18
R
19
S
ALGORITMO:
enfileire o nó raiz da árvore;
enquanto existirem nós enfileirados:
desenfileire e marque o nó;
para todos os nós filhos deste nó marcado:
enfileire o nó filho;
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
L
H
I
J
K
32/33
Busca em Profundidade
1
A
R
A
S
F
2
B
4
C
12
E
D
8
13
F
E
D
5
H
G
3
7
I
9
J
14
K
Q
L
16
M
19
K
Pilha
L
C
M
B
6
N
O
10
11
P
15
Q
17
R
18
S
ALGORITMO:
empilhe o nó raiz da árvore;
enquanto existirem nós empilhados:
desempilhe e marque o nó;
para todos os nós filhos deste nó marcado:
empilhe o nó filho;
C++ - Grafos e Árvores
Prof. Lincoln Cesar Zamboni
O
G
P
I
H
N
J
33/33