Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos, Ordenação Topológica em Grafos, Busca em Profundidade (DFS) e…
Grafos
Tipos de Grafos
Grafo Direcionado:
Arestas têm direção.
Representa relações direcionadas entre elementos.
Grafo Não Direcionado:
Arestas não têm direção.
Modela relações bidirecionais.
Vértices (Nós):
Pontos individuais no grafo.
Arestas:
Conexões entre vértices.
Ciclos e Aciclicidade
Ciclo:
Sequência de arestas que forma um circuito fechado.
Grafo Acíclico:
Não possui ciclos.
Algoritmos Importantes
Busca em Profundidade (DFS) e Busca em Largura (BFS):
Exploração de grafos.
Ordenação Topológica:
Organização hierárquica de tarefas em DAGs.
Definição Básica:
Grafos são estruturas matemáticas que representam relações entre objetos.
Compostos por nós (vértices) e conexões entre eles (arestas).
Grafos Ponderados
Atribuição de pesos às arestas para representar custos ou distâncias.
Ordenação Topológica em Grafos
Definição
A ordenação topológica é um arranjo linear dos vértices de um grafo direcionado acíclico (DAG) de tal forma que, para cada aresta dirigida uv, o vértice u aparece antes de v na ordenação.
Aplicações
Utilizada em tarefas que possuem dependências, como compilação de programas, planejamento de projetos, entre outros.
Algoritmo (DFS)
Passo a passo
Inicialize uma lista vazia para armazenar a ordenação topológica.
Marque todos os vértices como não visitados.
Para cada vértice não visitado, chame a função topological_sort_util.
Na função topological_sort_util, marque o vértice como visitado e chame recursivamente a função para seus vizinhos não visitados.
Adicione o vértice à frente da lista de ordenação.
A ordenação topológica fornece uma sequência linear que respeita as dependências direcionadas entre os vértices, sendo uma ferramenta crucial em diversos domínios, especialmente em tarefas de planejamento e organização de dados.
Busca em Profundidade (DFS) e Busca em Largura (BFS) em Grafos
Busca em Profundidade (DFS)
Definição: DFS é um algoritmo para percorrer ou pesquisar em árvores e grafos.
Estratégia:
Começa de um nó inicial e explora o máximo possível ao longo de cada ramificação antes de retroceder.
Implementação:
Utiliza uma abordagem recursiva ou uma pilha para armazenar os nós a serem explorados.
Aplicações:
Determinar a existência de caminhos, encontrar componentes conectados, topologia em DAGs, entre outros.
Busca em Largura (BFS)
Definição: BFS é um algoritmo para percorrer ou pesquisar em árvores e grafos.
Estratégia:
Explora todos os vizinhos de um nó antes de seguir para os vizinhos do próximo nível.
Implementação:
Utiliza uma fila para armazenar os nós a serem explorados.
Aplicações:
Encontrar o caminho mais curto, navegação em mapas, resolução de quebra-cabeças, entre outros.