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.
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...
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 |
Página seguinte  |
|
|
|
Enviado por