实验三

（一）实验题目

图的最大匹配与中国邮递员问题

（二）实验目的

1、掌握最大匹配,交错路径的定义；

2、掌握最大匹配的求解方法；

3、掌握中国邮递员问题与七桥问题的区别与联系；

4、求简化加权图的中国邮递员问题解。

（三）实验要求

输入：无向简单连通图的关联矩阵

输入：无向简单连通图的关联矩阵
（例如：）。
输出1：此图的任意一个最大匹配及匹配数

（例如:M={e1,e3}，β1=2）。
输出2：假设各边的权相同，均为1。将该图作为中国邮递员问题的图，输出相应的最优环游解（例如：CPP解：e1e5e3e4e5e2）。

（四）实验内容和实验步骤

1、需求分析

（1）输入的形式和输入值的范围：
- 输入形式：例如
  
  （给定的关联矩阵）
- 输入值的范围：非负整数

（2）输出的形式：

如图所示，输出时，按照实验要求的顺序依次展开输出

plaintext
──所有的最大匹配（虽然只要求输出任意一个。）
──匹配数
──CPP解

（3）程序所能实现的功能：
- l 能通过给定的无向简单图的关联矩阵，输出此图的最大匹配及匹配数，还能用作中国邮递员问题，输出相应的最优环路解
- 可循环，反复输入，方便测试多组数据

2、概要设计

我选择的是 Python 进行编程，（后面写的C++同理，就不解析了）
下面是各函数的功能分析：
- 1. dfs
    
    函数
    - 作用：该函数使用深度优先搜索（DFS）来找到图中所有可能的路径，然后通过回溯法将这些路径组合成可行解，并存储在ans列表中。同时，记录每个路径的长度并存储在setsize中。
    - 实现细节：递归地探索图中的节点，选择一条边加入路径，然后继续深度搜索。通过回溯，将每次选择的边添加到ans中，形成完整路径。在每一步中，使用edgest和pointst来标记边和节点的访问状态。
  2. path_dfs
    
    函数
    - 作用：该函数使用深度优先搜索（DFS）在邻接矩阵表示的图中找到从指定节点出发的路径，并存储在ans列表中。
    - 实现细节：递归地探索节点的邻接节点，选择一条边加入路径，然后继续深度搜索。通过回溯，将每次选择的边添加到ans中，形成完整路径。递归的终止条件是节点没有未访问的邻接节点。
  3. construct_path
    
    函数
    - 作用：该函数根据先前记录的前驱节点列表构建从起始节点到结束节点的路径，并将其存储在path列表中。
    - 实现细节：从结束节点开始，沿着前驱节点逐步回溯到起始节点，将每个节点加入路径中。最后，反转路径，使其从起始节点到结束节点。
  4. dijkstra
    
    函数
    - 作用：该函数实现了Dijkstra算法，计算从指定节点出发到其他所有节点的最短路径，并返回最短路径长度的列表。
    - 实现细节：使用堆（优先队列）来优化Dijkstra算法，按照当前已知的最短路径长度从小到大进行探索。在每一步中，更新与当前节点相邻的节点的最短路径长度，同时记录前驱节点，以便后续构建路径。
  5. postman
    
    函数
    - 作用：该函数解决中国邮递员问题（CPP），根据输入的关联矩阵构建图，并通过DFS、Dijkstra等算法找到最优路径。
    - 实现细节：首先计算每个节点的度数，找出奇数度节点，并构建关联的图。对奇数度节点使用Dijkstra算法计算最短路径，然后利用DFS找到最优匹配，最终修复路径，使得每条边都至少被访问一次。
  6. search
    
    函数
    - 作用：该函数使用DFS搜索从指定节点出发的所有路径，并将这些路径存储在result列表中。
    - 实现细节：递归地探索节点的邻接节点，选择一条边加入路径，然后继续深度搜索。通过回溯，将每次选择的边添加到result中，形成完整路径。在每一步中，使用visited标记节点是否被访问，确保路径不会形成环。
  7. 主函数部分
    - 作用：用户通过输入关联矩阵来定义图的结构，然后调用各函数求解中国邮递员问题。
    - 实现细节：通过输入关联矩阵构建图结构，利用DFS找到所有可能的路径，并输出最大匹配。然后，使用DFS和Dijkstra算法解决中国邮递员问题，最终输出最优路径。

