Matriz de Adjacência – Representação de Grafos
Um grafo é uma estrutura composta por vértices (nós) e arestas que conectam esses vértices. Grafos podem ser utilizados para modelar relacionamentos entre objetos ou representar uma rede. Eles são frequentemente usados para mostrar conexões entre cidades, pessoas ou até entidades mais abstratas.
Grafos podem ser dirigidos ou não dirigidos:
- Grafos dirigidos: Todas as arestas têm uma direção, o que significa que há uma “estrada” de um vértice para outro, mas talvez não haja o caminho de volta. É semelhante a uma rua de mão única.
Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
- Grafos não dirigidos: As arestas não possuem direcionamento, então se existe uma aresta entre dois vértices, eles estão conectados em ambas as direções.
Uma das formas de representar um grafo é por meio de uma Matriz de Adjacência. Trata-se de uma matriz quadrada que descreve todo o grafo. Cada linha e coluna da matriz corresponde a um vértice. Se existe uma aresta entre dois vértices, a respectiva posição na matriz recebe o valor 1; caso contrário, recebe 0.
A matriz de adjacência para o grafo dirigido apresentado acima pode se parecer com isto:
g = [
# 1 2 3 4 5 6 7 8
[0, 1, 0, 1, 0, 0, 0, 0], # ligações que saem do vértice 1
[0, 0, 0, 0, 1, 0, 0, 0], # ligações que saem do vértice 2
[0, 1, 0, 0, 0, 0, 0, 0], # ligações que saem do vértice 3
[0, 0, 0, 0, 0, 0, 0, 0], # ligações que saem do vértice 4
[0, 0, 0, 0, 0, 1, 0, 1], # ligações que saem do vértice 5
[0, 0, 0, 1, 0, 0, 1, 0], # ligações que saem do vértice 6
[0, 0, 0, 0, 0, 0, 0, 1], # ligações que saem do vértice 7
[0, 0, 0, 0, 1, 0, 0, 0], # ligações que saem do vértice 8
]Observe que, para uma aresta bidirecional, os dois vértices terão o valor 1 nas posições correspondentes.
Além disso, repare que alteramos a forma como numeramos as arestas. Se acessarmos
g[0], na prática estaremos retornando todas as conexões do nó com índice 1. Poderíamos ter utilizado 9 linhas e 9 colunas em vez de 8 para que os números da imagem correspondessem exatamente aos índices da matriz g, mas isso fica a seu critério 😎.Desafio: Arestas para Matriz de Adjacência
Dado um grafo com
v vértices e e arestas, você deve construir a matriz de adjacência correspondente.Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 1000) e e (1 ≤ e ≤ 100 000).As
e linhas seguintes contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está conectado ao vértice v2 e vice-versa.Saída
O programa deve imprimir a matriz de adjacência do grafo fornecido. Os valores de cada linha devem ser separados por um espaço.
Exemplos
Entrada | Saída |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 0 1 1 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB