2

Eu consigo achar um ciclo em um grafo não dirigido. Mas eu não consigo pensar em um jeito de listar os vértices de cada ciclo, e nem achar o menor ciclo. Como eu faço isso?

7
  • Já fez alguma coisa? Pode especificar melhor sua duvida, o que você está tentando? 15/01/2015 às 22:24
  • Estou tentando acabar o algoritmo para verificar se existe um ciclo no grafo. Eu queria listar todos os ciclos de um grafo não dirigido. E queria achar o menor ciclo desse grafo. 15/01/2015 às 22:47
  • Posso te indicar onde procurar, o livro fundamentos matemáticos para ciência da computação, Judith L Gersting.
    – pmargreff
    15/01/2015 às 22:53
  • Se bem que tenho quase certeza que é um problema NP, por que o número de caminhos é fatorial se for um grafo completo.
    – pmargreff
    15/01/2015 às 22:54
  • Valeu cara, vou dar uma olhada! 15/01/2015 às 22:55

2 Respostas 2

1

Existem diversos algoritmos, para grafos valorados, ou seja, onde cada aresta tem um peso, exemplos: Algoritmo de Dijkstra, Algoritmo de Bellman-Ford, Algoritmo A*, Algoritmo de Floyd-Warshall, Algoritmo de Johnson.

Porém como o encontro do menor caminho é um problema NP completo, as soluções são ineficientes, ou até matematicamente incalculáveis em números nem tão grandes. Se não me engano para grafos direcionados usava o algoritmo de Floyd-Warshall.

0

Primeiramente você deve dar peso 1 a todas as arestas existentes de seu grafo e peso INFINITO às arestas grafo[i][i] para todo vértice i. Também torne seu grafo pseudo-direcionado:

grafo[i][j] = 1
grafo[j][i] = 1

para quaisquer vértices i e j que estiverem conectados.

Geralmente, o peso na aresta grafo[i][i] é de 0, o que faz sentido quando você procura o caminho mais curto, já que não custa nada não se mover no grafo, mas se você mantiver dessa forma e executar os algoritmos abaixo, seu resultado final será apenas 0, já que o menor ciclo de um vértice até si mesmo vai ser sempre o caminho vértice i -> vértice i, ou seja, não se movimentar no grafo.

Dito isso, você pode executar o Algoritmo de Dijkstra para todo vértice i, usando i como o vértice inicial e final do algoritmo, ou seja, quanto custa chegar até o vértice i a partir do próprio vértice i (lembrando que a resposta não vai ser 0 porque você definiu que grafo[i][i] = INFINITO). E como os pesos das arestas são todos 1, o menor caminho lhe dará também o ciclo de menor distância. Executando esse algoritmo para todos os vértices você terá que grafo[i][i] vai ser o custo do menor ciclo no qual o vértice i está envolvido, para todo vértice i. Complexidade final O(n^3):

Dijkstra: O(n^2)
Executado n vezes, onde n é a quantidade de vértices no grafo.
Final: O(n^2) * n --> O(n^3)

Para achar o menor ciclo no grafo inteiro, execute o algoritmo acima e depois pegue min(grafo[i][i]) para todo vértice i, ou seja: pegando todos os ciclos no qual os vértices estão envolvidos, qual deles é o menor?!

E, finalmente, para listar os vértices envolvidos no menor ciclo, adicione ao algoritmo uma lista dos vértices anteriormente visitados no menor caminho (menor ciclo, nesse caso) entre quaisquer vértices i e j e retorne a lista do vértice i que fizer parte do menor ciclo encontrado por min(grafo[i][i]), como discutido acima. exemplo en.

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .