博客

欧拉路径：从一个点出发，每条边都只走一遍，结束于另一个点。

欧拉回路：起点和终点是同一个点。

大前提：基图（去掉方向后的图）中所有度非零的点属于一个连通分量。

欧拉路径：无向图中，只有两个点的度为奇数，这两个点分别为起点和终点。有向图中，只有一个点的出度比入度大1，这个点当起点，只有一个点的入度比出度大1，这个点当终点。

欧拉回路：无向图中，每个点的度为偶数。有向图中，每个点的入度等于出度。

欧拉回路算法：Hierholzer’s Algorithm O(E+V)

建一个栈cur_path保存当前遍历路径，一个vector circuit保存结果路径。

先按DFS遍历，如果当前结点还存在未访问过的边，把结点压入cur_path中，如果当前结点所有边都访问过了，把当前结点push_back进circuit，然后从cur_path中pop一个点出来作为新的当前结点。

代码出处及详细英文解释

// A C++ program to print Eulerian circuit in given 
// directed graph using Hierholzer algorithm 
#include <bits/stdc++.h> 
using namespace std; 
  
void printCircuit(vector< vector<int> > adj) 
{ 
    // adj represents the adjacency list of 
    // the directed graph 
    // edge_count represents the number of edges 
    // emerging from a vertex 
    unordered_map<int,int> edge_count; 
  
    for (int i=0; i<adj.size(); i++) 
    { 
        //find the count of edges to keep track 
        //of unused edges 
        edge_count[i] = adj[i].size(); 
    } 
  
    if (!adj.size()) 
        return; //empty graph 
  
    // Maintain a stack to keep vertices 
    stack<int> curr_path; 
  
    // vector to store final circuit 
    vector<int> circuit; 
  
    // start from any vertex 
    curr_path.push(0); 
    int curr_v = 0; // Current vertex 
  
    while (!curr_path.empty()) 
    { 
        // If there's remaining edge 
        if (edge_count[curr_v]) 
        { 
            // Push the vertex 
            curr_path.push(curr_v); 
  
            // Find the next vertex using an edge 
            int next_v = adj[curr_v].back(); 
  
            // and remove that edge 
            edge_count[curr_v]--; 
            adj[curr_v].pop_back(); 
  
            // Move to next vertex 
            curr_v = next_v; 
        } 
  
        // back-track to find remaining circuit 
        else
        { 
            circuit.push_back(curr_v); 
  
            // Back-tracking 
            curr_v = curr_path.top(); 
            curr_path.pop(); 
        } 
    } 
  
    // we've got the circuit, now print it in reverse 
    for (int i=circuit.size()-1; i>=0; i--) 
    { 
        cout << circuit[i]; 
        if (i) 
           cout<<" -> "; 
    } 
} 
  
// Driver program to check the above function 
int main() 
{ 
    vector< vector<int> > adj1, adj2; 
  
    // Input Graph 1 
    adj1.resize(3); 
  
    // Build the edges 
    adj1[0].push_back(1); 
    adj1[1].push_back(2); 
    adj1[2].push_back(0); 
    printCircuit(adj1); 
    cout << endl; 
  
    // Input Graph 2 
    adj2.resize(7); 
    adj2[0].push_back(1); 
    adj2[0].push_back(6); 
    adj2[1].push_back(2); 
    adj2[2].push_back(0); 
    adj2[2].push_back(3); 
    adj2[3].push_back(4); 
    adj2[4].push_back(2); 
    adj2[4].push_back(5); 
    adj2[5].push_back(0); 
    adj2[6].push_back(4); 
    printCircuit(adj2); 
  
    return 0; 
} 

用dfs求欧拉路径（回路）

void dfs(int u){
    for(int v=0; v<n; v++){                   
        if(adj[u][v] && !vis[u][v]){         //用邻接矩阵表示图
            vis[u][v] = 1;        
            dfs(v);                           
            output.push(Node(u, v));          //一定要dfs(v) 出栈后，再将u，v边压入输出栈
        }
    }
}