该算法在耿素云，屈婉玲的《离散数学》第一版第十五章15.1节定理15.1的证明中有详细介绍
用逐步插入回路法构造欧拉回路的方法是
设G为欧拉图,因此是偶图，偶图中必然有圈。现在G中找出任意一个圈C,从G中删除C中所有边得到偶图G’,G’的每一个连通分量都是偶图，因而都存在欧拉回路，设这些欧拉回路为C1,C2,—,Cn
考虑C上任意一个顶点v1,v1属于欧拉回路Ci1,从v1出发经Ci1回到v1,然后从v1出发沿C前进,先将Ci1中的所有顶点标记为已访问,若遇到的顶点v2已访问则只把该顶点加入欧拉回路,然后继续沿C前进，若该顶点未访问，则该顶点属于一个新的欧拉回路Ci2,和前面一样，从v2出发经Ci2回到v2，把Ci2中所有顶点标记为已访问,然后从v2出发继续沿C前进，以此类推，当最终环绕C一圈回到v1时就得到了G的欧拉回路
以下C++实现分别给出了以邻接矩阵和邻接表表示图的两种实现，阅读代码时请注意区分
C++代码:

#include <iostream>
#include <vector>
#include <list>
using namespace std;
#include "findCircle.h"
#include "find_road_adj_list.h"

enum FindCircleStyle {DFS_BACK, DFS};
bool findCircleForAdj_list(adjacency_list& adj, int first_vertex, vector<int>& circle, vector<bool>& visited, const int& root, vector<int>& pre)
{
    visited[first_vertex] = true;
    for (list<int>::const_iterator run = adj.getFirstEdge(first_vertex); run != adj.getEdgeList(first_vertex).end(); ++run)
    {
        if (visited[*run] == false)
        {
            pre[*run] = first_vertex;
            if (findCircleForAdj_list(adj, *run, circle, visited, root, pre))
                return true;
        }
        else
        {
            if (*run == root)
            {
                if (pre[first_vertex] == root)
                    continue;
                for (;first_vertex != root; first_vertex = pre[first_vertex])
                {
                    circle.push_back(first_vertex);
                }
                circle.push_back(root);
                return true;
            }
        }
    }
    return false;
}

void findEularPathForAdj_list(adjacency_list& adj, int first_vertex, vector<int>& eularPath, vector<bool>& in_eualr_path_has_got, FindCircleStyle flag, vector<vector<list<int>::iterator>> &edge_iterator_list)
{
    vector<int> circle_founded;
    vector<list<int>::const_iterator> circle;
    if (flag == FindCircleStyle::DFS_BACK)
    {
        FindRoad(adj, first_vertex, first_vertex, circle);
        circle_founded.resize(circle.size());
        for (int i = 0; i < circle.size(); ++i)
        {
            circle_founded[i] = *circle[i];
        }
    }
    else
    {
        vector<bool> visited(N, false);
        vector<int> pre(N, -1);
        findCircleForAdj_list(adj, first_vertex, circle_founded, visited, first_vertex, pre);
    }

    if (circle_founded.empty())
    {
        in_eualr_path_has_got[first_vertex] = true;
        return;
    }

    if (flag == FindCircleStyle::DFS_BACK)
    {
        int temp = *circle[0];
        adj.getEdgeList(*circle[0]).erase(edge_iterator_list[*circle[0]][first_vertex]);
        adj.getEdgeList(first_vertex).erase(circle[0]);
        for (int i = 1; i < circle.size(); ++i)
        {
            int temp_2 = *circle[i];
            adj.getEdgeList(*circle[i]).erase(edge_iterator_list[*circle[i]][temp]);
            adj.getEdgeList(temp).erase(circle[i]);
            temp = temp_2;
        }
    }
    else
    {
        for (int i = 0; i < circle_founded.size() - 1; ++i)
        {
            adj.getEdgeList(circle_founded[i]).erase(edge_iterator_list[circle_founded[i]][circle_founded[i + 1]]);
            adj.getEdgeList(circle_founded[i + 1]).erase(edge_iterator_list[circle_founded[i + 1]][circle_founded[i]]);
        }
        adj.getEdgeList(circle_founded.back()).erase(edge_iterator_list[circle_founded.back()][circle_founded[0]]);
        adj.getEdgeList(circle_founded[0]).erase(edge_iterator_list[circle_founded[0]][circle_founded.back()]);
    }

    for (int i = circle_founded.size() - 1; ; --i)
    {
        if (in_eualr_path_has_got[circle_founded[i]] == false)
        {
            vector<int> Eular_Path_for_sub_graph;
            findEularPathForAdj_list(adj, circle_founded[i], Eular_Path_for_sub_graph, in_eualr_path_has_got, flag, edge_iterator_list);

            for (int j = 0; j < Eular_Path_for_sub_graph.size(); ++j)
            {
               eularPath.push_back(Eular_Path_for_sub_graph[j]);
            }
        }
        eularPath.push_back(circle_founded[i]);

        if (i == 0)
            break;
    }
}

