实验要求：
1.给定一非负整数序列（例如：(4,2,2,2,2)）。
2.判断此非负整数序列是否是可图化的，是否是可简单图化的。
3.如果是可简单图化的，根据Havel定理过程求出对应的简单图，并输出此简单图的相邻矩阵（默认第i行对应顶点vi）。
4.判断此简单图是否是连通的。
5.如果是连通图，判断此图是否是jxdxlz。如果是jxdxlz，请输出一条欧拉回路（输出形式如：v2->v1->v5->v3->v4->v5->v2）。
--------------------------------------------分割线------------------------------------------------
对于整数序列的定义，这里运用了struct来进行运算，方便后续代码实现
struct k{int len;//该点的度数int num;//该点的编号int d;//该点的度数，保存不动，方便运算结束后将度数恢复}a[10000];可图化的判断：所有顶点的度数和为偶数。
for (int i = 1; i <= n; i++){cin >> s;int t = s;while (s < 0|| s !=t){cout << "不能输入负数,小数" << endl;cin >> s;}a[i].len = s;a[i].num = i;a[i].d = a[i].len;sum += a[i].len;}if (sum % 2 != 0){cout << "该序列不可图化" << endl;return 0;}可简单图化判断：Havel定理
Havel定理描述
给定一个非负整数序列{d1,d2,…dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。（顶点的度是指与该顶点相铃的顶点数）
可图化的判定比较简单：d1+d2+…dn=0(mod2)。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。
可简单图化的判定，有一个Havel定理，是说: 我们把序列排成不增序，即d1>=d2>=…>=dn，则d可简单图化当且仅当d’=(d2-1, d3-1, … d(d1+1)-1, d(d1+2), d(d1+3), … dn)可简单图化。
原文链接：https://blog.csdn.net/qq_35033987/article/details/78889683）
例如：（4 4 2 2 2 2）可简单图化——>（3 1 1 1 2）可简单图化——>
（3 2 1 1 1）可简单图化——>（1 0 0 1）可简单图化——>（1 1 0 0）可简单图化——>（0 0 0 0）可简单图化
（0 0 0 0）显然可简单图化，故（4 4 2 2 2 2）可简单图化
代码见下：
输出简单图相邻矩阵：直接将 c[n][n] 输出
cout << " " ;for (int i = 1; i <= n; i++){cout << "v" << i << " ";}cout << endl;for (int i = 1; i <= n; i++){cout << "v" << i << " ";for (int j = 1; j <= n ; j++){if (c[i][j] == 1)cout << "1 ";elsecout << "0 ";}cout << endl;}判断图是否连通：暴力dfs遍历
void tomako(int x){p[x] = 1;//p[x]=1 ——> x遍历过for (int i = 1; i <= n; i++){if (p[i] == 1)continue;if (c[x][i] == 1)tomako(i);}}tomako(1);bool book1 = 1;//可否简单图化标签for (int i = 1; i <= n; i++){if (p[i] == 0){book1 = 0;break;}}if (book1 == 0){cout << "不连通" << endl;return 0;}cout << "连通" << endl;jxdxlz定义：
jxdxlz是指通过图（ 无向图 或 有向图 ）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。. 具有 欧拉回路 的图称为jxdxlz（Euler Graph）
**
无向图G是jxdxlz的充分必要条件是G 是连通图并且没有奇数度顶点**
证明：
平凡图显然成立
必要性：图G是jxdxlz，证明G中没有奇数度节点
G是jxdxlz ——> G中存在欧拉回路 ——>欧拉回路中每个点每出现在欧拉回路的序列中就必定会获得两个度 ——>欧拉序列中的所有的点必然都是偶数度的节点 ——>不存在奇数度的节点
充分性：
G中没有奇数度的节点，证明G是jxdxlz——数学归纳法
假设边数是m
1.m=1，没有奇数度节点——该边只能是一个环——G是jxdxlz
2.假设m<=k成立，现在证明m=k+1成立
G连通且没有奇数度顶点——G中必然存在圈——删去圈上的所有的边——假设获得了s个连通分量，每个连通分量有最多k条边，并且都是偶数度的节点（圈上的边每条给顶点贡献两个度）——根据上述的归纳假设每个连通分量都是一个jxdxlz——我们现在将圈复原——必然存在一条欧拉回路连接了所有的节点并回到原点（这条回路的主路就是刚才删去的圈，每次进入连通分量的时候，遍历连通分量的欧拉回路在出来继续走圈）
(原文链接：https://blog.csdn.net/ltyqljhwcm/article/details/53232384)
故一个无向图为jxdxlz——>无奇数顶点
代码如下：
寻找欧拉回路：
有两种方法：Fleury算法， 逐步插入回路法
这里使用逐步插入回路法
1.逐步插入回路法
根据我们上面的证明，我们其实已经得到了一种求解欧拉回路的算法，那就是我们找到了一个圈，我们从圈开始，每次找到一个连通分量就进入走完连通分量的回路，知道我们的主路的圈全部走完，那么我们的走过的序列就是一个欧拉回路
即寻找与当前顶点相关联的顶点，删除两点之间的边，更新主顶点为关联的点。
void tomako1(int x){for (int i = 1; i <= n; i++){if (c[a[x].num][a[i].num] == 1){c[a[x].num][a[i].num] = 0;c[a[i].num][a[x].num] = 0;tomako1(i);}}}若走到尽头（x的度数为零），将x添加进数组，回溯回上个顶点，判断是否有路可走。
完整代码如下：
该代码可能不太容易理解，可以举个例子画图一步一步跟着代码实现来理解
举例：
本图是一个无向图
如上所示，边为（1,3）（1,2）（2,3）（3,4）（3,5）（4,5）
我们从1开始深搜(随机的，别的情况也会出现，这里模拟最容易看清本质的搜索过程)
1——>2——>3——>1
这时候我们会发现回到原点了，但是显然我们并没并且1走到了死胡同里，算法除了问题吗？
并不是，我们接着看
DFS搜索到1，这时候并没有出边开始执行add操作，我们将1节点加入最后的欧拉回路序列
函数递归回溯，3这时有多余的出边指向4，继续递归至顶点4
1——>2——>3——>4——>5——>3
又回到了顶点3这时候，顶点3也没有多余的出边，add 3
1——>2——>3——>4——>5
函数回溯至顶点5，顶点5没有多余的出边，add 5
1——>2——>3——>4
函数回溯至顶点4,4没有多余的出边，add 4
1——>2——>3 add 3
1——>2 add 2
1 add 1
最终结果1 3 5 4 3 2 1 为欧拉回路
通过上面的模拟我们已经可以发现了这个逐步插入回路法的DFS的实现的精髓了
实际上我们第一次搜索会起点的时候，就是找到了一个圈，然后我们函数回溯找每个节点是否还有多余的出边，有多余的出边就从这个入口节点我们就继续递归下去（进入一个连通分量），直到返回到入口节点，直到入口节点没有多余的出边的时候我们这时开始回溯一次回溯连通分量，将连通分量加入结果序列直到将整个圈上的所有的顶点都回溯完之后，返回最开始的起点，欧拉回路查找完毕
（该例子解题过程参考其他文章，原文链接：https://blog.csdn.net/ltyqljhwcm/article/details/53232384）
完整代码：
void tomako1(int x){for (int i = 1; i <= n; i++){if (c[a[x].num][a[i].num] == 1){c[a[x].num][a[i].num] = 0;c[a[i].num][a[x].num] = 0;tomako1(i);}}sum1++;ol[sum1] = a[x].num;//ol[i]为欧拉回路第i个元素的编号}for (int i = 1; i < sum1; i++)cout<<"v"<< ol[i]<<"->";cout << "v" << ol[sum1];最后放出全部代码
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;struct k{int len;int num;int d;}a[10000];int ol[10000];//欧拉回路int c[100][100];//c[i][j]=1——>i与j有边int n, sum = 0,sum1=0;bool book2 = 1;int p[10000] = {};bool cmp(k x, k y){return x.len > y.len;}void tomako(int x){p[x] = 1;//p[x]=1 ——> x遍历过for (int i = 1; i <= n; i++){if (p[i] == 1)continue;if (c[x][i] == 1)tomako(i);}}void tomako1(int x){for (int i = 1; i <= n; i++){if (c[a[x].num][a[i].num] == 1){c[a[x].num][a[i].num] = 0;c[a[i].num][a[x].num] = 0;tomako1(i);}}sum1++;ol[sum1] = a[x].num;//ol[i]为欧拉回路第i个元素的编号}int main(){cin >> n;double s;for (int i = 1; i <= n; i++){cin >> s;int t = s;while (s < 0|| s !=t){cout << "不能输入负数,小数" << endl;cin >> s;}a[i].len = s;a[i].num = i;a[i].d = a[i].len;sum += a[i].len;}if (sum % 2 != 0){cout << "该序列不可图化" << endl;return 0;}bool book = 1;//判断是否可简单图化;int t = n;//t为当前序列元素不为零的个数for (int i = 1; i <= t; i++){sort(a + i, a + n + 1, cmp);//快排if (a[i].len == 0)break;if (a[i].len > t - i)//若最大元素大于剩余元素个数，即会出现负数{book = 0;break;}for (int j = 1; j <= a[i].len; j++)//模拟Havel{a[i + j].len--;c[a[i].num][a[i + j].num] = 1;//c[i][j]=1——>i与j有边c[a[i + j].num][a[i].num] = 1;if (a[i + j].len == 0)t--;}}if (book == 0){cout << "不可简单图化" << endl;return 0;}cout << "可简单图化" << endl;cout << " " ;for (int i = 1; i <= n; i++){cout << "v" << i << " ";}cout << endl;for (int i = 1; i <= n; i++){cout << "v" << i << " ";for (int j = 1; j <= n ; j++){if (c[i][j] == 1)cout << "1 ";elsecout << "0 ";}cout << endl;}tomako(1);bool book1 = 1;for (int i = 1; i <= n; i++){if (p[i] == 0){book1 = 0;break;}}if (book1 == 0){cout << "不连通" << endl;return 0;}cout << "连通" << endl;for (int i = 1; i <= n; i++){if (a[i].d % 2 == 1)//奇度book2 = 0;}if (book2 == 0){cout << "不是jxdxlz" << endl;return 0;}tomako1(1);for (int i = 1; i < sum1; i++)cout<<"v"<< ol[i]<<"->";cout << "v" << ol[sum1];return 0;}以及几个有用的样例：
输入 1
8
2 2 2 2 4 4 4 4
输出 1
输入 2
5
4 2 2 2 2
输出 2
欧拉回路答案不唯一，需自己验证