Grafos são estruturas de dados muito poderosas formadas por um conjunto de nós, também conhecidos como vértices, e arestas que os conectam. Existem duas maneiras comuns de implementar grafos no seu código: * Matrizes de adjacência * Listas de adjacência Vamos analisar mais a fundo estes e revisar suas vantagens e limitações.

Matrizes de Adjacência

Começaremos com matrizes de adjacência. Uma matriz de adjacência é uma lista bidimensional na qual as linhas e colunas representam os vértices do grafo. Os valores na matriz representam as arestas ou conexões entre os nós. Por exemplo, se você tem uma matriz armazenada em uma variável chamada matrix, o valor armazenado em matrix[i][j], onde i é a linha e j é a coluna, representa a aresta ou conexão entre o nó i e o nó j. Os valores podem ter significados diferentes dependendo se o grafo é ponderado ou não ponderado: * Se o grafo não for ponderado, um valor de 1 significa que há uma aresta conectando esses nós, enquanto um valor de 0 significa que não há aresta entre eles. * Se o grafo for ponderado, o valor representaria o peso da aresta que conecta os nós. Uma das grandes vantagens de usar uma matriz de adjacência é que verificar se existe uma aresta entre dois nós leva tempo constante O(1). Isso ocorre porque o programa só precisa encontrar esse valor específico na lista 2D. No entanto, essa eficiência em encontrar as arestas vem com uma compensação. Matrizes de adjacência têm um grande requisito quadrático de espaço O(V²), onde V é o número de nós no grafo. Isto é ineficiente para grafos esparsos, que são grafos que possuem apenas algumas arestas. Por quê? Porque se o grafo for esparso, você estará armazenando muitos 0s na matriz para representar a ausência de arestas entre os nós, e esses 0s ainda ocuparão espaço na memória. Matrizes de adjacência também são ineficientes para encontrar os vizinhos de um nó porque o programa precisa iterar sobre toda a linha ou coluna para encontrar os 0s e 1s que representam as arestas. No pior caso, esse processo pode levar tempo O(V), onde V é o número de nós no grafo. Vamos ver um exemplo de matriz de adjacência para este gráfico em particular: <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-matrices-and-adjacency-lists-work-1.png" alt="A graph with four nodes labeled A, B, C, and D. Node A connects to B, C, and D. Node B connects to A and D. Node C connects to A. Node D connects to A and B."> Na matriz de adjacência: * Cada linha representa um nó. A primeira linha representa o nó A, a segunda linha representa o nó B e assim por diante. * Cada coluna também representa um nó. * Cada valor na matriz representa se existe uma aresta entre cada par de nós. Um valor 0 significa que não há uma aresta conectando esses nós, enquanto um valor 1 significa que há uma aresta. Os valores na diagonal representam se cada nó possui ou não um self-loop, uma aresta que conecta o nó a si mesmo. No nosso exemplo, todos são 0s porque o grafo não possui nenhum self-loop. Esta é uma representação visual da matriz de adjacência para mostrar como as linhas e colunas representam os nós correspondentes. Por exemplo, a primeira linha é [0, 1, 1, 1] porque o nó A tem arestas conectando-o aos nós B, C e D:

#      A  B  C  D
# A   [0, 1, 1, 1],
# B   [1, 0, 0, 1],
# C   [1, 0, 0, 0],
# D   [1, 1, 0, 0]

E esta é a mesma matriz de adjacência, mas implementada em código Python:

adjacency_matrix = [
    [0, 1, 1, 1],  # The neighbors of A are B, C, and D
    [1, 0, 0, 1],  # The neighbors of B are A and D
    [1, 0, 0, 0],  # The only neighbor of C is A
    [1, 1, 0, 0]   # The neighbors of D are A and B
]

Listas de Adjacência

Outra forma comum de representar grafos é usando listas de adjacência. Uma lista de adjacência é um array ou dicionário que armazena todos os vizinhos de cada nó. Existem duas maneiras de implementar listas de adjacência: * Como um array, onde cada índice representa um nó e a lista armazenada naquele índice contém seus vizinhos. * Como um dicionário, onde cada chave representa um nó e o valor associado a essa chave (uma lista) contém seus vizinhos. Listas de adjacência são mais eficientes do que matrizes de adjacência em termos de requisitos de espaço. Elas têm uma complexidade de espaço O(V + E), onde V é o número de vértices (nós) e E é o número de arestas. Também é eficiente para encontrar todos os nós vizinhos, já que essa operação requer apenas acessar a lista associada ao nó. No entanto, também há uma troca. Listas de adjacência são menos eficientes do que matrizes de adjacência para determinar se existe uma aresta entre dois nós. O processo de busca pode levar O(V) tempo no pior caso, já que pode ser necessário buscar em uma lista muito longa de vizinhos se o nó estiver conectado a todos os outros nós no grafo. Aqui está um exemplo de uma lista de adjacência para este grafo: <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-matrices-and-adjacency-lists-work-1.png" alt="A graph with four nodes labeled A, B, C, and D. Node A connects to B, C, and D. Node B connects to A and D. Node C connects to A. Node D connects to A and B. It's the same image as before."> Esta lista de adjacência é implementada como um dicionário. Cada chave no dicionário representa um nó e o valor associado a essa chave é uma lista com todos os vizinhos do nó correspondente:

adjacency_list = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['A', 'B']
}

Alternativamente, poderíamos implementá-lo como uma lista 2D, onde cada índice representa um nó. Por exemplo, o índice 0 representa o nó A, o índice 1 representa o nó B e assim por diante:

adjacency_list = [
    ['B', 'C', 'D'],  # Neighbors of A (index 0)
    ['A', 'D'],       # Neighbors of B (index 1)
    ['A'],            # Neighbors of C (index 2)
    ['A', 'B']        # Neighbors of D (index 3)
]

Note que mesmo que esta lista 2D possa parecer semelhante à matriz de adjacência, elas são bastante diferentes. * A matriz de adjacência armazena 0s, 1s ou outros valores que representam as arestas ou os pesos das arestas no grafo. * A lista de adjacência armazena a lista real de todos os vizinhos de cada nó. Esta é uma diferença muito importante com a qual você deve estar familiarizado. Matrizes de adjacência e listas de adjacência são muito importantes para implementar grafos. A escolha entre elas depende do tamanho do grafo e de como você precisa usar os dados. Matrizes de adjacência são úteis para grafos densos com muitas arestas, enquanto listas de adjacência geralmente são a escolha preferida para cenários do mundo real, onde grafos esparsos são mais comuns.