bool findCircle(bool adj_matrix[][N], int first_vertex, vector<int>& circle, vector<bool>& visited, const int& root, vector<int>& pre)
{
    visited[first_vertex] = true;
    for (int run = 0; run < N; ++run)
    {
        if (run == first_vertex || adj_matrix[first_vertex][run] == false)
            continue;
        if (visited[run] == false)
        {
            pre[run] = first_vertex;
            if (findCircle(adj_matrix, run, circle, visited, root, pre))
                return true;
        }
        else
        {
            if (run == root)
            {
                if (pre[first_vertex] == root)
                    continue;
                circle.push_back(root);
                for (; first_vertex != root; first_vertex = pre[first_vertex])
                {
                    circle.push_back(first_vertex);
                }
                return true;
            }
        }
    }
    return false;
}


void findEularPath(bool adj_matrix[][N], int first_vertex, vector<int>& eularPath, vector<bool> &in_eualr_path_has_got, FindCircleStyle flag)
{
    vector<int> circle;
    if (flag == FindCircleStyle::DFS_BACK)
    {
        FindRoad(false, first_vertex, first_vertex, adj_matrix, circle);
    }
    else
    {
        vector<bool> visited(N, false);
        vector<int> pre(N, -1);
        findCircle(adj_matrix, first_vertex, circle, visited, first_vertex, pre);
    }

    if (circle.empty())
    {
        in_eualr_path_has_got[first_vertex] = true;
        return;
    }

    for (int i = 0; i < circle.size() - 1; ++i)
    {
        adj_matrix[circle[i]][circle[i + 1]] = false;
        adj_matrix[circle[i + 1]][circle[i]] = false;
    }
    adj_matrix[circle.back()][first_vertex] = false;
    adj_matrix[first_vertex][circle.back()] = false;
    for (int i = 0; i < circle.size(); ++i)
    {
        if (in_eualr_path_has_got[circle[i]] == false)
        {
            vector<int> Eular_Path_for_sub_graph;
            findEularPath(adj_matrix, circle[i], Eular_Path_for_sub_graph, in_eualr_path_has_got, flag);

            for (int j = 0; j < Eular_Path_for_sub_graph.size(); ++j)
            {
                eularPath.push_back(Eular_Path_for_sub_graph[j]);
            }
        }
        eularPath.push_back(circle[i]);
    }
}
int main()
{
    FindCircleStyle flag = FindCircleStyle::DFS;
    adjacency_list adj(N, false);
    bool adj_matrix[N][N] = {false};
    vector<pair<int, int>> input{ {0, 1}, {0, 2}, {1, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6} };
    for (const auto& run : input)
    {
        adj.insert(run.first, run.second);
        adj_matrix[run.first][run.second] = true;
        adj_matrix[run.second][run.first] = true;
    }

    vector<vector<list<int>::iterator>> edge_iterator_list(N, vector<list<int>::iterator>(N));
    for (int i = 0; i < N; ++i)
    {
        list<int>& p = adj.getEdgeList(i);
        for (list<int>::iterator j = p.begin(); j != p.end(); ++j)
        {
            edge_iterator_list[i][*j] = j;
        }
    }
    vector<bool> in_eualr_path_has_got(N, false);
    vector<int> eularPath;

    findEularPath(adj_matrix, 0, eularPath, in_eualr_path_has_got, flag);
    cout << "逐步插入回路算法(邻接矩阵版本)发现的欧拉回路为:" << endl;
    for (const auto& run : eularPath)
    {
        cout << run << " ";
    }
    cout << eularPath[0];
    cout << endl;

    vector<bool> in_eualr_path_has_got_adj_list(N, false);
    vector<int> eularPath_adj_list;

    findEularPathForAdj_list(adj, 0, eularPath_adj_list, in_eualr_path_has_got_adj_list, flag, edge_iterator_list);
    cout << "逐步插入回路算法(邻接表版本)发现的欧拉回路为:" << endl;
    for (const auto& run : eularPath_adj_list)
    {
        cout << run << " ";
    }
    cout << eularPath_adj_list[0];
    cout << endl;
    return 0;
}

find_road_adj_list.h头文件内容

#pragma once

struct adjacency_list
{
    void insert(int u, int v) { adj[u].push_back(v); if (isDiGraph == false) adj[v].push_back(u); }
    void deleteEdge(int u, int v)
    {
        list<int>::iterator run = adj[u].begin();
        while (*run != v)
        {
            ++run;
        }
        adj[u].erase(run);

        if (isDiGraph == false)
        {
            run = adj[v].begin();
            while (*run != u)
            {
                ++run;
            }
            adj[u].erase(run);
        }
    }
    vector<list<int>> adj;
    bool isDiGraph;
    adjacency_list(size_t v_num, bool id) :adj(v_num), isDiGraph(id) {}
    list<int>::const_iterator getFirstEdge(int u) { return adj[u].begin(); }
    list<int>& getEdgeList(int u) { return adj[u]; }
};