3、详细设计

源代码：（Python和C++）

Python:

import heapq
import copy

def dfs(u, n, m, grid, edgest, pointst, ans, setsize):
    if u > m:
        path = []
        for i in range(m):
            if edgest[i]:
                path.append(i)
        setsize.append(len(path))
        ans.append(path)
        return
    temp = 0
    edge = [0, 0]
    for i in range(n):
        if grid[i][u] and not pointst[i]:
            temp += 1
            if temp == 1:
                edge[0] = i
            else:
                edge[1] = i

    if temp == 2:
        edgest[u] = True
        pointst[edge[0]] = True
        pointst[edge[1]] = True
        dfs(u + 1, n, m, grid, edgest, pointst, ans, setsize)
        edgest[u] = False
        pointst[edge[0]] = False
        pointst[edge[1]] = False
        dfs(u + 1, n, m, grid, edgest, pointst, ans, setsize)
    else:
        dfs(u + 1, n, m, grid, edgest, pointst, ans, setsize)


def path_dfs(x, graph, n, ans):
    for y in range(n):
        if graph[x][y] > 0:
            graph[x][y] -= 1
            graph[y][x] -= 1
            path_dfs(y, graph, n, ans)
    ans.append(x)
    return ans


def construct_path(precursor, start, end, path):
    path.clear()
    curr = end
    while curr != start:
        path.append(curr)
        curr = precursor[curr]
    path.append(start)
    path.reverse()


def dijkstra(start, distance, precursor, adjacency_matrix):
    INF = float('inf')
    n = len(adjacency_matrix)
    distance = [INF] * n
    distance[start] = 0

    pq = [(0, start)]
    heapq.heapify(pq)

    while pq:
        dist, curr_node = heapq.heappop(pq)

        if dist > distance[curr_node]:
            continue

        for i in range(n):
            if adjacency_matrix[curr_node][i] != INF:
                new_distance = dist + adjacency_matrix[curr_node][i]
                if new_distance < distance[i]:
                    distance[i] = new_distance
                    precursor[i] = curr_node
                    heapq.heappush(pq, (new_distance, i))
    return distance


