Se você já programa há tempo suficiente, já ouviu falar sobre o conceito de grafo. É um conteúdo obrigatório para um diploma em ciência da computação, e muitas empresas de alto nível testam a compreensão da teoria dos grafos durante entrevistas técnicas . No entanto, você não precisa estar trabalhando em problemas avançados para utilizar os conceitos. Vamos revisar por que os gráficos são estruturas de dados populares e como você pode implementá-los no código.
Modelos relacionais
Independentemente da experiência em codificação, você deve estar familiarizado com os tipos de dados de matrizes e dicionários. Essas coleções são conceitos padrão usados na maioria dos idiomas e funcionam muito bem ao apresentar conteúdo baseado em lista:
Na maioria das vezes, as listas são a solução perfeita para apresentar informações de um banco de dados ou de uma consulta baseada em REST. No entanto, há momentos em que uma lista precisa fornecer contexto sobre como os registros se relacionam entre si. É quando organizar os dados como um gráfico se torna útil.
Com gráficos, o objetivo principal não é listar informações (embora totalmente possível), mas definir o relacionamento entre objetos. Por que isso seria útil?
Um grafo não direcionado com dois vértices e uma aresta.
Aplicativos de mapeamento : como você organizaria os dados necessários para recriar um serviço de mapeamento como Apple ou Google Maps, se solicitado em uma entrevista técnica? Mais do que apenas fornecer uma lista de todas as estradas conhecidas em um banco de dados, seu modelo precisaria determinar a melhor maneira de chegar a um destino com base na hora do dia, tráfego e ruas de mão única, entre outros fatores. Para que esse volume considerável de dados seja eficaz, você precisa saber como uma única estrada se relaciona com todas as outras ruas do modelo.
Mídias sociais: o sucesso nas mídias sociais geralmente é medido pelo número de pessoas que você segue ou que seguem você. Plataformas de rede como o Twitter atraem um grande público, permitindo que você se conecte com qualquer pessoa, permitindo que você receba as atualizações mais recentes. O modelo do LinkedIn é mais detalhado, pois você não pode adicionar alguém à sua rede, a menos que o destinatário aceite sua solicitação de conexão. Nesse caso, as conexões do LinkedIn representam relacionamentos de mão dupla . Levando essa ideia adiante, você também pode pesquisar para ver se alguém em sua rede está conectado a uma oportunidade de trabalho que você deseja buscar. Neste caso, “rede” pode implicar uma conexão direta ou indireta. Um modelo tão robusto não se baseia apenas em uma lista simples, mas incluiria a inteligência para determinar como todos os perfis se relacionam.
Componentes do gráfico
Agora que vimos como os gráficos são usados em aplicações cotidianas, vamos apresentar seus componentes. Os nós em um grafo são chamados de vértices. Embora seja possível construir um grafo como um único vértice, os modelos que contêm vários vértices representam melhor as aplicações do mundo real. Objetos de gráfico se relacionam entre si por meio de conexões chamadas arestas. Dependendo de seus requisitos, um vértice pode ser conectado a uma ou mais coisas por meio de arestas. Também é possível criar um vértice sem arestas. Finalmente, ao contrário de outras estruturas padrão, como pilhas ou filas, os gráficos geralmente não têm um ponto inicial ou final designado. Aqui estão alguns exemplos de configurações de gráfico:
Um grafo não direcionado com dois vértices e uma aresta.
Um grafo não direcionado com quatro vértices e três arestas.
Um grafo não direcionado com três vértices e três arestas.
Dirigido vs. não dirigido
Em um grafo não direcionado, a conexão entre um vértice de origem e um destino são iguais. Esses modelos representam conexões de mão dupla – semelhantes a uma via de mão dupla no aplicativo de mapeamento. Para definir uma conexão em uma única direção, podemos atualizar nosso modelo para um grafo direcionado usando linhas e setas:
Um grafo direcionado com três vértices e três arestas.
Nível de conectividade
Às vezes, devemos representar o nível de conectividade entre os vértices em um grafo. Essa técnica funciona bem ao quantificar distâncias, tempos ou gravidade entre nós. Geralmente associado a uma aresta, o peso é uma variável comparativa rastreada para esse fim.
Um grafo direcionado com três vértices e três arestas onde as arestas são ponderadas.
Vértice do gráfico
Com um entendimento básico da teoria dos grafos, vamos ver como replicar alguns desses modelos em código. Abaixo, criamos um vértice que suporta um objeto genérico personalizado ( T). A tvaluevariável representa os dados mantidos pelo tipo, incluindo uma única string, int ou tipo personalizado (por exemplo, nome da rua ou perfil de mídia social). Além disso, observe que nossa classe está em conformidade com o popular protocolo Equatable (Swift). Isso nos permitirá comparar instâncias de vértices específicas para igualdade, se necessário.
public class Vertex <T> : Equatable {
var tvalue: T?
var neighbors = Array<Edge<T>>()
let uuid = UUID()
public init(with name: T) {
self.tvalue = name
}
//equatable conformance
public static func == (lhs: Vertex, rhs: Vertex) -> Bool {
return lhs.uuid == rhs.uuid
}
}
Listas de adjacência
A propriedade de vizinhos representa as conexões feitas com outros vértices. Conforme discutido, cada vértice pode se conectar a um ou mais vizinhos. Essa lista de relacionamentos às vezes é chamada de “lista de adjacências” e pode ser usada para resolver muitos problemas avançados.
var neighbors = Array<Edge<T>>()
Borda do gráfico
Adicionamos uma propriedade vizinha para armazenar uma matriz de tipos de aresta personalizados ao criar nosso vértice. Abaixo, uma aresta fornece uma referência para um vértice vizinho subsequente e seu valor potencial de peso da aresta.
public class Edge <T> {
var neighbor: Vertex<T>
var weight: Int
init() {
weight = 0
self.neighbor = Vertex<T>()
}
}
Construindo a tela
Com nossos objetos de vértice e borda no lugar, agora podemos adicioná-los à nossa estrutura de armazenamento central que chamaremos de tela do gráfico. Mesmo que nossa tela seja tecnicamente um array, o objetivo é visualizar a coleção como um conjunto de relacionamentos. A addVertexfunção nos permite adicionar um único vértice genérico à tela, enquanto o addEdgemétodo fornece informações de referência necessárias para uma aresta. Por fim, nosso código assume que o grafo é direcionado, pois a aresta é (apenas) adicionada à lista de adjacência do vértice de origem.
public class Graph <T> {
var canvas: Array<Vertex<T>>
public init() {
canvas = Array<Vertex>()
}
//add vertex to graph canvas
public func addVertex(element: Vertex<T>) {
canvas.append(element)
}
/add edge
public func addEdge(source: Vertex<T>, neighbor: Vertex<T>, weight: Int) {
//create a new edge
let newEdge = Edge<T>()
//connect source vertex to neighboring edge
newEdge.neighbor = neighbor
newEdge.weight = weight
source.neighbors.append(newEdge)
}
}
Em resumo, introduzimos gráficos e vimos como eles são usados para representar o relacionamento entre objetos. Também revisamos algumas maneiras de configurar um gráfico e os componentes usados para descrever diferentes modelos. Com nosso modelo definido, preparamos o cenário para funcionalidades mais avançadas, incluindo navegação em grafos e algoritmos de travessia, como busca em largura.
