Suponha que quer encontrar o caminho mais curto (de menor custo) num grafo com as características do grafo apresentado abaixo, mas que pode ter muitos mais nós e arcos.

Dado o grafo abaixo, considere que pretende encontrar os caminhos mais curtos (em número

de arestas) a partir do vértice

Assuma que o grafo é implementado

utilizando uma estrutura de dados que ordena e

Usando o algoritmo de travessia em largura (BFS), qual será a ordem de entrada dos vértices na Fila e o caminho resultante de 4 para 1.

Qual das opções representa uma ordenação topológica do grafo abaixo.

Quantas componentes fortemente conexas tem o digrafo acíclico da figura abaixo?

Considere um digrafo acíclico com seis nós, representados pelo conjunto .

Foi feita uma travessia em profundidade (DFS) neste grafo e os tempos de entrada (T_in) e de saída (T_out) de cada nó foram registados na tabela abaixo.

Qual das opções representa uma ordem topológica do grafo?

Suponha que precisa de implementar um TDA (tipo de dados abstrato) Grafo numa determinada aplicação.

Indique a opção de estrutura de dados mais adequada para a sua implementação, de modo a otimizar a gestão da memória e do tempo de inserção/remoção no grafo.

Assuma que vai efetuar uma travessia em profundidade (DFS) no grafo abaixo a partir do vértice 2 (vértice-fonte).

Indique todas as opções corretas em relação aos tempos de entrada e saída dos vértices na travessia. Considere que o tempo de entrada do vértice-fonte é 1.

• Nota: O tempo de entrada do vértice é o momento em que o vértice é descoberto pela primeira vez, e o tempo de saída é quando o vértice já não tem vizinhos "não visitados".

Suponha que precisa implementar um TDA (tipo de dados abstrato) Grafo numa determinada aplicação.

Indique a opção de estrutura de dados mais adequada para a sua implementação, sabendo que é extremamente importante minimizar o tempo gasto em pesquisas do tipo: "existe uma aresta (u,v) no grafo?".