def postman(n, m, grid):
    flag1, flag2, flag3 = False, False, False
    path = []
    for i in range(n):
        sum = 0
        for j in range(m):
            if grid[i][j]:
                sum += 1
        path.append(sum)

    odd = 0
    odd_num = []
    for i in range(n):
        if path[i] % 2 == 1:
            odd += 1
            odd_num.append(i)

    result = []
    graph = [[0] * 100 for _ in range(50)]
    ed = [[0] * 100 for _ in range(50)]
    for j in range(m):
        arr = []
        for i in range(n):
            if grid[i][j]:
                arr.append(i)
        L, r = arr[0], arr[1]
        graph[L][r] = 1
        graph[r][L] = 1
        ed[L][r] = j
        ed[r][L] = j

    if odd != 0:
        dfs_grid_st = [0] * 100
        for i in range(len(path)):
            dfs_grid_st[path[i]] = i
        odd_grid = [[0] * 100 for _ in range(100)]
        odd_path = [[[] for _ in range(odd)] for _ in range(odd)]

        INF = float('inf')
        adjacency_matrix = [[INF] * n for _ in range(n)]
        ans = []
        for j in range(m):
            arr = [i for i in range(n) if grid[i][j]]
            L, r = arr[0], arr[1]
            adjacency_matrix[L][r] = 1
            adjacency_matrix[r][L] = 1

        for i in range(n):
            adjacency_matrix[i][i] = 0

        for i in range(odd):
            start = odd_num[i]
            distance = []
            precursor = [-1] * n
            distance = list(dijkstra(start, distance, precursor, adjacency_matrix))
            for k in range(len(distance)):
                for z in range(odd):
                    if odd_num[z] == k:
                        odd_grid[i][z] = distance[k]

            for j in range(odd):
                if i == j:
                    odd_path[i][j].append(0)
                    continue
                path = []
                end = odd_num[j]
                construct_path(precursor, start, end, path)
                for k in range(len(path)):
                    x = path[k]
                    odd_path[i][j].append(x)

        ans_dfs = []
        set_size = []
        edgest = [False] * 100
        pointst = [False] * 100

        dfs_grid = [[0] * 1000 for _ in range(20)]
        ed_dfs = [[0] * 100 for _ in range(100)]

        for i in range(odd):
            for j in range(odd):
                ed_dfs[i][j] = -1

        idx = 0
        for p in range(odd):
            for z in range(p + 1, odd):
                if odd_grid[p][z]:
                    dfs_grid[p][idx] = 1
                    dfs_grid[z][idx] = 1
                    ed_dfs[p][z] = idx
                    ed_dfs[z][p] = idx
                    idx += 1

        dfs(0, odd, idx, dfs_grid, edgest, pointst, ans_dfs, set_size)
        length = len(ans_dfs)
        max_match = 0

        for i in range(length):
            if set_size[i] > max_match:
                max_match = i

        res_long = len(ans_dfs[max_match])
        mindfs = INF
        flagdfs = 0

        for k in range(length):
            if set_size[k] == res_long:
                sum_val = 0
                for i in range(res_long):
                    for edi in range(odd):
                        for edj in range(edi + 1, odd):
                            if ans_dfs[k][i] == ed_dfs[edi][edj]:
                                sum_val += len(odd_path[edi][edj]) - 1
                if sum_val < mindfs:
                    mindfs = sum_val
                    flagdfs = k

        final_ans = []
        for i in range(res_long):
            for edi in range(odd):
                for edj in range(edi + 1, odd):
                    if ans_dfs[flagdfs][i] == ed_dfs[edi][edj]:
                        final_ans.append(odd_path[edi][edj])
        for i in range(len(final_ans)):
            for j in range(len(final_ans[i]) - 1):
                Le, ri = final_ans[i][j], final_ans[i][j + 1]
                graph[Le][ri] += 1
                graph[ri][Le] += 1
    ans = []
    ans = path_dfs(0, graph, n, ans)
    need_len = len(ans)
    print("CPP解：", end="")
    for i in range(need_len - 1):
        print(f"e{ed[ans[i]][ans[i + 1]] + 1}", end=" ")
    print()

# dfs搜索从start点开始的所有路径
def search(visited, start, re):
    vi = copy.deepcopy(visited)
    vi[start] = True
    r = copy.deepcopy(re)
    r.append(start)
    flag = True
    for i in adj_points[start]:
        if not vi[i]:
            flag = False
            search(vi, i, r)
    if flag:
        result.append(r)



