Este repositório foi criado para a disciplina de Grafos e Complexidade de Algoritmos, e contém implementações e estudos relacionados à teoria dos grafos. Aborda conceitos fundamentais e algoritmos utilizados na análise de grafos.
Os grafos são modelos matemáticos amplamente utilizados para representar relações entre elementos, sendo aplicáveis em diversas áreas, como redes de computadores, inteligência artificial, logística, biologia computacional, entre outras.
Neste repositório, você encontrará implementações de algoritmos clássicos em C# para manipulação de grafos, incluindo busca, percorrimento e estruturação.
A representação de um grafo pode ser feita de várias formas, sendo a lista de adjacência uma das mais eficientes em termos de espaço. Nesse método, cada vértice mantém uma lista de nós adjacentes, facilitando operações como inserção e busca de conexões. A adição de arestas conecta os vértices, permitindo a modelagem de diferentes tipos de grafos.
Implementação: C# - C
A busca em largura (BFS) é um algoritmo de percorrimento de grafos que explora todos os vértices de um nível antes de avançar para o próximo. Ele utiliza uma fila para garantir que os nós sejam visitados na ordem correta, sendo útil para encontrar o caminho mais curto em grafos não ponderados.
Implementação: C# - C
A busca em profundidade (DFS) é um algoritmo de percorrimento de grafos que explora o máximo possível de um caminho antes de retroceder. Ele utiliza uma pilha (ou recursão) para gerenciar os nós visitados, avançando profundamente por um ramo até não poder mais, e depois retornando para explorar outros caminhos.
Implementação: C# - C
Grafos conexos são grafos em que existe um caminho entre qualquer par de vértices. Em outras palavras, em um grafo conexo, é possível ir de qualquer vértice para qualquer outro, seja por meio de uma sequência de arestas ou por um caminho direto.
Implementação: C# - C