bool Enable(int start, int i, const list<int>::const_iterator& j, bool node[], int& edgeLinkRootUsed) //检查j是否是i的下一可达顶点, 是返回1否则返回0
{

    if (node[*j])
        return false;

    if (*j == start && edgeLinkRootUsed == i)
        return false;

    return true;
}

list<int>::const_iterator Search(const adjacency_list& adj, int start, int k, const list<int>::const_iterator& option, bool node[], int& edgeLinkRootUsed)  //在顶点k上搜索顶点option后的第一个可达顶点,搜索成功返回顶点标号，否则返回-1
{
    list<int>::const_iterator m = option;
    if (option == adj.adj[k].end())
        m = adj.adj[k].begin();
    else
        ++m;

    for (; m != adj.adj[k].end(); ++m)
    {
        if (Enable(start, k, m, node, edgeLinkRootUsed))
            return m;
    }
    return m;
}

void FindRoad(const adjacency_list& adj, int start, int end, vector<list<int>::const_iterator> &path_list)  //路径搜索函数,寻找start和end间的所有路径
{

    int i;   //i为当前顶点,k为下一可达顶点
    list<int>::const_iterator interval, k;
    int edgeLinkRootUsed = -1;
    bool node[N] = { 0 };

    if (start != end)
        node[start] = 1; //start标记为已访问,
    i = start; k = adj.adj[start].cend();  //i初始化为起始顶点
    while (true)
    {
        if ((interval = Search(adj, start, i, k, node, edgeLinkRootUsed)) == adj.adj[i].cend())   //搜索从k起的下一个可达顶点失败
        {
            if (i == start)    //路径搜索完毕，退出
                break;

            if (k != adj.adj[i].cend())
            {
                path_list.pop_back();
            }
        }
        else
        {
            //搜索出下一可达顶点
            if (k == adj.adj[i].cend())
            {
                path_list.push_back(interval);           //建立表示当前顶点i的路径节点 
            }
            else
            {
                path_list.back() = interval;
            }
            node[*interval] = true;                                 //下一可达顶点标记为已访问

            if (i == start && adj.isDiGraph == false)
            {
                edgeLinkRootUsed = *interval;
            }
            i = *interval;     //更新i为下一可达顶点

            if (i == end)    //到达终点
            {
                return;
            }
            else
            {
                k = adj.adj[i].cend();           //k重置 
                continue;
            }
        }
        node[i] = false;
        k = path_list.back();    //回溯
        if (path_list.end() - 1 == path_list.begin())
        {
            i = start;
        }
        else
        {
            i = *(*(path_list.end() - 2));
        }

    }
}

findCircle.h头文件内容

#pragma once
#define N 7
bool Enable(int start, int i, int j, bool p[][N], bool node[], int& edgeLinkRootUsed) //检查j是否是i的下一可达顶点, 是返回1否则返回0
{
    if (p[i][j] == false)
        return false;

    if (node[j])
        return false;

    if (j == start && edgeLinkRootUsed == i)
        return false;

    return true;
}

int Search(int start, int k, int option, bool p[][N], bool node[], int& edgeLinkRootUsed)  //在顶点k上搜索顶点option后的第一个可达顶点,搜索成功返回顶点标号，否则返回-1
{
    int m = option;

    for (m++; m < N; m++)
    {
        if (Enable(start, k, m, p, node, edgeLinkRootUsed))
            return m;
    }
    return -1;
}


void FindRoad(bool isDiGraph, int start, int end, bool p[][N], vector<int> &path_list)  //路径搜索函数,寻找start和end间的所有路径
{
    int i, k;   //i为当前顶点,k为下一可达顶点
    int interval;
    bool node[N] = { 0 };  //Node数组标记各顶点在搜索过程中是否已被访问,Node[i]=0表示i+1顶点未被访问,Node[i]=1表示i+1顶点已被访问，这里首先初始化Node数组
    int edgeLinkRootUsed = -1;

    if (start != end)
        node[start] = 1; //start标记为已访问
    i = start; k = -1;  //i初始化为起始顶点
    while (true)
    {
        if ((interval = Search(start, i, k, p, node, edgeLinkRootUsed)) == -1)   //搜索从k起的下一个可达顶点失败
        {
            if (i == start)    //路径搜索完毕，退出
                break;

            if (k != -1) 
            {
                path_list.pop_back();
            }
        }
        else
        {
            //搜索出下一可达顶点
            if (k == -1)
            {
                path_list.push_back(i);           //建立表示当前顶点i的路径节点                //下一可达顶点标记为已访问  
            }
            node[interval] = true;                                 //下一可达顶点标记为已访问

            if (i == start && isDiGraph == false)
            {
                edgeLinkRootUsed = interval;
            }
            i = interval;     //更新i为下一可达顶点

            if (i == end)    //到达终点
            {
                return;
            }
            else
            {
                k = -1;           //k重置 
                continue;
            }
        }
        node[i] = false;
        k = i;    //回溯
        i = path_list.back();
    }
}