Um programador eficaz precisa de uma sólida compreensão de estruturas de dados e algoritmos. As entrevistas técnicas geralmente testam suas habilidades de resolução de problemas e pensamento crítico.
Os gráficos são uma das muitas estruturas de dados importantes na programação. Na maioria dos casos, entender gráficos e resolver problemas baseados em gráficos não é fácil.
O que é um gráfico e o que você precisa saber sobre ele?
O que é um gráfico?
Um grafo é uma estrutura de dados não linear que possui nós (ou vértices) com arestas que os conectam. Todas as árvores são subtipos de grafos, mas nem todos os grafos são árvores, e o grafo é a estrutura de dados da qual as árvores se originaram.
Embora você possa construir estruturas de dados em JavaScript e outras linguagens, você pode implementar um gráfico de várias maneiras. As abordagens mais populares são listas de borda, listas de adjacência, e matrizes de adjacência.
o Guia da Khan Academy para representar gráficos é um ótimo recurso para aprender sobre como representar um gráfico.
Existem muitos tipos diferentes de gráficos. Uma distinção comum é entre dirigido e não direcionado gráficos; estes surgem muito em desafios de codificação e usos na vida real.
Tipos de gráficos
- Gráfico direcionado: Um grafo no qual todas as arestas têm uma direção, também conhecido como dígrafo.
- Gráfico não direcionado: Um grafo não direcionado também é conhecido como grafo de duas vias. Em grafos não direcionados, a direção das arestas não importa, e a travessia pode ir em qualquer direção.
- Gráfico ponderado: Um grafo ponderado é um grafo cujos nós e arestas têm um valor associado. Na maioria dos casos, esse valor representa o custo de explorar esse nó ou borda.
- Gráfico finito: Um grafo que tem um número finito de nós e arestas.
- Gráfico infinito: Um grafo que tem uma quantidade infinita de nós e arestas.
- Gráfico trivial: Um grafo que tem apenas um nó e nenhuma aresta.
- Gráfico simples: Quando apenas uma aresta conecta cada par de nós de um grafo, ele é chamado de grafo simples.
- Gráfico nulo: Um grafo nulo é um grafo que não possui arestas conectando seus nós.
- Multigrafo: Em um multigrafo, pelo menos um par de nós tem mais de uma aresta conectando-os. Em multigrafos, não há auto-loops.
- Gráfico completo: Um grafo completo é um grafo no qual cada nó se conecta a todos os outros nós do grafo. Também é conhecido como um gráfico completo.
- Pseudo gráfico: Um grafo que tem um auto-loop além de outras arestas do grafo é chamado de pseudografo.
- Gráfico normal: Um grafo regular é um grafo onde todos os nós têm graus iguais; ou seja, cada nó tem o mesmo número de vizinhos.
- Gráfico conectado: Um grafo conectado é simplesmente qualquer grafo no qual quaisquer dois nós se conectam; ou seja, um grafo com pelo menos um caminho entre cada dois nós do grafo.
- Gráfico desconectado: Um grafo desconectado é o oposto direto de um grafo conectado. Em um grafo desconectado, não há arestas ligando os nós do grafo, como em um grafo nulo gráfico.
- Gráfico cíclico: Um gráfico cíclico é um gráfico que contém pelo menos um ciclo gráfico (um caminho que termina onde começou).
- Gráfico acíclico: Um grafo acíclico é um grafo sem ciclos. Pode ser dirigido ou não dirigido.
- Subgráfico: Um subgrafo é um gráfico derivado. É um grafo formado por nós e arestas que são subconjuntos de outro grafo.
UMA ciclo em um grafo é uma aresta que começa em um nó e termina no mesmo nó. Portanto, um auto-loop é um loop sobre apenas um nó do grafo, como visto em um pseudografo.
Algoritmos de Travessia de Gráficos
Sendo um tipo de estrutura de dados não linear, percorrer um gráfico é bastante complicado. Atravessar um grafo significa percorrer e explorar cada nó dado que existe um caminho válido através das arestas. Os algoritmos de travessia de grafos são principalmente de dois tipos.
- Pesquisa em largura (BFS): A busca em largura é um algoritmo de travessia de grafos que visita um nó do grafo e explora seus vizinhos antes de ir para qualquer um de seus nós filhos. Embora você possa começar a percorrer um gráfico a partir de qualquer nó selecionado, o nó raiz geralmente é o ponto de partida preferido.
- Pesquisa em profundidade (DFS): Este é o segundo maior algoritmo de travessia de grafos. Ele visita um nó do grafo e explora seus nós filhos ou ramificações antes de prosseguir para o próximo nó - ou seja, indo fundo primeiro antes de ir largo.
A busca em largura é o algoritmo recomendado para encontrar caminhos entre dois nós o mais rápido possível, especialmente o caminho mais curto.
A pesquisa em profundidade é mais recomendada quando você deseja visitar todos os nós do gráfico. Ambos os algoritmos de travessia funcionam bem em qualquer caso, mas um pode ser mais simples e mais otimizado que o outro em cenários selecionados.
Uma ilustração simples pode ajudar a entender melhor os dois algoritmos. Pense nos estados de um país como um gráfico e tente verificar se dois estados, X e S, estão conectados. Uma busca em profundidade pode percorrer um caminho quase ao redor do país sem perceber cedo o suficiente que S está a apenas 2 estados de distância X.
A vantagem de uma busca em largura é que ela mantém a proximidade do nó atual o máximo possível antes de ir para o próximo. Ele encontrará a conexão entre X e S em pouco tempo sem ter que explorar todo o país.
Outra grande diferença entre esses dois algoritmos está na maneira como eles são implementados no código. A busca em largura é uma algoritmo iterativo e faz uso de um fila, enquanto uma busca em profundidade geralmente é implementada como um algoritmo recursivo que alavanca o pilha.
Abaixo está algum pseudocódigo demonstrando a implementação de ambos os algoritmos.
Pesquisa em largura
bfs (Gráfico G, raiz GraphNode) {
deixar q ser novo Fila// marca root como visitado
root.visit = verdadeiro// adiciona root na fila
q.enfileirar(raiz)
enquanto (q não é vazio) {
deixar atual seja q.dequeue() // remove o elemento da frente na fila
para (vizinhos n da corrente em G) {
E se (n énão ainda visitado) {
// adiciona à fila - para que você possa explorar seus vizinhos também
q.enfileirar(n)
n.visitado = verdadeiro
}
}
}
}
Pesquisa em profundidade
dfs (Gráfico G, raiz GraphNode) {
// caso base
E se (raiz é nulo) Retorna// marca root como visitado
root.visit = verdadeiro
para (vizinhos n da raiz em G)
E se (n énão ainda visitado)
dfs (G, n) // chamada recursiva
}
Alguns outros algoritmos de travessia de grafos derivam de pesquisas em largura e em profundidade. Os mais populares são:
- Pesquisa bidirecional: Este algoritmo é uma maneira otimizada de encontrar o caminho mais curto entre dois nós. Ele usa duas pesquisas em largura que colidem se houver um caminho.
- Classificação topológica: Isso é usado em gráficos direcionados para classificar os nós na ordem desejada. Você não pode aplicar uma classificação topológica a gráficos não direcionados ou gráficos com ciclos.
- Algoritmo de Dijkstra: Este também é um tipo de BFS. Também é usado para encontrar o caminho mais curto entre dois nós em um gráfico direcionado ponderado, que podem ter ciclos ou não.
Perguntas comuns da entrevista com base em gráficos
Os gráficos estão entre os mais importantes estruturas de dados que todo programador deveria conhecer. Muitas vezes surgem perguntas sobre esse tópico em entrevistas técnicas, e você pode encontrar alguns problemas clássicos relacionados ao tópico. Estes incluem coisas como os problemas do "juiz da cidade", "número de ilhas" e "caixeiro viajante".
Estes são apenas alguns dos muitos problemas populares de entrevistas baseadas em gráficos. Você pode experimentá-los em Código Leet, HackerRank, ou GeeksforGeeks.
Noções básicas sobre estruturas e algoritmos de dados de gráficos
Os gráficos não são úteis apenas para entrevistas técnicas. Eles também têm casos de uso do mundo real, como em redes, mapas, e sistemas de companhias aéreas para encontrar rotas. Eles também são usados na lógica subjacente dos sistemas de computador.
Os gráficos são excelentes para organizar dados e nos ajudar a visualizar problemas complexos. Os gráficos só devem ser usados quando absolutamente necessário, para evitar problemas de complexidade de espaço ou memória.
