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:
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 |
Já que o grafo não é orientado, a relação 1-2 significa 2-1 também.
Página seguinte  |
|
|
|
Enviado por