欧拉路径与哈密顿路径¶

概述¶

欧拉路径和哈密顿路径是图中两种重要的路径问题。欧拉路径要求经过每条边恰好一次，哈密顿路径要求经过每个顶点恰好一次。

欧拉路径¶

定义¶

欧拉路径：经过图中每条边恰好一次的路径
欧拉回路：起点和终点相同的欧拉路径
欧拉图：存在欧拉回路的图

判定定理¶

无向图： - 欧拉回路：所有顶点度数为偶数 - 欧拉路径：恰好两个顶点度数为奇数

有向图： - 欧拉回路：每个顶点入度等于出度 - 欧拉路径：一个顶点出度=入度+1（起点），一个顶点入度=出度+1（终点），其余入度=出度

Hierholzer算法¶

C
#define MAX_V 1000
#define MAX_E 10000

typedef struct {
    int adj[MAX_V][MAX_V];
    int degree[MAX_V];
    int vertexCount;
    int edgeCount;
} EulerGraph;

void initEulerGraph(EulerGraph *g, int n) {
    g->vertexCount = n;
    g->edgeCount = 0;
    
    for (int i = 0; i < n; i++) {
        g->degree[i] = 0;
        for (int j = 0; j < n; j++) {
            g->adj[i][j] = 0;
        }
    }
}

void addEulerEdge(EulerGraph *g, int u, int v) {
    g->adj[u][v]++;
    g->adj[v][u]++;
    g->degree[u]++;
    g->degree[v]++;
    g->edgeCount++;
}

int hasEulerCircuit(EulerGraph *g) {
    for (int i = 0; i < g->vertexCount; i++) {
        if (g->degree[i] % 2 != 0) {
            return 0;
        }
    }
    return 1;
}

int hasEulerPath(EulerGraph *g, int *start) {
    int oddCount = 0;
    *start = 0;
    
    for (int i = 0; i < g->vertexCount; i++) {
        if (g->degree[i] % 2 != 0) {
            oddCount++;
            *start = i;
        }
    }
    
    return oddCount == 0 || oddCount == 2;
}

int eulerPath[MAX_E];
int eulerCount = 0;

void hierholzer(EulerGraph *g, int u) {
    for (int v = 0; v < g->vertexCount; v++) {
        while (g->adj[u][v] > 0) {
            g->adj[u][v]--;
            g->adj[v][u]--;
            hierholzer(g, v);
        }
    }
    eulerPath[eulerCount++] = u;
}

void findEulerPath(EulerGraph *g) {
    int start;
    
    if (!hasEulerPath(g, &start)) {
        printf("No Euler path exists\n");
        return;
    }
    
    eulerCount = 0;
    hierholzer(g, start);
    
    printf("Euler path: ");
    for (int i = eulerCount - 1; i >= 0; i--) {
        printf("%d ", eulerPath[i]);
    }
    printf("\n");
}

Fleury算法¶

C
int isBridge(EulerGraph *g, int u, int v) {
    EulerGraph temp = *g;
    
    temp.adj[u][v]--;
    temp.adj[v][u]--;
    temp.degree[u]--;
    temp.degree[v]--;
    
    int visited1[MAX_V] = {0};
    int count1 = countReachable(&temp, u, visited1);
    
    *g = temp;
    g->adj[u][v]++;
    g->adj[v][u]++;
    g->degree[u]++;
    g->degree[v]++;
    
    int visited2[MAX_V] = {0};
    int count2 = countReachable(g, u, visited2);
    
    return count1 < count2;
}

void fleury(EulerGraph *g, int u, int path[], int *pathCount) {
    path[(*pathCount)++] = u;
    
    if (g->degree[u] == 0) {
        return;
    }
    
    int edgeCount = 0;
    int candidates[MAX_V];
    
    for (int v = 0; v < g->vertexCount; v++) {
        if (g->adj[u][v] > 0) {
            candidates[edgeCount++] = v;
        }
    }
    
    for (int i = 0; i < edgeCount; i++) {
        int v = candidates[i];
        
        if (g->degree[u] == 1 || !isBridge(g, u, v)) {
            g->adj[u][v]--;
            g->adj[v][u]--;
            g->degree[u]--;
            g->degree[v]--;
            
            fleury(g, v, path, pathCount);
            return;
        }
    }
}

哈密顿路径¶

定义¶

哈密顿路径：经过图中每个顶点恰好一次的路径
哈密顿回路：起点和终点相同的哈密顿路径
哈密顿图：存在哈密顿回路的图

回溯法求解¶

C
typedef struct {
    int adj[MAX_V][MAX_V];
    int vertexCount;
} HamiltonGraph;

int path[MAX_V];
int visited[MAX_V];
int found = 0;

int isValid(HamiltonGraph *g, int v, int pos) {
    if (!g->adj[path[pos - 1]][v]) {
        return 0;
    }
    
    for (int i = 0; i < pos; i++) {
        if (path[i] == v) {
            return 0;
        }
    }
    
    return 1;
}

