Teoria dos Grafos

Material Teórico
Algoritmos de Busca em Grafos

Responsável pelo Conteúdo:

Prof. Dr. Cleber Silva Ferreira da Luz

Revisão Textual:
Prof. Me. Luciano Vieira Francisco
 Algoritmos de Busca em Grafos

• Introdução;
• Busca em Grafos.

OBJETIVO DE APRENDIZADO
• Conhecer todos os principais conceitos de busca em grafos.
 Orientações de estudo
Para que o conteúdo desta Disciplina seja bem
aproveitado e haja maior aplicabilidade na sua
formação acadêmica e atuação profissional, siga
algumas recomendações básicas:
Conserve seu
material e local de
estudos sempre
organizados.
Aproveite as
Procure manter indicações
contato com seus de Material
colegas e tutores Complementar.
para trocar ideias!
Determine um Isso amplia a
horário fixo aprendizagem.
para estudar.

Mantenha o foco!
Evite se distrair com
as redes sociais.

Seja original!
Nunca plagie
trabalhos.

Não se esqueça
de se alimentar
Assim: e de se manter
Organize seus estudos de maneira que passem a fazer parte hidratado.
da sua rotina. Por exemplo, você poderá determinar um dia e
horário fixos como seu “momento do estudo”;

Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma

alimentação saudável pode proporcionar melhor aproveitamento do estudo;

No material de cada Unidade, há leituras indicadas e, entre elas, artigos científicos, livros, vídeos
e sites para aprofundar os conhecimentos adquiridos ao longo da Unidade. Além disso, você tam-
bém encontrará sugestões de conteúdo extra no item Material Complementar, que ampliarão sua
interpretação e auxiliarão no pleno entendimento dos temas abordados;

Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de discus-
são, pois irão auxiliar a verificar o quanto você absorveu de conhecimento, além de propiciar o
contato com seus colegas e tutores, o que se apresenta como rico espaço de troca de ideias e de
aprendizagem.
UNIDADE Algoritmos de Busca em Grafos

Introdução
Técnicas de busca em grafos são utilizadas em diversas modelagens utilizando
grafos. Em inúmeros problemas há necessidade de visitar os vértices do grafo.
Diferentes algoritmos de busca em grafos foram propostos ao longo dos anos, de
modo que nesta Unidade estudaremos os principais algoritmos de busca em grafos,
a saber; busca em profundidade e busca em largura.

O algoritmo de busca em profundidade realiza a procura em grafo G; começa no

vértice raiz e explora tanto quanto possível cada um de seus ramos. Já o algoritmo
de busca em largura também começa a procura por um vértice raiz e explora todos
os seus vizinhos. Assim, começaremos a estudar um algoritmo genérico de busca.

Busca em Grafos
Algoritmos de busca em grafos são utilizados para solucionar diversos proble-
mas. O seguinte Quadro apresenta um algoritmo para uma busca genérica:

Quadro 1

Ler G = (N, M)
Escolher e marcar um vértice i
Enquanto existir j Є N marcado com uma aresta (j, k) não explorado Fazer
Escolher o vértice j e explorar a aresta (j, k)
// condição variável em conformidade com o tipo de busca //
Se k é não marcado então marcar k
Fim_do_Enquanto

Fonte: Acervo do conteudista

Um exemplo de aplicação que utiliza busca em grafos é dado no problema de

encontrar a saída em um labirinto. Observe, na Figura 1a, um simples labirin-
to. O problema consiste em encontrar uma saída para o qual. É possível mode-
lar este problema com grafos e encontrar uma saída utilizando busca em grafo
(GOLDBARG; GOLDBARG, 2012).

Já a Figura 1b ilustra o começo do processo de modelagem. Primeiro, são colo-

cados círculos margeando todas as paredes do labirinto. Estes círculos representam
vértices dos grafos e são pontos de mudanças de direção no caminho do labirinto.

8
 Entrada Entrada

Saída Saída

a) Labirinto b) Pontos de mudança de direção

Figura 1 – Transformação de um labirinto em um grafo

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Nesta modelagem, as arestas mostram a possibilidade de movimento no labirin-

to. A Figura 2a ilustra as arestas e os vértices representados dentro do labirinto; já
a Figura 2b apresenta o grafo modelado no labirinto:

Entrada Entrada

Saída Saída

a) Grafo no labirinto b) Grafo do labirinto

Figura 2 – Grafo do labirinto

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Para encontrar a saída do labirinto é necessário percorrer os diversos caminhos

