Página Inicial

Este trabalho foi elaborado para a disciplina de Estrutura de Dados no Instituto Federal Catarinense – Campus Araquari, na turma de Bacharelado em Sistemas de Informação 5 (BSI 5). Nosso objetivo é apresentar de forma clara e concisa os conceitos fundamentais relacionados a grafos, sua representação computacional e os principais algoritmos de varredura e análise.

No decorrer deste documento, exploraremos:

• A origem histórica dos grafos e a resolução do problema das sete pontes de Königsberg por Euler;
• A definição formal de grafos, diferenciando grafos direcionados e não direcionados;
• Grafos direcionados acíclicos (DAGs) e suas aplicações em dependências e ordenação topológica;
• Grafos ponderados e algoritmos de caminho mínimo, com ênfase no algoritmo de Dijkstra;
• Grafos bipartidos e completações bi-partidas;
• As principais estruturas de representação (listas de arestas, listas de adjacência e mapas de adjacência);
• Estratégias de varredura em grafos: Busca em Largura (BFS) e Busca em Profundidade (DFS);
• Outros métodos úteis em grafos, apresentados com exemplos de código em Python.

A estrutura adotada visa não apenas descrever os conceitos teóricos, mas também ilustrar cada tópico com exemplos práticos e referências bibliográficas atualizadas, de modo a facilitar o entendimento e a aplicação dos grafos em problemas reais de computação. Ao final, são apresentados exercícios de fixação e sugestões de leituras para aprofundamento.