void hamiltonPathUtil(HamiltonGraph *g, int pos) {
    if (pos == g->vertexCount) {
        found = 1;
        printf("Hamilton path: ");
        for (int i = 0; i < g->vertexCount; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
        return;
    }
    
    for (int v = 1; v < g->vertexCount; v++) {
        if (!visited[v] && isValid(g, v, pos)) {
            path[pos] = v;
            visited[v] = 1;
            
            hamiltonPathUtil(g, pos + 1);
            
            if (found) return;
            
            visited[v] = 0;
        }
    }
}

void findHamiltonPath(HamiltonGraph *g) {
    for (int i = 0; i < g->vertexCount; i++) {
        visited[i] = 0;
        path[i] = -1;
    }
    
    path[0] = 0;
    visited[0] = 1;
    found = 0;
    
    hamiltonPathUtil(g, 1);
    
    if (!found) {
        printf("No Hamilton path exists\n");
    }
}

哈密顿回路¶

C
void hamiltonCircuitUtil(HamiltonGraph *g, int pos) {
    if (pos == g->vertexCount) {
        if (g->adj[path[pos - 1]][path[0]]) {
            found = 1;
            printf("Hamilton circuit: ");
            for (int i = 0; i < g->vertexCount; i++) {
                printf("%d ", path[i]);
            }
            printf("%d\n", path[0]);
        }
        return;
    }
    
    for (int v = 1; v < g->vertexCount; v++) {
        if (!visited[v] && g->adj[path[pos - 1]][v]) {
            path[pos] = v;
            visited[v] = 1;
            
            hamiltonCircuitUtil(g, pos + 1);
            
            if (found) return;
            
            visited[v] = 0;
        }
    }
}

动态规划求解哈密顿路径¶

C
int dp[1 << MAX_V][MAX_V];

int hamiltonPathDP(HamiltonGraph *g, int start, int end) {
    int n = g->vertexCount;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int v = 0; v < n; v++) {
            dp[mask][v] = 0;
        }
    }
    
    dp[1 << start][start] = 1;
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                
                if (g->adj[u][v] && dp[mask][u]) {
                    dp[mask | (1 << v)][v] = 1;
                }
            }
        }
    }
    
    return dp[(1 << n) - 1][end];
}

C++ 实现¶

C++
class EulerPath {
private:
    vector<vector<int>> adj;
    int n;
    vector<int> path;
    
    void hierholzer(int u) {
        for (int v = 0; v < n; v++) {
            while (adj[u][v] > 0) {
                adj[u][v]--;
                adj[v][u]--;
                hierholzer(v);
            }
        }
        path.push_back(u);
    }
    
public:
    EulerPath(int n) : n(n), adj(n, vector<int>(n, 0)) {}
    
    void addEdge(int u, int v) {
        adj[u][v]++;
        adj[v][u]++;
    }
    
    vector<int> findEulerPath() {
        vector<int> degree(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                degree[i] += adj[i][j];
            }
        }
        
        int oddCount = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (degree[i] % 2) {
                oddCount++;
                start = i;
            }
        }
        
        if (oddCount != 0 && oddCount != 2) {
            return {};
        }
        
        path.clear();
        hierholzer(start);
        reverse(path.begin(), path.end());
        return path;
    }
};

class HamiltonPath {
private:
    vector<vector<int>> adj;
    int n;
    vector<int> path;
    vector<bool> visited;
    
    bool dfs(int pos) {
        if (pos == n) {
            return true;
        }
        
        for (int v = 0; v < n; v++) {
            if (!visited[v] && adj[path[pos - 1]][v]) {
                path[pos] = v;
                visited[v] = true;
                
                if (dfs(pos + 1)) {
                    return true;
                }
                
                visited[v] = false;
            }
        }
        
        return false;
    }
    
public:
    HamiltonPath(int n) : n(n), adj(n, vector<int>(n, 0)) {}
    
    void addEdge(int u, int v) {
        adj[u][v] = adj[v][u] = 1;
    }
    
    vector<int> findHamiltonPath() {
        path.assign(n, -1);
        visited.assign(n, false);
        
        for (int start = 0; start < n; start++) {
            path[0] = start;
            visited[start] = true;
            
            if (dfs(1)) {
                return path;
            }
            
            visited[start] = false;
        }
        
        return {};
    }
};

时间复杂度分析¶

问题	算法	时间复杂度	空间复杂度
欧拉路径	Hierholzer	O(E)	O(V + E)
欧拉路径	Fleury	O(E²)	O(V + E)
哈密顿路径	回溯法	O(n!)	O(n)
哈密顿路径	动态规划	O(n² × 2ⁿ)	O(n × 2ⁿ)

判定条件对比¶

欧拉路径¶

有简单判定条件：基于顶点度数
多项式时间可解：O(E)时间找到路径

哈密顿路径¶

NP完全问题：没有多项式时间算法（除非P=NP）
需要枚举搜索：指数时间复杂度

充分条件（哈密顿图）¶

Dirac定理：若图G有n ≥ 3个顶点，且每个顶点度数 ≥ n/2，则G是哈密顿图。

Ore定理：若图G有n个顶点，对于任意不相邻的顶点u、v，deg(u) + deg(v) ≥ n，则G是哈密顿图。

应用场景¶

欧拉路径¶

一笔画问题：判断图形能否一笔画成
中国邮递员问题：邮递员路线规划
电路设计：PCB布线、扫描线算法
DNA序列拼接：将DNA片段拼接成完整序列

哈密顿路径¶

旅行商问题：访问所有城市恰好一次
排课问题：课程安排优化
电路测试：测试路径规划
国际象棋：马的遍历问题

七桥问题¶

哥尼斯堡七桥问题：能否从某点出发，经过每座桥恰好一次，回到起点？

Text Only
1 2 3 4 5 6 7	`A /\|\ / \| \ B--+--C \ \| / \\|/ D`

分析：四个顶点的度数都是奇数，不存在欧拉路径。

参考资料¶

《算法导论》
Eulerian Path - Wikipedia
Hamiltonian Path - Wikipedia
《图论及其应用》- J.A. Bondy