possíveis. A forma mais simples de encontrar a saída do labirinto sem nunca percor-
rer mais de uma vez uma mesma parede consiste em rotular as arestas percorridas
na busca, de modo a nunca transitar uma aresta anteriormente rotulada. A busca
começa pela entrada do labirinto, isto é, pelo vértice que representa a entrada no
labirinto, continuando até que o vértice que representa a saída seja alcançado.
As figuras 3a e 3b ilustram duas possíveis sequências de visita no grafo quando
aplicado o algoritmo da busca genérica: o caminho exemplificado na Figura 3a
consiste na visita ao vértice 1, caminhando depois pelas arestas (1,2), (2,3), (3,4),
(4,5), (5,6), (6,7), (7,8), neste momento, o ciclo se fecha sobre o vértice 4 e pela
aresta (8,4), continuando, são percorridas as arestas (4,9), (9,10), (10,11), (11, 12),

9
9
UNIDADE Algoritmos de Busca em Grafos

(12,13) e, por fim, pela aresta (13,14). A Figura 3b apresenta uma busca mais efi-
ciente, inicialmente visitando o vértice 1 e percorrendo as arestas (1,2), (2,3), (3,4),
(4,5), (5,6), (6,7), (7,8), chegando ao vértice 8, ou seja, à saída do labirinto.

2 1 1
2
3
6 5
7 8 4 3
10 9 4
5
11
6
12
13 14 8
7

a) Busca 1 b) Busca 2

Figura 3 – Busca no grafo do labirinto

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Diversos algoritmos são construídos com base no algoritmo genérico. Esses

algoritmos variam o critério de avaliação dos vértices e das arestas. Assim, um
algoritmo muito eficiente e elegante é conhecido como algoritmo de busca em
profundidade – sobre o qual estudaremos na próxima seção.

Busca em Profundidade
A técnica de busca em profundidade tem se mostrado útil no desenvolvimento
de algoritmos eficientes que resolvem problemas, tal como encontrar componentes
fortemente conexos de um grafo (CORMEN et al., 2002).

O algoritmo conhecido como Busca em Profundidade (BP) é desenvolvido so-

bre um algoritmo genérico; todavia, a seleção de vértice é realizada sobre o vértice
não marcado mais recentemente alcançado na busca – os passos que a BP realiza
são apresentados a seguir:

Quadro 2

Procedimento BP(v)
marcar v
Enquanto existir w Є Γ(V) fazer
Se w é não marcado
explorar (v, w)
marca w
BP(w)
Senão
Se (v,w) não explorada
explorar(v,w)
Fim_Enquanto

Fonte: Acervo do conteudista

10
 Importante! Importante!

Note que esse procedimento é recursivo, considerando um grafo conexo e não direcional
(GOLDBARG; GOLDBARG, 2012).

Aplicando o procedimento de busca em 1 4

profundidade em um grafo G a partir de um 3
vértice v qualquer, os vértices marcados e as
arestas exploradas em consequência da satis-
5
fação da condição do primeiro “se” compõem
uma subárvore de G, denominada árvore de
2
profundidade de G – as demais são denomi-
nadas arestas de retorno. 6 7

Analisaremos a busca em profundidade Figura 4 – Exemplo de grafo

por meio de um exemplo; para isso, consi- para a busca em profundidade
dere o grafo apresentado na Figura 4: Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Aplicaremos o algoritmo da busca em profundidade no grafo apresentado (Figu-

ra 4), partindo do vértice 1. As figuras 5a a 5f ilustram a aplicação do procedimento
da busca em profundidade:

1 1
1

2 2

2 3 3

a) Aresta (1, 2) b) Aresta (2, 3) c) Aresta (3, 1)

1 1 1

2 2
2

3 3
3

4 4

5 5

d) Aresta (3, 4) e) Aresta (4, 5) f) Aresta (5, 3)

Figura 5 – Busca em profundidade

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

11
11
UNIDADE Algoritmos de Busca em Grafos

Considere que o grafo da Figura 4 está representado na forma de uma lista de

adjacências, onde os vértices de cada lista encadeada estão ordenados. O inicial
(Vértice 1) é a raiz da árvore de profundidade.

A busca começa no Vértice 1, logo após é verificado o Vértice 2. Como o Vér-

