Estrutura de dados eficiente para manter um gráfico

5

Link do problema - link

Na minha opinião, o problema pode ser resolvido por uma estrutura de dados, que mostra como cada número está conectado a outro e, por meio de recursão, encontra o menor valor possível. Mas a minha pergunta é: qual estrutura de dados (mais eficiente) pode conter / representar tais dados? Além disso, existe uma maneira melhor (mais rápida) de resolver esse problema.

Obrigado

    
por 7Aces 04.10.2012 / 22:36
fonte

2 respostas

2

O problema é equivalente ao problema de caminho mais curto em um gráfico, onde os vértices são dados pelo primeiro e terceiro número de cada um dos seus triplos, uma borda é dada por um triplo "conectando" dois vértices, e o peso da borda é dado pelo segundo número de cada triplo. Ele pode ser eficientemente resolvido, por exemplo, pelo algoritmo de Dijkstra . O artigo da Wikipedia lista algumas estruturas de dados de heap diferentes para gráficos que podem ser apropriados para esse algoritmo, desde que o gráfico seja "esparso".

    
por 04.10.2012 / 22:50
fonte
0

array multidimensional, também podemos chamar de matriz.

crie uma matriz decimal (digamos A) - onde n é o número do nó no gráfico. quando o nó i e j estiverem conectados, defina A[i][j] para 1 mais como 0.

    
por 23.04.2013 / 20:00
fonte