Estrutura de Dados (CC4652)
Aula 12 - Grafos
Prof. Luciano Rossi
Ciência da Computação
Centro Universitário FEI
2º Semestre de 2023
1 / 45
Grafos
Classificação das Estruturas de Dados
2 / 45
Grafos
Conceitos
Um grafo consiste em um conjunto de nós (ou vértices) e em um
conjunto de arestas (ou arcos)
Cada aresta em um grafo é especificada por um par de nós.
Grafo com 5 nós e 6 arestas:
3 / 45
Grafos
Conceitos
Uma matriz de adjacência é uma das formas de se representar um grafo
Em grafos não direcionados, as matrizes de adjacência são simétricas
ao longo da diagonal principal
4 / 45
Grafos
Conceitos
Cada nó ou aresta pode ter propriedades, características ou dados
Ou seja, os nós ou arestas podem conter informação
5 / 45
Grafos
Conceitos
Os grafos podem ser:
▶ Não Direcionados (não dirigidos): não existe direção obrigatória
▶ Direcionados (dirigidos ou dígrafos): As arestas têm sentido - a ponta
da seta representa o segundo nó
6 / 45
Grafos
Conceitos
Os grafos podem também ter suas arestas ponderadas
7 / 45
Grafos
Conceitos
Exemplos de uso:
8 / 45
Grafos
Conceitos
Grafo - Exemplo Linkedin
9 / 45
Grafos
Conceitos
Exemplos de uso Grafo Não Direcionado:
▶ Amizade em Rede Social
10 / 45
Grafos
Conceitos
Exemplos de uso Grafo Direcionado:
▶ Caminho entre duas cidades: Cidade 1 e Cidade 6
11 / 45
Grafos
Conceitos
Dois vértices que são conectados por uma aresta são chamados de
adjacentes. Ex: A e B são adjacentes
Uma aresta é dita ser incidente a cada um de seus nós terminais. Ex:
(A, B) é incidente aos vértices A e B
12 / 45
Grafos
Conceitos
Um vértice que não possui nenhuma aresta incidente é chamado de
isolado
Um grafo com nenhum vértice é chamado de vazio
13 / 45
Grafos
Conceitos
Um vértice que é nó terminal de um laço é dito ser adjacente a si
próprio.
14 / 45
Grafos
Conceitos
Os nós são: A,B,C,D,E,F,G,H
As arestas são: (A,B), (A,D), (A,C), (C,D), (C,F), (E,G), (A,A)
15 / 45
Grafos
Conceitos
Vizinhança Aberta (Open Neighborhood): Conjunto de nós adjacentes a
um nó.
▶ Exemplo: N (2) = {3, 5, 1}
Vizinhança Fechada (Close Neighborhood): Conjunto de nós adjacentes
a um nó e o próprio nó.
▶ Exemplo: N (2) = {2, 3, 5, 1}
16 / 45
Grafos
Conceitos
Grau do Vértice (Degree of a Vertex): Medido pela incidência
▶ Exemplo: d(2) = 3
▶ Exemplo: d(6) = 1
▶ Exemplo: d(1) = 4
17 / 45
Grafos
Conceitos
Grau do Vértice (Degree of a Vertex):
18 / 45
Grafos
Conceitos
Grafo Completo
▶ Um grafo completo de n vértices é um grafo simples cujo conjunto de
arestas contém exatamente uma aresta para cada par de vértices distintos.
▶ Exemplos para 1, 2, 3, 4 e 5 nós:
19 / 45
Grafos
Conceitos
Grafo Bipartido
▶ Grafo Bipartido é um grafo cujos vértices podem ser divididos em dois
conjuntos disjuntos U e V tais que toda aresta conecta um vértice de U a
um vértice em V
20 / 45
Grafos
Representações
Matriz de Adjacência
▶ Grafo Bipartido é um grafo cujos vértices podem ser divididos em dois
conjuntos disjuntos U e V tais que toda aresta conecta um vértice de U a
um vértice em V
21 / 45
Grafos
Representações
Matriz de Adjacência
22 / 45
Grafos
Representações
Matriz de Adjacência
23 / 45
Grafos
Representações
Lista de Adjacência
▶ A Lista de Adjacência é um array de listas
▶ O tamanho do array é igual ao número de vértices
24 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
BF S(G, s)
▶ Entrada: um grafo G e um vértice inicial s;
▶ Saída: distâncias em relação ao vértice inicial.
25 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
Duas partes:
▶ Inicialização;
▶ Execução;
Baseado em fila:
▶ First-In, First-Out.
26 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
Atributo dos vértices:
▶ distância
▶ cor:
⋆ branca (inicial)
⋆ cinza (visitado)
⋆ preta (finalizado)
27 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
BF S(G, s) : 8 enquanto Q! = V AZIO faça
1 para cada vértice vi em G.V − {s} faça 9 ui = Remove(Q)
2 vi .d = ∞ 10 para cada vi em G.Adj[ui ] faça
3 vi .cor = BRAN CO 11 se vi .cor == BRAN CO
4 s.d = 0 12 vi .d = ui .d + 1
5 s.cor = CIN ZA 13 vi .cor = CIN ZA
6 Q = V AZIO 14 Insere(Q, vi )
7 Insere(Q, s) 15 ui .cor = P RET O
28 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
BF S(G, s) :
1 para cada vértice vi em G.V − {s} faça
2 vi .d = ∞
3 vi .cor = BRAN CO
4 s.d = 0
5 s.cor = CIN ZA
6 Q = V AZIO
7 Insere(Q, s)
29 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
30 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
31 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
32 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
33 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
34 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
35 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
36 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
37 / 45
Teoria dos Grafos
Algoritmos de Busca em Grafos - Busca em Largura (Breadth First Search (BFS))
8 enquanto Q! = V AZIO faça
9 ui = Remove(Q)
10 para cada vi em G.Adj[ui ] faça
11 se vi .cor == BRAN CO
12 vi .d = ui .d + 1
13 vi .cor = CIN ZA
14 Insere(Q, vi )
15 ui .cor = P RET O
38 / 45
Grafos
Laboratório
1 #include <stdio.h>
2
3 #define V 6
4 #define E 12
5
6 int get_index(char x){
7 return x - 97;
8 }
9
10 void inicia_arestas(int arestas[V][V]){
11 for(int i = 0; i < V; i++){
12 for(int j = 0; j < V; j++){
13 arestas[i][j] = 0;
14 }
15 }
16 }
17 ...
39 / 45
Grafos
Laboratório
1 ...
2 void cria_arestas(int arestas[V][V], int v, int u){
3 arestas[v][u] = 1;
4 }
5
6 void mostra_arestas(int arestas[V][V]){
7 for(int i = 0; i < V; i++){
8 for(int j = 0; j < V; j++){
9 printf("%d ", arestas[i][j])
;
10 }
11 printf("\n");
12 }
13 }
14 ...
40 / 45
Grafos
Laboratório
1 ...
2 void mostra_adjacentes(int arestas[V][V], char v){
3 //implementar
4 }
5
6 void mostra_distancias(int arestas[V][V], char v){
7 //implementar
8 }
9 ...
41 / 45
Grafos
Laboratório
Matriz de Adjacências
0 1 0 1 1 0
1 0 1 0 0 1
0 1 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 1
0 1 0 0 1 0
42 / 45
Grafos
Laboratório
Adjacências
a -> b
a -> d
a -> e
b -> a
b -> c
b -> f
c -> b
d -> a
e -> a
e -> f
f -> b
f -> e
43 / 45
Grafos
Laboratório
Matriz de Distâncias
0 1 2 1 1 2
1 0 1 2 2 1
2 1 0 3 3 2
1 2 3 0 2 3
1 2 3 2 0 1
2 1 2 3 1 0
44 / 45
Estrutura de Dados (CC4652)
Aula 12 - Grafos
Prof. Luciano Rossi
Ciência da Computação
Centro Universitário FEI
2º Semestre de 2023
45 / 45
