Grafos, representação, pesquisa em largura e em profundidade

  1. Considere os Grafos:

    $G1= \{\{1,2,3,4,5,6,7,8\},(1,2),(1,3),(2,6),(3,6),(3,8),$

    $(4,7),(5,6),(5,2),(5,7),(6,7),(7,3),(8,4)\}$

    $G2=\{\{0,1,2,3,4,5,6,7,8\},\{(0,2),(0,3),(1,3),(2,3),(2,5),$

    $(5,8),(6,5),(6,7),(7,8)\}$

    1. Para o grafo G1 indique qual é o resultado da pesquisa em largura (bfs), iniciada no vértice 1. i.e quais as anotações em cada nó do grafo após a pesquisa. Desenhe a árvora em largura.

    2. Para o grafo G2 indique quais as anotações nos nós feitas pela pesquisa em profundidade (dfs). Desenhe as árvores em profundidade.

  2. Usando a implementação do tad grafos dada na teórica (ficheiros grafo.c, grafo.h e grafosmain.c - grafos.tgz) e pesquisa em largura (bfs)

    1. Defina a função caminho2 que dados um grafo e dois vertices lista o menor caminho entre os dois vertices (os vertices do caminho) e a distância minima entre os dois vertices.

    2. Defina a função caminho3 que dados um grafo e três vertices (u, v, e x) lista o menor caminho entre u e v que passa por x.

  3. Usando as estruturas de dados e as funções definidas para representar grafos dadas na teorica:

    1. Implemente a função pesquisa em profundidade (dfs) dada nas aulas (acrescente int ti e int tf a struct vertice para poder anotar os tempos de visita de cada nó).

    2. Defina a função ordena vertices que dado um grafo directo sem ciclos, usando a sua função (dfs), lista uma linearização do grafo (ordenação topologica).