Grafos
1368 palavras
6 páginas
Estruturas de DadosGrafos: Representação e Busca
André Macedo Santana andremacedo@ufpi.edu.br EricoMenesesLeão ericoleao@ufpi.edu.br Representação e Busca
Introdução
.:
Primeiras palavras -‐ Existem três formas tradicionais de representar os grafos:
-‐ matriz de adjacência;
-‐ matriz de incidência; e
-‐ lista de adjacência;
-‐ Além disso uma operação muito importante em grafos é como percorrê-‐lo.
Apresentaremos aqui duas formas, também tradicionais, de executar essa
operação em grafos:
-‐ busca em largura; e
-‐ busca em profundidade.
Estruturas de Dados
Santana, A. M. &Leão, E. M. 2009
UniversidadeAberta do Piauí - UAPI
Representação e Busca
Representação
.:
Matriz de Adjacência -‐ Uma das formas mais uClizadas para representar grafos é via matriz de
adjacência. Seja A = [ aij] uma matriz n × n, onde n é o numero de vérCces de um
grafo G = (V,E) qualquer, a matriz de adjacência A é construída da seguinte forma:
Estruturas de Dados
Santana, A. M. &Leão, E. M. 2009
UniversidadeAberta do Piauí - UAPI
Representação e Busca
Representação
.:
Matriz de Adjacência -‐ Quando o