Algoritmos V

Enviado por Tiago Madeira


1. Representando Grafos na Programação

No último artigo, conhecemos a representação chamada "grafo" da seguinte maneira:

Como todos sabemos, seria bem difícil trabalhar uma árvore assim na programação! Por isso, existem várias maneiras de representar um grafo. Nesta série só vou usar as duas mais populares:

  • Matriz de Adjacência
  • Lista de Adjacência

Poderíamos falar também sobre a Matriz de Incidência, mas eu nunca precisei utilizá-la, então prefiro só entrar nessas duas mesmo.

Cada vértice é um número

Para representar um grafo, cada vértice sempre vai ser um número. No caso de você querer representar amizade entre duas pessoas, como no exemplo do Orkut no último artigo, você cria um vetor chamado nome[] que contém o nome de cada número...

Matriz de Adjacência

A matriz de adjacência é uma matriz de N x N (onde N é o número de vértices do grafo). Ela inicialmente é preenchida toda com 0 e quando há uma relação entre o vértice do x (número da coluna) com o do y (número da linha), matriz[x][y] é marcado um 1.

Vamos escrever este grafo aqui usando uma matriz de adjacência:

Matriz Inicial

1

2

3

4

5

1

0

0

0

0

0

2

0

0

0

0

0

3

0

0

0

0

0

4

0

0

0

0

0

5

0

0

0

0

0

2. Relações do nosso grafo

Já que o grafo não é orientado, a relação 1-2 significa 2-1 também.

  • 1-2 (2-1)
  • 1-3 (3-1)
  • 2-3 (3-2)
  • 2-4 (4-2)
  • 4-5 (5-4)

Página seguinte 



As opiniões expressas em todos os documentos publicados aqui neste site são de responsabilidade exclusiva dos autores e não de Monografias.com. O objetivo de Monografias.com é disponibilizar o conhecimento para toda a sua comunidade. É de responsabilidade de cada leitor o eventual uso que venha a fazer desta informação. Em qualquer caso é obrigatória a citação bibliográfica completa, incluindo o autor e o site Monografias.com.