Lista 2 de exercícios (em construção)
Algoritmos e Estrutura de Dados II
Profa. Ariane Machado Lima
Lista 2 de exercícios – Grafos: implementações e outras propriedades
Implemente e teste a estrutura de dados, e as rotinas básicas para sua manipulação, para grafos direcionados utilizando matriz de adjacência.
Implemente e teste a estrutura de dados, e as rotinas básicas para sua manipulação, para grafos não-direcionados utilizando matriz de adjacência.
Implemente e teste a estrutura de dados, e as rotinas básicas para sua manipulação., para grafos direcionados utilizando lista de adjacência.
Implemente e teste a estrutura de dados, e as rotinas básicas para sua manipulação, para grafos não-direcionados utilizando lista de adjacência.
Seja um grafo g não-direcionado ponderado (com um peso inteiro associado a cada aresta). Escreva um algoritmo que, dado g e um custo mínimo int c, retorne uma cópia de g contendo apenas as arestas de custo maior do que c. Utilize apenas as rotinas da interface de grafos.
Implemente o algoritmo de busca em profundidade utilizando a interface de grafos.
Adapte o algoritmo de busca em profundidade para retornar true se o grafo é acíclico e false caso contrário. Obs: note que, para grafos não-direcionados, a aresta (u,v) NÃO implica um ciclo entre u e v.
Adapte o algoritmo anterior para, quando achar um ciclo, imprimi-lo.
Escreva uma função que, dado um grafo direcionado acíclico (DAG), imprime sua ordenação topológica.
Sejam dois grafos g1 e g2 contendo exatamente os mesmos vértices. Verifique se g2 é um subgrafo de g1, retornando true/false conforme o caso.