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?
-
Já fez alguma coisa? Pode especificar melhor sua duvida, o que você está tentando?– Fernando LealCommented 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.– SakataGintokiCommented 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.– pmargreffCommented 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.– pmargreffCommented 15/01/2015 às 22:54
-
Valeu cara, vou dar uma olhada!– SakataGintokiCommented 15/01/2015 às 22:55
2 Respostas
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.
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.