图论---无向图中国邮路的实现

开始编程前分析设计思路和程序的整体的框架，以及作为数学问题的性质：

程序流程图：

数学原理：

        本质上是找到一条欧拉回路，考虑图中的边权重、顶点的度数以及如何通过添加最少的额外边来构造欧拉回路，涉及到欧拉回路、最短路径算法以及奇点匹配。

时间复杂度分析：

        程序的时间复杂度主要来自于Floyd算法和ADD函数。Floyd是动态规划算法。它的时间复杂度是O(n^3)。 ADD函数是一个递归函数它的时间复杂度是O(2^n)，其中n是奇点的数量。在最坏情况下，奇点的数量可能接近于节点的数量，ADD函数的时间复杂度可能接近于O(2^n)。综合看，这段程序的时间复杂度是O(n^3 + 2^n)。由于2^n的增长速度非常快，当n较大时，2^n将远大于n^3，因此这段程序的时间复杂度应该为O(2^n)

源代码：

#include 
#include 
// 定义常量
const int N = 105;
const int inf = 100000000;
// 建立矩阵和路径数组
int matrix[N][N], mapp[N][N];
int p[N][N];
int path[N], d[N];
int sg[N];
int cont[N];
int vis[N];
int n, m;
int top;
// 设置结构体将边和权重关联
struct node
{
    int v, u, cost;
} gg[N];
// 使用深度优先递归搜索
void DFS(int beg)
{
    for (int i = 1; i