Grafos são estruturas de dados usadas para representar as conexões ou relacionamentos entre objetos ou entidades. Eles são frequentemente usados para modelar redes. Os tipos de redes que você pode modelar com um grafo incluem redes sociais, redes de transporte, redes de comunicação e até sistemas de recomendação. Por exemplo, grafos podem representar conexões entre usuários em uma plataforma de mídia social ou conexões entre cidades em uma rede rodoviária. Eles são muito versáteis. Um grafo é frequentemente representado como uma coleção de pontos ou círculos conectados por linhas. Esses círculos e linhas representam os dois componentes principais de um grafo: nós e arestas. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-1.png" alt="A simple graph showing five nodes labeled A, B, C, D, and E connected by edges. Node A connects to B, B connects to A, C, and D, C connects to B and D, D connects to B, C, and E, and E connects to D."> Nodos, também conhecidos como vértices, representam os objetos ou entidades que fazem parte da rede modelada pelo grafo. Eles podem ser usuários, produtos, estações, cidades ou quaisquer outras entidades no modelo. Neste exemplo, os nós são representados como círculos e rotulados com as letras A, B, C, D e E para distingui-los visualmente. Edges são as conexões entre os nós. Se dois nós estão conectados por uma aresta, isso significa que eles estão de alguma forma conectados na rede. Neste exemplo, há cinco arestas conectando os diferentes pares de nós. O nó A está conectado ao nó B. O nó B está conectado aos nós A, C e D e assim por diante. O significado específico da conexão dependerá do contexto. Pode ser física, como uma estrada real que conecta duas cidades, ou pode ser mais abstrata, como a conexão entre dois usuários em uma plataforma de mídia social. Se dois nós estão diretamente conectados por uma aresta, como os nós A e B neste exemplo, eles são conhecidos como nós adjacentes. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-2.png" alt="The same graph with nodes A and B highlighted to illustrate adjacent nodes - two nodes that are directly connected by an edge.">

Tipos de Grafos

Existem diferentes tipos de gráficos com características e aplicações diferentes. Vamos analisar alguns deles.

Grafos Não Direcionados

Grafos não direcionados são grafos onde as arestas não têm uma direção específica. Esse tipo de aresta é geralmente representado por uma linha reta entre os nós. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-1.png" alt="An example of an undirected graph where all edges are represented as straight lines without arrows, demonstrating that connections work in both directions between nodes."> Isso significa que, se houver uma aresta conectando os nós A e B, a conexão funciona em ambas as direções: do nó A para o nó B e do nó B para o nó A. Dependendo da rede que está sendo modelada pelo grafo, essa conexão pode ter significados diferentes. Por exemplo, se você está modelando conexões entre usuários de uma plataforma de mídia social, isso significa que o usuário A está conectado ao usuário B e o usuário B está conectado ao usuário A. A conexão é bidirecional.

Grafos Dirigidos

Em contraste, grafos direcionados são grafos onde as arestas têm uma direção específica. Se houver uma conexão do nó A para o nó B, isso não implica necessariamente que haja uma conexão do nó B para o nó A. As arestas de um grafo direcionado são frequentemente representadas como linhas retas que terminam com uma seta para indicar a direção. Aqui está um exemplo. Neste gráfico, você pode ir do nó A para o nó B mas não do nó B para o nó A por causa da direção da aresta. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-4.png" alt="A directed graph example showing the same nodes as before but with arrows indicating specific one-way connections: from A to B, B to C, C to D, D to B, and D to E, demonstrating unidirectional edges."> Por exemplo, se você estiver modelando uma rede rodoviária, isso seria útil para modelar ruas ou estradas de mão única. Você pode ir da cidade A para a cidade B através daquela estrada, mas não da cidade B para a cidade A. Você precisará pegar uma rota diferente. Se houver uma conexão bidirecional entre os nós de um grafo direcionado, você pode representar isso com duas arestas direcionadas entre eles. Aqui você pode ver um exemplo. Você pode ir do nó B para o nó D e do nó D para o nó B porque existem duas arestas conectando-os, mas cada aresta tem uma direção. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-5.png" alt="A directed graph showing bidirectional connection between nodes B and D with two arrows, one pointing from B to D and another from D to B.">

