Resumo de Grafo e busca em largura e em profundidade

## Introdução a Grafos Olá! Você já parou para pensar como o Google Maps encontra o melhor caminho para você, ou como o Facebook sugere amigos? Por trás de muitas dessas funcionalidades complexas do dia a dia, existe uma estrutura de dados muito poderosa e elegante chamada **grafo**. Grafos nos permitem modelar e entender as conexões entre diferentes coisas. ### O que é um Grafo? Um grafo é, essencialmente, uma forma de representar objetos e as relações entre eles. Pense em cidades conectadas por estradas, pessoas conectadas por amizades, ou páginas da web conectadas por *links*. Todas essas situações podem ser representadas como um grafo. > Um **grafo** é uma estrutura de dados não linear composta por um conjunto de **vértices** (ou nós) e um conjunto de **arestas** (ou arcos), que são as conexões entre esses vértices. Imagine que cada cidade é um ponto e cada estrada que liga duas cidades é uma linha. O conjunto de todas as cidades e estradas forma um grafo. A beleza dos grafos reside na sua capacidade de simplificar e visualizar interações complexas. #### Componentes de um Grafo Todo grafo é definido por dois elementos principais: * **Vértices (V):** São os objetos ou entidades que estamos modelando. Eles são como os pontos em um mapa. Em um grafo de rede social, cada pessoa seria um vértice. * **Arestas (E):** São as conexões ou relações entre os vértices. Elas ligam um vértice a outro. Em uma rede social, uma amizade entre duas pessoas seria uma aresta. Formalmente, um grafo $G$ é definido como um par $(V, E)$, onde $V$ é um conjunto finito e não vazio de vértices, e $E$ é um conjunto de pares de vértices, representando as arestas. Fun fact: O matemático suíço Leonhard Euler é creditado por resolver o problema das Sete Pontes de Königsberg em 1736, o que é frequentemente considerado o primeiro problema resolvido na teoria dos grafos. ### Tipos de Grafos Nem todas as relações são iguais. Às vezes, a direção da conexão importa; outras vezes, as conexões têm um 'custo' ou 'peso' associado. Isso nos leva a diferentes tipos de grafos. #### Grafos Não Direcionados Em um grafo não direcionado, a conexão entre dois vértices é mútua e não tem uma direção específica. Se o vértice A está conectado ao vértice B, então B também está conectado a A, da mesma forma. * **Exemplo:** Redes de amizade no Facebook. Se você é amigo de alguém, essa pessoa também é sua amiga. A aresta não tem uma 'direção'. > Em grafos **não direcionados**, a ordem dos vértices em um par que forma uma aresta não importa. Uma aresta entre $u$ e $v$ é a mesma que entre $v$ e $u$, representada como ${u, v}$ ou $(u, v)$ (onde a ordem não implica direção). #### Grafos Direcionados (Digrafos) Em contraste, um grafo direcionado (também conhecido como digrafo) tem arestas que apontam de um vértice para outro. A relação é unilateral ou tem uma direção específica. * **Exemplo:** Seguir alguém no Twitter. Se você segue alguém, não significa necessariamente que essa pessoa o segue de volta. A aresta tem uma direção. Um sistema de ruas de mão única também é um bom exemplo. > Em grafos **direcionados** (ou **digrafos**), a ordem dos vértices em um par que forma uma aresta importa. Uma aresta de $u$ para $v$ (representada como $(u, v)$) é diferente de uma aresta de $v$ para $u$. #### Grafos Ponderados Às vezes, as conexões em um grafo não são apenas 'existentes' ou 'não existentes', mas também carregam uma informação adicional, como um custo, distância ou tempo. Essa informação é chamada de peso. * **Exemplo:** Em um mapa de estradas, o peso de uma aresta entre duas cidades pode ser a distância em quilômetros, o tempo de viagem ou o custo de pedágio. Em uma rede de computadores, o peso pode ser a latência da conexão. > Um grafo **ponderado** é aquele em que cada aresta possui um valor associado, chamado **peso**. Esse peso pode representar custo, distância, tempo, capacidade, etc. Em um grafo não ponderado, todas as arestas são consideradas d