歐拉一筆畫問題：圖論判定與 C# 實現

問題本質

給定無向圖的邊列表（二元組），判斷是否存在「一筆畫」路徑（歐拉路徑）：恰好遍歷所有邊且不重複。根據歐拉定理：

• 連通圖存在歐拉路徑 ⇔ 奇度頂點數為 0 或 2。
• 奇度頂點 0 為歐拉回路（閉合），2 為歐拉路徑（不閉合）。

判定算法

1. 統計每個頂點的度（出現次數）。
2. 計算奇度頂點個數。
3. 返回 oddCount == 0 || oddCount == 2。

注意：需先確認圖連通，否則直接返回 false。本題假設輸入為連通圖。

C# 完整實現

using System;
using System.Collections.Generic;
using System.Linq;

public class EulerPath
{
    public static bool HasEulerPath(string input)
    {
        if (string.IsNullOrWhiteSpace(input)) return false;
        
        // 解析邊：支持空格、換行、逗號分隔
        var edges = input.Split(new[] {' ', '\r', '\n', '\t'}, StringSplitOptions.RemoveEmptyEntries)
                         .Select(s => s.Split(','))
                         .Where(p => p.Length == 2)
                         .Select(p => (p[0], p[1]));
        
        // 統計度
        var degree = new Dictionary<string, int>();
        foreach (var (u, v) in edges)
        {
            degree[u] = degree.GetValueOrDefault(u) + 1;
            degree[v] = degree.GetValueOrDefault(v) + 1;
        }
        
        // 計算奇度頂點數
        int oddCount = degree.Values.Count(d => d % 2 == 1);
        return oddCount == 0 || oddCount == 2;
    }
    
    // 進階：同時返回路徑類型
    public static (bool hasPath, string type) Analyze(string input)
    {
        bool has = HasEulerPath(input);
        if (!has) return (false, "非歐拉圖");
        
        var edges = input.Split(new[] {' ', '\r', '\n', '\t'}, StringSplitOptions.RemoveEmptyEntries)
                         .Select(s => s.Split(','))
                         .Where(p => p.Length == 2)
                         .Select(p => (p[0], p[1]));
        var degree = new Dictionary<string, int>();
        foreach (var (u, v) in edges)
        {
            degree[u] = degree.GetValueOrDefault(u) + 1;
            degree[v] = degree.GetValueOrDefault(v) + 1;
        }
        int odd = degree.Values.Count(d => d % 2 == 1);
        return odd == 0 ? (true, "歐拉回路") : (true, "歐拉路徑");
    }
}

// 測試
var tests = new[]
{
    "a,b b,c b,d d,e d,f",      // 工字形：4奇點 → false
    "a,b b,c c,a",              // 三角形：0奇點 → 回路
    "a,b a,c b,d c,d c,e d,f e,f" // 8字形：2奇點 → 路徑
};

foreach (var t in tests)
    Console.WriteLine($"{t,-35} => {EulerPath.Analyze(t)}");

輸出結果

a,b b,c b,d d,e d,f            => (False, 非歐拉圖)
a,b b,c c,a                    => (True, 歐拉回路)
a,b a,c b,d c,d c,e d,f e,f    => (True, 歐拉路徑)

多筆畫擴展

若圖不可一筆畫，最少筆數 = max(1, 奇度頂點數 / 2)。

public static int MinStrokes(string input)
{
    var edges = input.Split(new[] {' ', '\r', '\n', '\t'}, StringSplitOptions.RemoveEmptyEntries)
                     .Select(s => s.Split(','))
                     .Where(p => p.Length == 2)
                     .Select(p => (p[0], p[1]));
    var degree = new Dictionary<string, int>();
    foreach (var (u, v) in edges)
    {
        degree[u] = degree.GetValueOrDefault(u) + 1;
        degree[v] = degree.GetValueOrDefault(v) + 1;
    }
    int odd = degree.Values.Count(d => d % 2 == 1);
    return Math.Max(1, odd / 2);
}

構建實際路徑

判定只是第一步，若需輸出具體繪筆順序，使用 Fleury 算法 或 Hierholzer 算法（O(E)）。Hierholzer 步驟：

1. 從任意頂點（奇度圖選奇度點）開始 DFS。
2. 走過邊即刪除，遞歸深入。
3. 回溯時將頂點加入結果棧，最終反轉得路徑。

總結

歐拉一筆畫判定核心是「統計奇度頂點」，C# 實現極其簡潔。掌握 Hierholzer 算法可進一步輸出具體路徑，應用於繪圖軟件、PCB 布線、基因組裝等領域。