Grafos Rotulados por Vértice

Um grafo rotulado por vértice é um grafo no qual cada nó está associado a um rótulo ou identificador além dos seus dados. Esses rótulos são usados para identificar os nós, representá-los visualmente e armazenar informações adicionais sobre eles. Por exemplo, em um grafo de rede de transporte, os nós poderiam ser cidades e seus rótulos poderiam ser seus nomes, coordenadas ou qualquer outra característica que fosse útil para os propósitos do modelo.

Grafos Cíclicos

Grafos cíclicos são grafos direcionados com pelo menos um ciclo. Um cycle é um caminho que você pode seguir pelas arestas de um grafo que o levará de volta ao nó inicial onde você começou. Neste exemplo, temos um grafo direcionado. Se você olhar mais de perto, notará que ele tem um ciclo. Se começarmos no nó B, formos para o nó C e depois para o nó D, podemos voltar para o nó B novamente através das arestas direcionadas. Isto é um ciclo, então isto é um grafo cíclico. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-6.png" alt="A directed graph showing a cycle where you can start at node B, go to node C, then to node D, and back to node B, forming a complete cycle.">

Grafos Rotulados por Aresta

Em grafos com arestas rotuladas, as arestas estão associadas a rótulos. Esses rótulos geralmente são desenhados ao lado de suas arestas correspondentes.

Grafos Ponderados

Grafos ponderados são um tipo específico de grafo rotulado por arestas em que os rótulos nas arestas representam valores que podem ser comparados e usados para realizar operações aritméticas. Algumas arestas têm um peso maior, enquanto outras têm um peso menor. Esses pesos representam o "custo" da aresta. Por exemplo, eles podem representar a distância entre duas cidades ou o tempo que leva para ir de uma cidade para a outra. Este é um exemplo de um grafo ponderado. Escrevemos cada peso ao lado da sua aresta correspondente. O "custo" de ir do nó B para o nó D é 3 e, como este é um grafo não direcionado, esse é o mesmo custo de ir do nó D de volta para o nó B. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-7.png" alt="A weighted graph showing nodes connected by edges with numerical weights labeled next to each edge, such as weight 3 between nodes B and D.">

Grafo Acíclico Dirigido

Outro tipo muito comum de grafo em ciência da computação é o directed acyclic graph, que é um grafo direcionado sem ciclos. Aqui está um exemplo. É um grafo direcionado porque cada aresta tem uma direção. É acíclico porque não possui ciclos. Por quê? Note que, se você começar em um nó específico, não poderá voltar a ele por causa da direção das arestas. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-8.png" alt="A directed acyclic graph (DAG) with connections from A to B, B to C, B to D, C to D, and D to E, demonstrating how the directional flow prevents any cycles from forming.">

Grafo Desconectado

E o último tipo de grafo que abordaremos nesta lição é o disconnected graph. Um grafo desconectado é um grafo com dois ou mais grupos de nós que não estão conectados por nenhuma aresta. Um exemplo do mundo real seria uma rede social, onde você tem dois ou mais grupos de pessoas que não se conhecem e que não têm amigos em comum. Este é um exemplo. O primeiro componente tem os nós A, B e C. O segundo componente tem os nós D e E. Esses componentes não têm nenhuma aresta entre eles, então este é um grafo desconectado. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/what-are-graphs-in-computer-science-9.png" alt="A disconnected graph showing two separate components: the first component has nodes A, B, and C connected in sequence (A connects to B, B connects to C), and the second component has nodes D and E connected to each other, with no connections between the two components."> Você pode implementar grafos de várias maneiras, incluindo conjuntos, funções e arrays. Você aprenderá mais sobre isso nas próximas lições. Entender gráficos e as características dos diferentes tipos de gráficos é essencial para resolver uma ampla variedade de problemas em ciência da computação e outras áreas.