while True:
    print("# 请输入关联矩阵：（输入‘0’退出）")
    grid = [[0] * 1000 for _ in range(100)]
    cin = input()

    if cin == "0":
        break

    count = 0
    while cin:
        row = list(map(int, cin.split()))
        for i in range(len(row)):
            grid[count][i] = row[i]
        cin = input()
        count += 1

    n = count
    m = len(row)
    inc = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            inc[j][i] = grid[i][j]

    ans = []
    set_size = []
    edgest = [False] * 100
    pointst = [False] * 100

    dfs(0, n, m, grid, edgest, pointst, ans, set_size)

    length = len(ans)
    max_match = 0
    for i in range(length):
        if set_size[i] > max_match:
            max_match = i

    res_long = len(ans[max_match])
    count = 1
    for k in range(length):
        if set_size[k] == res_long:
            if count:
                print("最大匹配：M = { ", end="")
                count = 0
            else:
                print("         M = { ", end="")
            for i in range(res_long):
                if i == res_long-1:
                    print(f"e{ans[k][i] + 1}", end=" ")
                else:
                    print(f"e{ans[k][i] + 1}", end=",")
            print("}")

    # 点的数量
    v_count = len(inc[0])
    # 找到所有点的邻接节点，方便用dfs搜索路径
    adj_points = {i: [] for i in range(v_count)}
    for each in inc:
        p = list(filter(lambda x: x[1] == 1, enumerate(each)))
        adj_points[p[0][0]].append(p[1][0])
        adj_points[p[1][0]].append(p[0][0])
    result = []
    visited = [False] * v_count

    # 搜索每一个点开始的路径
    for i in range(v_count):
        search(visited, i, re=[])
    # 路径按长度排序
    s = sorted(result, key=lambda x: len(x), reverse=True)
    print("匹配数： β\u2081 = %d" % (len(s[0]) // 2) )
    print()

    postman(n, m, grid)

    print()

"""
4 5
1 0 0 1 1
1 1 0 0 0
0 0 1 1 0
0 1 1 0 1

5 6
1 0 0 1 0 1
1 1 0 0 0 0
0 1 1 0 0 0
0 0 0 1 1 0
0 0 1 0 1 1

5 7
1 1 0 0 0 0 1
1 0 0 1 0 1 0
0 0 0 0 1 1 1
0 1 1 0 1 0 0
0 0 1 1 0 0 0

5 6
1 1 0 0 0 0
0 1 0 1 0 1
0 0 1 1 0 0
1 0 1 0 1 0
0 0 0 0 1 1
"""

C++:

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;
 
struct Node {
    int num;
    vector<Node> child;
};

vector<Node> points;
vector<vector<int> > results;

//寻找所有的匹配
void dfs(int u, int n, int m, int grid[][1000], bool edgest[], bool pointst[], vector<vector<int> >& ans, vector<int>& setsize)
{
	if (u>m)
	{
		vector<int>path;//将搜索到的边存进去
		for (int i = 0; i < m; i++)
		{
			if (edgest[i])path.push_back(i);
		}
		setsize.push_back(path.size());
		ans.push_back(path);
		return;//深度搜索完毕,搜完边就行
	}
	int temp = 0;//临时用来计算此边关联的点有没有被搜索过
	int edge[2] = { 0 };//用来看是哪两个点
	for (int i = 0; i < n; i++)
	{
		if (grid[i][u]&&!pointst[i])
		{
			temp++;
			if (temp == 1)edge[0] = i;
			else edge[1] = i;
		}
	}
	if (temp == 2)//说明这条边能用
	{
		edgest[u] = true;
		pointst[edge[0]] = true;
		pointst[edge[1]] = true;
		dfs(u + 1, n, m, grid, edgest, pointst, ans, setsize);
		edgest[u] = false;
		pointst[edge[0]] = false;
		pointst[edge[1]] = false;
		dfs(u + 1, n, m, grid, edgest, pointst,ans, setsize);
	}
	else
	{   //这边不能用也能搜，但没有上面那么多，因为不用改变状态
		dfs(u + 1, n, m, grid, edgest, pointst, ans, setsize);
	}
}


void pathdfs(int x, int graph[][100], int n, vector<int>&ans) 
{
	for (int y = 0; y < n; ++y) 
	{
		if (graph[x][y] > 0) 
		{
			graph[x][y]--;
			graph[y][x]--;
			pathdfs(y,graph,n,ans);
		}
	}
	ans.push_back(x);
}


// 构造最短路径
void ConstructPath(const vector<int>& precursor, int start, int end, vector<int>& path) 
{
	path.clear();
	int curr = end;
	while (curr != start) 
	{ // 从终点回溯到起点
		path.push_back(curr);
		curr = precursor[curr];
	}
	path.push_back(start);
	// 反转路径，使其从起点到终点
	reverse(path.begin(), path.end());
}

// Dijkstra算法实现
void Dijkstra(int start, vector<int>& distance, vector<int>& precursor, vector<vector<int> > adjacencyMatrix) 
{
	// 定义无穷大的距离值
	const int INF = INT_MAX;
	int n = adjacencyMatrix.size();
	distance.resize(n, INF); // 初始化距离数组为无穷大
	distance[start] = 0; // 起点到自身的距离为0
	precursor.resize(n, -1); // 初始化前驱节点数组，表示还未访问的节点前驱为-1
 
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; // 小顶堆存储未访问节点
	pq.push(make_pair(0, start)); // 将起点加入小顶堆
 
	while (!pq.empty()) {
		int dist = pq.top().first;
		int currNode = pq.top().second;
		pq.pop();
 
		// 如果当前节点已经被访问过，跳过
		if (dist > distance[currNode]) {
			continue;
		}
 
		// 遍历当前节点的相邻节点
		for (int i = 0; i < n; ++i) 
		{
			if (adjacencyMatrix[currNode][i] != INF) 
			{ // 判断当前节点与相邻节点是否存在连接
				int newDistance = dist + adjacencyMatrix[currNode][i];
				if (newDistance < distance[i]) 
				{ // 如果新的距离更小
					distance[i] = newDistance;
					precursor[i] = currNode; // 更新前驱节点
					pq.push(make_pair(newDistance, i));
				}
			}
		}
	}
}
 
void postman(int n,int m,int grid[][1000])
{
	//分三种情况，欧拉图，半欧拉图，非欧拉图
	bool flag1 = false, flag2 = false, flag3 = false;//与上面情况对应
	vector<int> path;//存放每个点度数
	for (int i = 0; i < n; i++)
	{
		int sum = 0;
		for (int j = 0; j < m; j++)
		{
			if (grid[i][j])
				sum++;
		}
		path.push_back(sum);
	}
	int odd=0;//记录有多少个奇数顶点,同时存下奇数度顶点
	vector<int> oddnum;
	for (int i = 0; i < n; i++)
		if (path[i] % 2 == 1)
		{
			odd++;
			oddnum.push_back(i);
		}
	vector<int>result;//存放结果
	//若odd为0则代表其为欧拉图,所有的度数均为偶数
	//将关联矩阵转化为邻接矩阵和边矩阵
	int graph[50][100] = { 0 }, ed[50][100] = { 0 };
	for (int j = 0; j < m; j++)
	{
		vector<int>arr;
		for (int i = 0; i < n; i++)
		{
			if (grid[i][j])arr.push_back(i);
		}
		int L = arr[0], r = arr[1];
		graph[L][r] = 1;
		graph[r][L] = 1;
		ed[L][r] = j;
		ed[r][L] = j;
	}
 
	if (odd != 0)
	{
		int dfsgridst[100] = { 0 };
		for (int i=0; i < path.size(); i++)dfsgridst[path[i]] = i;
		int oddgrid[100][100] = {0};//存奇数顶点的对应的最短路的矩阵
		vector<vector<vector<int> > >oddpath(odd, vector<vector<int> >(odd));
		// 定义无穷大的距离值
		const int INF = INT_MAX;
		vector<vector<int> > adjacencyMatrix(n, vector<int>(n, INF));
		vector<int> ans;
		//用adjacencyMatrix存邻接矩阵
		for (int j = 0; j < m; j++)
		{
			vector<int>arr;
			for (int i = 0; i < n; i++)
			{
				//若不能直接到达那么距离是无穷
				if (grid[i][j])arr.push_back(i);
			}
			int L = arr[0], r = arr[1];
			adjacencyMatrix[L][r] = 1;
			adjacencyMatrix[r][L] = 1;
		}
		for (int i = 0; i < n; i++)adjacencyMatrix[i][i] = 0;
 
		for (int i = 0; i < odd; i++)
		{
			int start = oddnum[i]; // 起点
			vector<int> distance; // 保存最短距离的数组
			vector<int> precursor; // 保存前驱节点的数组
			
			Dijkstra(start, distance, precursor, adjacencyMatrix);
			
			for (int k = 0; k < distance.size(); k++)//distance里面存起点到第k个点的最短距离
			{
				for (int z = 0; z < odd; z++)
				{
					if (oddnum[z] == k)
					{
						oddgrid[i][z] = distance[k];
					}
				}
			}
			for (int j = 0; j < odd; j++)
			{
				if (i == j)
				{
					oddpath[i][j].push_back(0);
					continue;
				}
				vector<int> path; // 保存最短路径的数组
				int end = oddnum[j]; // 终点
				ConstructPath(precursor, start, end, path);	
				for (int k = 0; k < path.size(); ++k) {
				    int x = path[k];
				    oddpath[i][j].push_back(x);
				}
			}		
		}
 
		vector<vector<int> >ansdfs;
		vector<int>setsize;
		bool edgest[100] = { false }, pointst[100] = { false };
		//将oddnum转化为关联矩阵,有n*（n-1）/2条边
		int dfsgrid[20][1000] = { 0 };
		int eddfs[100][100] = {0};
		for (int i = 0; i < odd; i++)
			for (int j = 0; j < odd; j++)eddfs[i][j] = -1;
		int idx = 0;
		for (int p = 0; p < odd; p++)
		{
			for (int z = p+1; z < odd; z++)
			{
				if (oddgrid[p][z])//若有边就将其存入关联矩阵当中
				{
					dfsgrid[p][idx] = 1;
					dfsgrid[z][idx] = 1;
					eddfs[p][z] = idx;
					eddfs[z][p] = idx;
					idx++;
				}
			}
		}
		dfs(0, odd, idx, dfsgrid, edgest, pointst, ansdfs, setsize);
		int len = ansdfs.size();
		int max = 0;//记录最大匹配的位置;
		for (int i = 0; i < len; i++)
		{
			if (setsize[i] > max)
				max = i;
		}
		int reslong = ansdfs[max].size();//记录找到的数组的长度
		//将所有的最大匹配集输出
		int mindfs = INF;
		int flagdfs = 0;
		for (int k = 0; k < len; k++)
		{
			if (setsize[k] == reslong)//若是最大匹配集的长度就将对应的路径加到矩阵当中
			{	
				int sum = 0;
				for (int i = 0; i < reslong; i++)
				{
					for (int edi = 0; edi < odd; edi++)
					{
						for (int edj = edi + 1; edj < odd; edj++)
						{
							if (ansdfs[k][i] == eddfs[edi][edj])
							{
								sum += oddpath[edi][edj].size()-1;
							}
						}
					}
				}
				if (sum < mindfs)
				{
					mindfs = sum;
					flagdfs = k;
				}
			}
		}
		vector<vector<int> >finalans;
		for (int i = 0; i < reslong; i++)
		{
			for (int edi = 0; edi < odd; edi++)
			{
				for (int edj = edi + 1; edj < odd; edj++)
				{
					if (ansdfs[flagdfs][i] == eddfs[edi][edj])
					{
						finalans.push_back(oddpath[edi][edj]);
					}
				}
			}
		}
		for (int i = 0; i < finalans.size(); i++)
		{
			for (int j = 0; j < finalans[i].size()-1; j++)
			{
				int Le = finalans[i][j], ri = finalans[i][j + 1];
				graph[Le][ri] += 1;
				graph[ri][Le] += 1;
			}
		}
	}
	vector<int> ans;
	pathdfs(0, graph, n, ans);
	int needlen = ans.size();
	printf("\nCPP解：");
	for (int i = 0; i < needlen-1; i++)
	{
		printf("e%d ", ed[ans[i]][ans[i + 1]]+1);
	}
	printf("\n");
}

void search(vector<bool> visited, int start, vector<int> rep) {
    visited[start] = true;
    rep.push_back(start);
    bool flag = true;
    for (int i=0; i<points[start].child.size(); i++) {
        if (!visited[points[start].child[i].num]) {
            flag = false;
            search(visited, points[start].child[i].num, rep);
        }
    }
    if (flag) {
        results.push_back(rep);
    }
}

struct CompareVectors {
    bool operator()(const vector<int>& x, const vector<int>& y) const {
        return x.size() > y.size();
    }
};



int main()
{
	while(1)
	{
		points.clear();
		results.clear();
		int grid[100][1000] = { 0 };
		int n, m;
	 
		vector<vector<int> >ans;
		vector<int>setsize;
		bool edgest[100] = { false }, pointst[100] = { false };
		
		cout << "请输入边数和点数：（输入‘0’退出）" << endl;
		cin >> n;
		
		if(n == 0) break;
		
		cin >> m;
		cout << "请输入关联矩阵：" << endl;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
				cin >> grid[i][j];
		}
		
		dfs(0, n, m, grid, edgest, pointst, ans, setsize);
		
		int len = ans.size();
		int max = 0;//记录最大匹配的位置;
		for (int i = 0; i < len; i++)
		{
			if (setsize[i] > max)
				max = i;
		}
		int reslong = ans[max].size();//记录找到的数组的长度
		
		//将所有的最大匹配集输出
		int cc = 1;
		cout << endl;
		for (int k = 0; k < len; k++)
		{
			if (setsize[k] == reslong)//若是最大匹配集的长度就输出
			{
				if(cc)
				{
					printf("最大匹配：M = { ");
					cc = 0;
				}
				else printf("          M = { ");
				for (int i = 0; i < reslong; i++)
				{
					printf("e%d,", ans[k][i]+1);
				}
				printf("\b }\n");
			}
		}
		
	    // 建立节点
		unsigned int v_num = m, e_num = n;
		
	    for (int i = 0; i < v_num; i++)
		{
	        points.push_back(Node{i});
	    }
	    for (int j = 0; j < e_num; j++)
		{
	        vector<int> t;
	        for (int i = 0; i < v_num; i++) {
	            if (grid[i][j] == 1) t.push_back(i);
	        }
	        points[t[0]].child.push_back(points[t[1]]);
	        points[t[1]].child.push_back(points[t[0]]);
	    }
	    
	    vector<bool> visited;
	    visited.assign(v_num, false);
	    
	    for (int i = 0; i < v_num; i++) {
	        search(visited, i, vector<int>());
	    }
	    sort(results.begin(), results.end(), CompareVectors());
	    
	    cout << "匹配数：β1 = " << results[0].size() / 2 << endl;
	
		postman(n, m, grid);
		
		cout << endl;
	}
	return 0;
}

/*
中国邮递员问题

4 5
1 0 0 1 1
1 1 0 0 0
0 0 1 1 0
0 1 1 0 1

5 6
1 0 0 1 0 1
1 1 0 0 0 0
0 1 1 0 0 0
0 0 0 1 1 0
0 0 1 0 1 1

5 7
1 1 0 0 0 0 1
1 0 0 1 0 1 0
0 0 0 0 1 1 1
0 1 1 0 1 0 0
0 0 1 1 0 0 0

5 6
1 1 0 0 0 0
0 1 0 1 0 1
0 0 1 1 0 0
1 0 1 0 1 0
0 0 0 0 1 1
*/

4、调试分析

（1）调试过程中所遇到的问题及解决方法：
- 问题很多
  
  解决方法：基本解决了
（2）算法的时空分析：
- 1. dfs函数
    
    时间复杂性：
    - 在最坏情况下，对于每个节点，都要考虑是否选择当前边，因此时间复杂度为 O(2^m)，其中 m 为边的数量。
    空间复杂性：
    - O(n + m)，主要由递归调用和存储结果列表所占空间。
  2. path_dfs函数
    
    时间复杂性：
    - 在最坏情况下，需要遍历所有可能的路径，时间复杂度为 O(n!)，其中 n 为节点的数量。
    空间复杂性：
    - O(n)，主要由递归调用和存储结果列表所占空间。
  3. construct_path函数
    
    时间复杂性：
    - 该函数在最坏情况下需要遍历整个路径，时间复杂度为 O(n)，其中 n 为路径的长度。
    空间复杂性：
    - O(n)，主要由存储路径的列表所占空间。
  4. dijkstra函数
    
    时间复杂性：
    - 由于使用了堆优化的Dijkstra算法，时间复杂度为 O((n + m) * log(n))，其中 n 为节点数量，m 为边数量。
    空间复杂性：
    - O(n)，主要由存储最短路径长度、前驱节点和优先队列所占空间。
  5. postman函数
    
    时间复杂性：
    - 该函数的主要复杂度来自DFS、Dijkstra以及对最大匹配的搜索。DFS的时间复杂度为 O(2^odd)，其中 odd 为奇数度节点的数量。Dijkstra的时间复杂度为 O((n + m) log(n))。因此，总体时间复杂度为 O((n + m) log(n) + 2^odd)。
    空间复杂性：
    - O(n + m + odd^2)，主要由存储图结构、路径信息和Dijkstra算法的空间占用。
  6. search函数
    
    时间复杂性：
    - 在最坏情况下，需要遍历所有可能的路径，时间复杂度为 O(n!)，其中 n 为节点的数量。
    空间复杂性：
    - O(n)，主要由递归调用和存储结果列表所占空间。
  7. 主函数部分：
    
    时间复杂性：
    - 主程序主要调用了上述函数，因此总体时间复杂度取决于这些函数的复杂度。
    空间复杂性：
    - O(n + m)，主要由存储图结构和结果列表所占空间。
实际性能可能会受到不同输入情况的影响。
需要注意的是，这些复杂度分析是基于最坏情况下的情形，实际运行中可能会受到具体输入数据的影响。

（五）实验结果

（六）实验总结

在完成这个实验的过程中，我深刻体会到了解决复杂图论问题的挑战和乐趣。以下是一些实验总结的要点：
1. 复杂问题的分解：
  
  图论问题通常涉及多个步骤和算法的组合。通过合理的分解问题，将其划分为更小的子问题，有助于更好地理解和解决整体问题。在这个实验中，中国邮递员问题被分解为寻找所有可能路径、计算最短路径、最大匹配等多个子问题。
2. 深度优先搜索与动态规划：
  
  深度优先搜索在图论问题中具有广泛的应用。通过深度优先搜索，可以找到图中的所有路径，从而解决一些组合型问题。动态规划则可以用于记录中间结果，避免重复计算，提高算法效率。
3. 算法的选择与优化：
  
  在处理图论问题时，选择合适的算法非常关键。例如，在中国邮递员问题中，选择了深度优先搜索和Dijkstra算法来解决子问题。此外，通过使用堆优化的Dijkstra算法，提高了寻找最短路径的效率。
4. 调试与测试：
  
  在编写复杂的程序时，调试和测试是不可或缺的环节。通过逐步调试，检查算法的正确性，发现并修复潜在的错误。编写一些简单但具有代表性的测试用例，验证算法在不同情况下的鲁棒性。
5. 空间与时间复杂度的权衡：
  
  在解决问题时，需要综合考虑算法的时间复杂度和空间复杂度。有时候，为了提高运行效率，可能需要占用更多的空间，这是一个常见的权衡问题。
6. 编码规范与可读性：
  
  写出清晰、规范、可读性高的代码是良好编程实践的一部分。良好的代码风格和注释有助于他人理解代码，也有助于自己在后续维护和修改时更容易理解代码逻辑。
总的来说，通过这个实验，我对图论问题的解决方法有了更深入的了解，也提高了对复杂问题分析和解决的能力。同时，实验中的调试和测试过程让我更加注重代码的质量和稳定性。这对于日后处理更加复杂的问题将是非常宝贵的经验。

参考文献：离散数学II实验四：白

离散数学II实验三（Python/C++）

实验三

（一）实验题目

（二）实验目的

（三）实验要求

（四）实验内容和实验步骤

1、需求分析

2、 概要设计

3、详细设计

Python:

C++:

4、调试分析

（五）实验结果

（六）实验总结

2、概要设计