algorithm - オイラーパスを見つけるアルゴリズムを探しています

Question

グラフ内のオイラー パスを見つけるアルゴリズムを探しています。

数週間前に良いものを見たことがありますが、今は見つけられません。タグ付けされたエッジ、偶数/奇数接続の何かがあったことを覚えています...

同様のシンプルで簡単なアルゴリズムを知っていますか?

Answer 1

Hierholzer のアルゴリズムは、有向グラフでオイラー パスを見つけるための優れた方法です。

http://stones333.blogspot.com/2013/11/find-eulerian-path-in-directed-graph.html

コードとテストケースが含まれています。

Answer 2

これが私の解決策です。「スタックが空です」という例外が発生し、実際にそれを修正する時間がないため、最終的にブロックを使用して印刷しました。これが誰かに役立つことを願っています！

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();            
    }