La recherche de l'algorithme de trouver euler chemin

De Graph-Magics.com, pour un graphe non-dirigé, ce qui vous donnera le tour dans le sens inverse, c'est à dire à partir de la fin de vertex pour le début de vertex:

1. Commencer avec une pile vide et le vide du circuit (chemin eulérien).
   • Si tous les sommets ont même degré: choisir l'un d'eux. Ce sera l'actuel sommet.
   • Si il y a exactement 2 sommets ayant un degré impair: choisir l'un d'eux. Ce sera l'actuel sommet.
   • Sinon pas d'Euler-circuit ou de chemin d'accès existe.

Répétez l'étape 2 jusqu'à ce que le sommet n'a pas plus de voisins et de la pile est vide.

1. Si le sommet n'a pas de voisins:
   • Ajouter à circuit,
   • Supprimer le dernier sommet de la pile et de le définir comme l'actuel.

Autrement:

• Ajouter le sommet de la pile,
• Prendre ses voisins, retirez l'arête entre sélectionnés voisin et que le sommet, et de définir ce voisin que l'actuel sommet.

OriginalL'auteur MJW

Je n'ai pas de code dans n'importe quelle langue, mais je sais algorithme, comment les trouver et je vais l'écrire ici.

Supposons que nous avons graphe ayant n nœuds. Nous appelons le degré d'un nœud nombre d'arêtes connectées à ce nœud. Au premier abord, nous devons dire que la somme des degrés de chaque nœud serait même selon la "poignée de main" du problème.

Supposons maintenant que nous avons quelques Euler chemin p, à partir du nœud s et se terminant vers le nœud f. Ensuite, pour chaque nœud, qui est différente de st et t, chaque fois que nous entrons dans ce nœud, nous devrions les laisser(si nous ne pars pas, alors on ne pourra pas accéder à la grande finale f nœud), donc pour ces nœuds de degré devrait être de même, et pour s et f, si elles sont différentes degré serait étrange, car nous gauche s à la première fois, et puis après chaque entrée, nous avons quitté le s nœud, donc, il y aurait 1 + 2*degré n, où n est le nombre de fois où nous avons visité s à nouveau. En va de même pour f. Donc, il devrait y avoir 2 nœuds avec odd degré si il existe d'Euler chemin. Et si il y a le cercle d'Euler, puis degré de chaque nœud doit être de même, et si c'est le cas, alors il n'a pas d'importance qui nœud de nous choisir comme s, nous mettrons fin à la cercle en s aussi.

Maintenant le problème est de savoir comment obtenir du cercle d'Euler/chemin d'accès. Ici, nous avons besoin de définir le "pont" dans le graphique. Le pont est une arête de propriété spécifique, si on supprime ce bord, puis dans le reste du graphique le nombre de composants augmente d'une unité. En d'autres termes, le bridge est un avantage qui est la seule connexion de bord pour les deux composants dans le graphique.

Puisque nous savons ce qui est du pont, on peut définir l'algorithme. S'il y a exactement 2 nœuds avec le même degré:
1) nous partons de l'un d'eux et aller de l'avant à la prochaine nœuds en choisissant les bords connecté au nœud actuel.
2) si l'on ne devait choisir lisière entre le pont et nonbridge, on doit toujours choisir nonebridge.
3) si il y a le nœud nonebridge bord gauche, alors seulement nous pouvons choisir n'importe quel pont.

Si il n'y a pas de nœud de degré impair, alors nous pouvons commencer à partir de n'importe quel nœud et suivre ces 3 règles.

C'est l'ensemble de l'algorithme qui fonctionne toujours.
voici quelques liens utiles également.

https://www.math.ku.edu/~jmartin/cours/math105-F11/Conférences/chapitre 5-part2.pdf
http://www.graph-magics.com/articles/euler.php

OriginalL'auteur Mamuka

Soo c'est ma solution , j'ai utilisé le bloc finally pour imprimer parce que je suis d'exception "de la pile est vide" et je n'ai pas vraiment le temps de corriger cela. J'espère que cela aide quelqu'un!

public void EulerTour()
    {
        GetInput(); //gets the adjency matrix

        int start = NodeList[0]; //start from any vertex, i choose 0
        tempPath.Push(NodeList[0]); //temporary path - stack
        try
        {
            while (tempPath.Count != 0) 
            {
                for (int i = 0; i < total; i++)
                {
                    if (adjencyMatrix[start, i] == 'd')
                    {
                        tempPath.Push(NodeList[i]);
                        adjencyMatrix[start, i] = 'n';
                        adjencyMatrix[i, start] = 'n';

                        if (!hasNeighbour((int)tempPath.Peek())) //checks if current node has any neighbour
                        {
                            while (!hasNeigbour((int)tempPath.Peek()))
                            {
                                finalPath.Push(tempPath.Pop());

                            }
                            start = (int)tempPath.Peek();
                        }
                        else
                        {
                            start = i;
                            break;
                        }
                    }
                }
            }
        }
        catch
        {
            Console.WriteLine("Print: ");
        }
        finally
        {
            foreach (object o in finalPath)
            {
                Console.Write(o.ToString() + "---->");
            }
        }     
        Console.ReadKey();            
    }

OriginalL'auteur Jure Kljajic