#include "stdafx.h"
#include <time.h>
#include<iostream>
#include<ctime>
#include<algorithm>
#include <stdlib.h>
#include<string>
#include <cstdio>
#include <fstream>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <cstring>
#include <map>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define M 202
#define INF 100000001
using namespace std;
int v0[10000];
int u0[10000];;
int m = 0;
int n = 0;
int cout0 = 0;
typedef long long ll;
struct stack
{
int top, node[M];
}s;
int e[M][M];
int suiji[3][10000];
void RAND(int max, int min, int n)
{
srand((unsigned)time(NULL));
for (int i = 1; i <= max; ++i)
{
for (int j = 1; j <= i; ++j)
if (i != j)
{
suiji[0][cout0] = j;
suiji[1][cout0] = i;
cout0++;
}
}
int c = 2;
int j = 0;
int c1 = 0;
srand((unsigned)time(NULL));
for (int i = 0; i<n; i++)
{
suiji[2][i] = 3;
}
suiji[2][0] = 2;
while (j<n)
{
suiji[2][j + c] = 2;
j = j + c;
c1++;
c++;
if (c1 == max - 2)
{
suiji[0][n - 1] = 2;
}
}
}
void dfs(int x)
{
int i;
s.node[++s.top] = x;
for (i = 0; i<n; i++)
{
if (e[i][x]>0)
{
e[i][x] = e[x][i] = 0; //删除这条边
dfs(i);
break;
}
}
}
void fleury(int x)
{
int i, flag;
s.top = 0; s.node[s.top] = x;
while (s.top >= 0)
{
flag = 0;
for (i = 0; i<n; i++)
{
if (e[s.node[s.top]][i]>0)
{
flag = 1;
break;
}
}
if (!flag) printf("%d ", s.node[s.top--] + 1);
else dfs(s.node[s.top--]);
}
puts("");
}
//检验输入边数和顶点数的值是否有效,可以自己推算为啥:
//顶点数和边数的关系是:((Vexnum*(Vexnum - 1)) / 2) < edge
bool check(int Vexnum, int edge) {
if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
return false;
return true;
}
//顶点从1开始编号
bool check_edge(int Vexnum, int start, int end, int weight) {
if (start<1 || end<1 || start>Vexnum || end>Vexnum || weight < 0) {
return false;
}
return true;
}
//边集结构,用于保存每条边的信息
typedef struct edge_tag {
bool visit; //判断这条边是否加入到了最小生成树中
int start; //该边的起点
int end; //该边的终点
int weight; //该边的权重
}Edge;
//创建一个图,但是图是使用边集结构来保存
void createGraph(Edge * &e, int Vexnum, int edge) {
e = new Edge[edge];//为每条边集开辟空间
int start = 0;
int end = 0;
int weight = 0;
int i = 0;
while (i != edge)
{
start = suiji[0][i];
end = suiji[1][i];
weight = suiji[2][i];
cout << start << " " << end << " " << weight;
cout << " | ";
while (!check_edge(Vexnum, start, end, weight)) {
cout << "输入的值不合法,请重新输入每条边的起点、终点和权重:" << endl;
start = suiji[0][i];
end = suiji[1][i];
weight = suiji[2][i];
}
e[i].start = start;
e[i].end = end;
e[i].weight = weight;
e[i].visit = false; //每条边都还没被初始化
++i;
}
}
int cmp(const void* first, const void * second) {
return ((Edge *)first)->weight - ((Edge *)second)->weight;
}
int find_root(int child, int * parent) {
if (parent[child] == child) {
return child;
}
parent[child] = find_root(parent[child], parent);
return parent[child];
}
bool union_tree(Edge e, int * parent, int * child) {
//先找出改边所在子树的根节点
int root1;
int root2;
//记住我们顶点从1开始的,所以要减1
root1 = find_root(e.start - 1, parent);
root2 = find_root(e.end - 1, parent);
//只有两个顶点不在同一颗子树上,才可以把两棵树并未一颗树
if (root1 != root2) {
//小树合并到大树中,看他们的孩子个数
if (child[root1] > child[root2]) {
parent[root2] = root1;
//大树的孩子数量是小树的孩子数量加上
//大树的孩子数量在加上小树根节点自己
child[root1] += child[root2] + 1;
}
else {
parent[root1] = root2;
child[root2] += child[root1] + 1;
}
return true;
}
return false;
}
void Kruskal() {
int Vexnum = 0;
int edge = 0;
cout << "请输入图的顶点数和边数:" << endl;
cin >> Vexnum >> edge;
cout << "下面为随机生成的完全图(依次为起点,终点,权值):" << endl;
while (!check(Vexnum, edge)) {
cout << "你输入的图的顶点数和边数不合法,请重新输入:" << endl;
cin >> Vexnum >> ed�
没有合适的资源?快使用搜索试试~ 我知道了~
满足三角不等式的TSP问题的近似算法
共55个文件
tlog:12个
cpp:6个
pdb:4个
5星 · 超过95%的资源 需积分: 5 59 下载量 115 浏览量
2018-07-15
21:00:42
上传
评论 19
收藏 5.37MB ZIP 举报
温馨提示
完美版满足三角不等式的TSP问题的近似算法,内部含有课程设计报告和源程序,适合大学数据与算法分析课程学习。 满足三角不等式的TSP问题的近似算法: (1)描述及输入原始数据模块 (2)求解最小生成树模块 (3)构造欧拉图模块 (4)搜索欧拉回路模块 (5)抄近路计算模块 (6)存储及输出结果模块
资源推荐
资源详情
资源评论
收起资源包目录
满足三角不等式的TSP问题的近似算法.zip (55个子文件)
满足三角不等式的TSP问题的近似算法
.vs
满足三角不等式的TSP问题的近似算法
v15
Browse.VC.db 6.75MB
.suo 30KB
ipch
1833d73b8401f2b2.ipch 3.5MB
满足三角不等式的TSP问题的近似算法
stdafx.cpp 338B
满足三角不等式的TSP问题的近似算法.cpp 11KB
stdafx.h 366B
targetver.h 370B
满足三角不等式的TSP问题的近似算法.vcxproj.filters 1KB
满足三角不等式的TSP问题的近似算法.vcxproj 8KB
满足三角不等式的TSP问题的近似算法.vcxproj.user 165B
Debug
满足三角不等式的TSP问题的近似算法.pch 2.88MB
stdafx.obj 7KB
满足三角不等式的.F8676F62.tlog
CL.write.1.tlog 1KB
CL.read.1.tlog 15KB
CL.command.1.tlog 2KB
link.write.1.tlog 744B
满足三角不等式的TSP问题的近似算法.lastbuildstate 248B
link.command.1.tlog 1KB
link.read.1.tlog 3KB
vc141.idb 187KB
vc141.pdb 420KB
满足三角不等式的TSP问题的近似算法.log 254B
满足三角不等式的TSP问题的近似算法.obj 67KB
满足三角不等式的TSP问题的近似算法.cpp 11KB
报告.doc 286KB
满足三角不等式的TSP问题的近似算法.sln 2KB
满足三角不等式的TSP问题的近似算法-程序
.vs
满足三角不等式的TSP问题的近似算法
v15
Browse.VC.db 248KB
.suo 20KB
ipch
1833d73b8401f2b2.ipch 3.5MB
满足三角不等式的TSP问题的近似算法
stdafx.cpp 338B
满足三角不等式的TSP问题的近似算法.cpp 11KB
stdafx.h 366B
targetver.h 370B
满足三角不等式的TSP问题的近似算法.vcxproj.filters 1KB
满足三角不等式的TSP问题的近似算法.vcxproj 8KB
满足三角不等式的TSP问题的近似算法.vcxproj.user 165B
Debug
满足三角不等式的TSP问题的近似算法.pch 2.88MB
stdafx.obj 7KB
满足三角不等式的.F8676F62.tlog
CL.write.1.tlog 1KB
CL.read.1.tlog 15KB
CL.command.1.tlog 2KB
link.write.1.tlog 744B
满足三角不等式的TSP问题的近似算法.lastbuildstate 248B
link.command.1.tlog 1KB
link.read.1.tlog 3KB
vc141.idb 187KB
vc141.pdb 420KB
满足三角不等式的TSP问题的近似算法.log 254B
满足三角不等式的TSP问题的近似算法.obj 67KB
满足三角不等式的TSP问题的近似算法.cpp 11KB
满足三角不等式的TSP问题的近似算法.sln 2KB
Debug
满足三角不等式的TSP问题的近似算法.pdb 668KB
满足三角不等式的TSP问题的近似算法.ilk 420KB
Debug
满足三角不等式的TSP问题的近似算法.pdb 668KB
满足三角不等式的TSP问题的近似算法.ilk 420KB
共 55 条
- 1
资源评论
- 大路朝天,勇往直前2018-11-08被迫评论,有啥内容忘了
薛定谔的小毛球
- 粉丝: 48
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 王锐的《OpenSceneGraph 3.0 Beginner's Guide》中文翻译版,个人读了翻译的很不错!值得推荐
- scr ubuntu上传
- AI Python编程学习课件-第6章深度学习
- STM32单片机FPGA毕设电路原理论文报告液晶显示模块与8031单片机的接口电路及编程
- STM32单片机FPGA毕设电路原理论文报告液晶航向指示器接口电路设计
- Pytorch深度学习入门与实战2024
- STM32单片机FPGA毕设电路原理论文报告野战救护车手术台稳定液压系统及其自动控制
- STM32单片机FPGA毕设电路原理论文报告压延机卷取调速装置改造
- STM32单片机FPGA毕设电路原理论文报告形状记忆合金驱动的微电脑密码锁的设计
- HTML小游戏27 - Chuck Chicken 魔法蛋网页游戏源码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功