tice 2 é não marcado, então é realizada uma chamada recursiva do procedimento
BP, passando esse vértice como parâmetro de entrada. Neste momento, a chama-
da do procedimento BP(1) fica interrompida, esperando a volta da chamada BP(2)
para ser completada. Durante o processamento de BP(2) é verificado que no Vér-
tice 1 é marcado e que a aresta (1, 2) já foi explorada. Portanto, prossegue-se para
o segundo vizinho do Vértice 2, o nó 3. Assim, a aresta (2, 3) é incluída na árvore,
tal como exemplificado na Figura 5b e o procedimento BP(3) é, então, iniciado. A
lista de adjacências do Vértice 3 é composta pelos vértices 1, 2, 4, 5, 6 e 7. A aresta
(3, 1), ou (1, 3), é não explorada, entretanto, o Vértice 1 é marcado. A aresta (3, 1)
não é incluída na árvore de profundidade, uma vez que é uma aresta de retorno,
conforme ilustrado na Figura 5c – em que a aresta de retorno é representada por
uma linha pontilhada.

Já a aresta (3, 2) é explorada e a (3, 4) é incluída na árvore, conforme ilustrado

na Figura 5d. Assim, uma chamada ao procedimento BP(4) e a aresta (4, 5) é inclu-
ída na árvore, condição ilustrada na Figura 5e.

O procedimento BP(5) é iniciado. O Vértice 3 é marcado, mas a aresta (3, 5)

ainda não é explorada. Dessa forma, a aresta de retorno (5, 3) ou (3, 5) é explorada,
conforme ilustrado na Figura 5f. A verificação do Vértice 5 termina e o procedi-
mento BP(5) é encerrado. No processamento do Vértice 4 também não existem
outros adjacentes ao vértice, terminando, também, o procedimento BP(4).

Assim, retorna-se ao procedimento BP(3). A aresta (3, 5) já está explorada.

Logo, o próximo vizinho do Vértice 3 a ser examinado é o Vértice 6. A aresta (3,
6) é incluída na árvore e uma chamada para BP(6) é realizada. O Vértice 6 não tem
outros vizinhos além do Vértice 3, o procedimento BP(6) é finalizado – isso também
ocorre na verificação do Vértice 7.

As figuras 6a e 6b ilustram as inclusões das arestas (3, 6) e (3, 7), respectivamen-

te, durante a verificação do Vértice 3; já a Figura 6c apresenta a árvore de profundi-
dade construída pelo algoritmo de busca de profundidade para o grafo apresentado
na Figura 4, iniciando pelo Vértice 1.

12
 1 1 1

2 2 2

3 3 3

7 7

4 4 4
6 6 6

5 5 5

a) Aresta (3,6) b) Aresta (3,7) c) Árvore de profundidade

Figura 6 – Busca em profundidade em grafo não direcionado

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

No caso do grafo desconexo, o procedimento BP deve ser chamado novamente

enquanto existir vértice não marcado no grafo. Dessa forma, em vez de uma árvore
de profundidade, o algoritmo construirá uma floresta de profundidade.

O algoritmo de profundidade possui complexidade de O(n+m).

Algoritmo de Busca em Profundidade em Grafos Orientados

Analisaremos o algoritmo de busca em profundidade em grafos orientados, sen-
do essencialmente o mesmo para grafos não orientados; contudo, uma diferença
é que mesmo se o grafo for conexo, o algoritmo de busca pode gerar uma floresta
de profundidade. Em grafos orientados, o algoritmo de busca é chamado enquanto
ainda existir algum vértice não marcado. A seguir, veremos como a busca é realiza-
da para grafos orientados (GOLDBARG; GOLDBARG, 2012):

Quadro 3

Procedimento BP Dir
Ler G = (N, M)
Enquanto existir v Є N, v não marcado Fazer
BP(v)
Fim_Equanto

Fonte: Acervo do conteudista

13
13
UNIDADE Algoritmos de Busca em Grafos

Em grafos orientados, as arestas são particionadas em quatro conjuntos, em vez

de dois – como acontece nos grafos não orientados. O primeiro conjunto contém
as arestas onde o vértice destino ainda não foi marcado. Tais arestas participam da
árvore de profundidade que será construída pelo algoritmo. Considere o Vértice w
e que o destino da aresta seja marcado, então, com uma das três situações a seguir,
denotando o conjunto do qual a aresta participa:
1. Caso w seja descendente de v na floresta, então a aresta será denomi-
nada avanço;
2. Caso v seja descendente de w na floresta, então a aresta será denomi-
nada retorno;
3. Caso v não seja descendente de w e nem w seja descendente de v na flo-
resta, então a aresta será denominada cruzamento.

Aplicaremos o algoritmo de busca em profundidade em um grafo orientado;

para isto, considere o grafo apresentado na Figura 7:

1 4

2
6

Figura 7 – Busca em profundidade em grafo direcionado (1)

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

As figuras 8a a 8f mostram a aplicação do algoritmo de busca em profundidade

em um grafo orientado:

1 1

2 3 6

a) Arco (1, 2) b) Arco (2, 3) c) Arco (3, 6)

1 1 1

