Um grafo é uma representação gráfica de elementos de dados e das conexões ou ausência de conexões entre eles. Várias situações do mundo real podem ser representadas como grafos: diagramas de organizações, mapas rodoviários, redes em geral: sociais, energia elétrica, água e esgoto, computadores, transporte, comunicações (satélites, telefonia com fio e sem fio), entre outras aplicações.

Para representarmos um grafo de forma computacional, como estrutura de dados, na memória de um computador, os dados precisam ser organizados, há duas formas: matrizes de adjacências e listas de adjacências.

Considere a matriz de adjacências a seguir.

Matriz de Adjacências (ANEXO)

Existe um caminho de G a X, seleciona a alternativa que apresenta o comprimento do caminho mais curto e o algoritmo usado.

Alternativas:

a) Não é possível calcular porque não é um grafo valorado.

b) 3 com o algoritmo de busca em largura.

c) 4 com o algoritmo de Dijkstra.

d) 4 com o algoritmo de Kruskal.

e) 3 com o algoritmo de Prim.