Neste tutorial, você aprenderá o que é uma matriz de adjacência. Além disso, você encontrará exemplos funcionais de matriz de adjacência em C, C ++, Java e Python.
Uma matriz de adjacência é uma forma de representar um grafo G = (V, E) como uma matriz de booleanos.
Representação da matriz de adjacência
O tamanho da matriz é VxVonde Vestá o número de vértices no gráfico e o valor de uma entrada Aijé 1 ou 0 dependendo se há uma aresta do vértice i ao vértice j.
Exemplo de matriz de adjacência
A imagem abaixo mostra um grafo e sua matriz de adjacência equivalente.
Matriz de adjacência de um gráfico
No caso de gráficos não direcionados, a matriz é simétrica em relação à diagonal por causa de cada aresta (i,j), também há uma aresta (j,i).
Prós da matriz de adjacência
As operações básicas como adicionar uma aresta, remover uma aresta e verificar se há uma aresta do vértice i para o vértice j são operações de tempo constante e extremamente eficientes.
Se o grafo for denso e o número de arestas for grande, a matriz de adjacência deve ser a primeira escolha. Mesmo que o gráfico e a matriz de adjacência sejam esparsos, podemos representá-los usando estruturas de dados para matrizes esparsas.
A maior vantagem, entretanto, vem do uso de matrizes. Os avanços recentes em hardware nos permitem realizar operações matriciais ainda caras na GPU.
Ao realizar operações na matriz adjacente, podemos obter insights importantes sobre a natureza do gráfico e a relação entre seus vértices.
Contras da matriz de adjacência
O VxVrequisito de espaço da matriz de adjacência a torna um grande consumidor de memória. Gráficos à solta geralmente não têm muitas conexões e esta é a principal razão pela qual as listas de adjacência são a melhor escolha para a maioria das tarefas.
Embora as operações básicas sejam fáceis, as operações gostam inEdgese outEdgessão caras ao usar a representação de matriz de adjacência.
Exemplos de Python, Java e C / C ++
Se você sabe como criar matrizes bidimensionais, também sabe como criar uma matriz de adjacência.
Python Java C C + # Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = () for i in range(size): self.adjMatrix.append((0 for i in range(size))) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix(v1)(v2) = 1 self.adjMatrix(v2)(v1) = 1 # Remove edges def remove_edge(self, v1, v2): if self.adjMatrix(v1)(v2) == 0: print("No edge between %d and %d" % (v1, v2)) return self.adjMatrix(v1)(v2) = 0 self.adjMatrix(v2)(v1) = 0 def __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('(:4)'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main()
// Adjacency Matrix representation in Java public class Graph ( private boolean adjMatrix()(); private int numVertices; // Initialize the matrix public Graph(int numVertices) ( this.numVertices = numVertices; adjMatrix = new boolean(numVertices)(numVertices); ) // Add edges public void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges public void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the matrix public String toString() ( StringBuilder s = new StringBuilder(); for (int i = 0; i < numVertices; i++) ( s.append(i + ": "); for (boolean j : adjMatrix(i)) ( s.append((j ? 1 : 0) + " "); ) s.append(""); ) return s.toString(); ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); System.out.print(g.toString()); ) )
// Adjacency Matrix representation in C #include #define V 4 // Initialize the matrix to zero void init(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr(i)(j) = 0; ) // Add edges void addEdge(int arr()(V), int i, int j) ( arr(i)(j) = 1; arr(j)(i) = 1; ) // Print the matrix void printAdjMatrix(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) ( printf("%d: ", i); for (j = 0; j < V; j++) ( printf("%d ", arr(i)(j)); ) printf(""); ) ) int main() ( int adjMatrix(V)(V); init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; )
// Adjacency Matrix representation in C++ #include using namespace std; class Graph ( private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero Graph(int numVertices) ( this->numVertices = numVertices; adjMatrix = new bool*(numVertices); for (int i = 0; i < numVertices; i++) ( adjMatrix(i) = new bool(numVertices); for (int j = 0; j < numVertices; j++) adjMatrix(i)(j) = false; ) ) // Add edges void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the martix void toString() ( for (int i = 0; i < numVertices; i++) ( cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix(i)(j) << " "; cout << ""; ) ) ~Graph() ( for (int i = 0; i < numVertices; i++) delete() adjMatrix(i); delete() adjMatrix; ) ); int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.toString(); )
Aplicativos de matriz de adjacência
- Criação de tabela de roteamento em redes
- Tarefas de navegação