4
Arco de
2 2 avanço 2
14
Arco de
 3

2 3 6

a) Arco (1, 2) b) Arco (2, 3) c) Arco (3, 6)

1 1 1

4
Arco de
2 2 avanço 2

Arco de
cruzamento
Arco de
3
3 retorno 3

6
6 6

d) Aresta (3, 4) e) Aresta (4, 5) f) Aresta (5, 3)

Figura 8 – Busca em profundidade em grafo direcionado (2)

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

Note que a busca começa pelo Vértice 1. Conforme ilustrado nas Figuras 8a a
8c, o algoritmo procede incluindo os arcos (1, 2), (2, 3) e (3, 6), respectivamente.
Na verificação do Vértice 6 encontra-se o arco (6, 2). É verificado que o Vértice
2 já é marcado e o Vértice 6 é o seu descendente na árvore. Dessa forma, o arco
(6, 2) é classificado como de retorno, conforme ilustrado na Figura 8d. Os procedi-
mentos para os vértices 6, 3 e 2 são encerrados e a busca volta ao Vértice 1.
Agora, o arco (1, 3) é explorado. Devido ao fato de o Vértice 3 já estar na árvore
e ser descendente de 1, então, o arco (1, 3) será reconhecido como de avanço,
conforme ilustrado na Figura 8e. Assim, a chamada do procedimento de busca ao
Vértice 1 se encerra, tendo construído uma primeira árvore – composta pelos arcos
(1, 2), (2, 3) e (3, 6).
Todavia, os vértices 4 e 5 permanecem não marcados. Assim, uma nova chama-
da de procedimento de busca em profundidade é realizada ao Vértice 4. O primeiro
arco explorado é o (4, 3). O Vértice 3 já está marcado. Como nem o Vértice 3 des-
cende de 4, como também 4 não descende de 3, então o arco (4, 3) é classificado
como de cruzamento (GOLDBARG; GOLDBARG, 2012).
Agora, os arcos (4, 5) e (5, 3) são considerados pela busca, procedimento ilustra-
do nas figuras 9a e 9b; já a Figura 9c apresenta a floresta de profundidade do grafo:

1 1 1

2 4 2 4 2

3 3

3
5
5
6 6 6

a) Arco (4, 5) b) Arco (5,3) c) Floresta de profundidade

Figura 9 – Busca em profundidade em grafo direcionado (3)

Fonte: Adaptada de Goldbarg e Goldbarg, 2012

15
15
UNIDADE Algoritmos de Busca em Grafos

A complexidade do algoritmo de busca em profundidade é de O(n+m).

Busca em Largura
Busca em largura é outro algoritmo baseado no de busca genérico. Neste al-
goritmo de busca, a seleção do vértice é realizada sobre os vértices não marcados
menos recentemente alcançados na busca. A seguir é apresentado o pseudocódigo
da busca em largura (GOLDBARG; GOLDBARG, 2012).

Quadro 4

Procedimento BL(G=(N,M))
definir uma fila Q vazia
escolher um vértice inicial v
marcar v
insere v em Q
Enquanto Q ≠ Ø Fazer
v ← remove elemento de Q
Para todo w Є Γ(v) Fazer
Se w é não marcado
explorar (v, w)
insere w em Q
marcar w
Senão
Se (v, w) não explorada
explorar (v, w)
Fim_Se
Fim_para
Fim_enquanto

Fonte: Acervo do conteudista

Aplicaremos o algoritmo da busca em largura no grafo apresentado na Figura 10 e

que é o mesmo grafo utilizado em exemplos anteriores. Consideraremos novamente
que o grafo está representado através de uma lista de adjacência cujos nós – de cada
lista encadeada – estão ordenados. A busca é iniciada por meio do Vértice 1, enquan-
to que o vértice inicial é a raiz da árvore de profundidade.

16
 1 4
3

6 7

Figura 10 – Busca em largura em grafo não direcionado (1)

Fonte: Adaptado de Goldbarg e Goldbarg, 2012

A aplicação do algoritmo de busca em largura é ilustrada nas figuras 11a a 11h.

Como a busca começa pelo Vértice 1, este é marcado e colocado em Q e logo em
seguida removido de Q. O Vértice 1 possui como vértices adjacentes os de núme-
ros 2 e 3. O Vértice 2 não é marcado, assim, a aresta (1, 2) é incluída na árvore,
o Vértice é marcado e incluído em Q, conforme ilustrado na Figura 11b; o mesmo
ocorre com o Vértice 3, ilustrado na Figura 11c. O Vértice 2, na frente da fila Q, é
removido e a aresta (2, 3) é explorada, assim como na Figura 11d. Já as figuras 11e
a 11h ilustram as inclusões dos vértices 4, 5 e 7, respectivamente, na árvore de bus-
ca em largura e na fila Q. Depois que o Vértice 4 é removido da fila, a aresta (4, 5)
é explorada, conforme ilustrado na Figura 11i. A execução do algoritmo continua
e os vértices restantes são retidos da fila até que Q esteja vazia.

