Um guia para a estrutura de dados do gráfico

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.

MAKEUSEO VÍDEO DO DIA

O que é um gráfico e o que você precisa saber sobre ele?

como acelerar um disco rígido

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 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.