Esta lição introduz os fundamentos dos grafos, uma estrutura de dados abstrata essencial para modelar conjuntos de instâncias (ou objetos) e as relações entre eles. Os grafos são constituídos por vértices (ou nós), que representam as instâncias, e arestas, que indicam as relações entre esses vértices. A representação de um grafo é feita através da notação G = (V, E), onde V é o conjunto de vértices e E é o conjunto de arestas. Os grafos podem ser classificados como direcionados ou não direcionados, conectados ou desconectados, e ponderados ou não ponderados, dependendo da natureza das relações que representam.
Além disso, a lição detalha três principais estruturas de dados para representar grafos: matrizes de adjacência, listas de adjacência, e listas de arestas. Matrizes de adjacência são mais adequadas para grafos densos, onde a quantidade de arestas se aproxima do número máximo de possíveis conexões entre todos os vértices, enquanto listas de adjacência são mais eficientes para grafos esparsos, que têm significativamente menos arestas. Listas de arestas oferecem uma representação simples e direta, útil quando as relações entre vértices são mais importantes do que as propriedades individuais dos vértices.
Classificação
Lição.