1 1
1

2 2 3

Q = (1) Q = (2) Q = (2, 3)

a) Inclusão de 1 b) Aresta de (1, 2) c) Aresta de (1, 3)

1 1 1

2 3 2 3
2 3

4 4 5

Q = (3) Q = (4) Q = (4,5)

d) Aresta de (2, 3) e) Aresta de (3, 4) f) Aresta de (3, 5)

1 1

2 3 2 3

4 4 7
5 6 5 6
17
Q = (4, 5, 6) Q = (4, 5, 6, 7) 17
g) Aresta de (3, 6) h) Aresta de (3, 7)
UNIDADE Algoritmos de Busca em Grafos
4 4 5

Q = (3) Q = (4) Q = (4,5)

d) Aresta de (2, 3) e) Aresta de (3, 4) f) Aresta de (3, 5)

1 1

2 3 2 3

4 4 7
5 6 5 6

Q = (4, 5, 6) Q = (4, 5, 6, 7)
g) Aresta de (3, 6) h) Aresta de (3, 7)

2 3

4 7
5 6

Q = (5, 6, 7)
i) Aresta de (4, 5)

Figura 11 – Busca em largura em grafo não direcionado

Fonte: Adaptada de Goldbarg e Goldbarg, 2012

A busca em largura possui complexidade de O(n+m)

Em Síntese Importante!

Algoritmos de busca em grafos são utilizados para solucionar diversos problemas mode-
lados por grafos.
Existem diversos algoritmos de busca em grafos, entre os quais o de busca em profundi-
dade e de busca em largura, sendo ambos simples e eficientes.
A busca em profundidade é um algoritmo que percorre os vértices do grafo com o ob-
jetivo de chegar a um determinado vértice. A principal característica desse algoritmo é
percorrer todos os nós filhos de um nó pai.
A busca em largura também percorre os vértices do grafo, objetivando chegar a um
vértice específico. Todavia, a técnica implementada na busca em largura é diferente da
operada em profundidade, afinal, a busca em largura visita todos os vértices vizinhos.

18
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:

Livros
Introdução à Teoria dos Grafos
CLÁUDIO, L. L. Introdução à teoria dos grafos. [S.l.]: Impar, 2016.
Fundamentos da Teoria dos Grafos para Computação
NICOLETTI, A. M.; HRUSCHKA JR, E. R. Fundamentos da teoria dos grafos para
computação. São Carlos, SP: Edufscar, 2006.
Grafos e Redes: Teoria e algoritmos básicos
SIMÕES, J. M. S. Grafos e redes: teoria e algoritmos básicos. [S.l.]: Interciência, 2013.

Leitura
Matemática Discreta: Combinatória, teoria dos grafos e algoritmos
CARDOSO, M.; SZYMANSKI, J.; ROSTAMI, M. Matemática discreta: combinatória,
teoria dos grafos e algoritmos. [S.l.]: Escolar, 2009.
[Link]

19
19
UNIDADE Algoritmos de Busca em Grafos

Referências
BOAVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. 2. ed. São
Paulo: Blucher, 2001.

______.; JURKIEWICZ, S. Grafos: introdução e prática. 2. ed. [S.l.]: Blucher, 2017.

CORMEN, T. et al. Algoritmos – teoria e prática. 2. ed. [S.l.]: Campus, 2002.

FEOFILOFF, P.; KOHAYAKAWA, Y.; WAKABAYASHI, Y. Uma introdução su-

cinta à teoria dos grafos. 2011. Disponível em: <[Link]
teoriadosgrafos>. Acesso em: 24 nov. 2018.

FURTADO, A. L. Teoria dos grafos algoritmos. Rio de Janeiro: LTC, 1973.

GOLDBARG, M.; GOLDBARG, E. Grafos – conceitos, algoritmos e aplicações.

[S.l.]: Campus, 2012.

NICOLETTI, A. M.; HRUSCHKA JR, E. R. Fundamentos da teoria dos grafos

para computação. São Carlos, SP: Edufscar, 2006.

SIMÕES, J. M. S. Grafos e redes: teoria e algoritmos básicos. [S.l.]: Interciência, 2013.

SZWARCFITER, J. L. Teoria computacional de grafos. [S.l.]: Elsevier, 2018.

20