数据结构和算法《欢迎高手来挑战》回帖有奖哦

梦幻一生 · 发表于 2016-3-6 19:27:20

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

问题描述：
对一个顶点数<=600的有向图，每个顶点的出度不超过8

设顶点集为V，现从V中随机抽取60个顶点构成顶点集V'，随机给定源点（source）和汇点（destination）；

要求从源点出发，到达汇点，经过V'中所有顶点的最小路径。（可以经过V'外的其他点）

我的思路一，暴力法
找出从源点到汇点的所有路径，找出包含V'的一条路径

思路二找出一个出度和入度的最小生成树

求各位大神各抒己见。愿大神间的交流能擦出不一样的火花

DAY · 发表于 2016-3-6 19:35:58

回溯算法。。。

梦幻一生 · 发表于 2016-3-6 21:06:18

DAY 发表于 2016-3-6 19:35
回溯算法。。。

要不写个代码试试，看得花多长时间

DAY · 发表于 2016-3-6 21:36:10

其实我也不是很懂回溯算法，
正在自学中。。。。

梦幻一生 · 发表于 2016-3-6 21:58:08

DAY 发表于 2016-3-6 21:36
其实我也不是很懂回溯算法，
正在自学中。。。。

哈哈，一起学习。主要是顶点多，不然就好办了

错过会难过 · 发表于 2016-3-7 09:31:26

判断一个传入的点是不是汇点,是则将汇点入栈 ,
如果不是, 则将传入的点生成8个点 , 循环传入函数
代码大概是这样吧 , 没经过调试 , 会有bug

int g_endX = 10; // 给定终点的位置
int g_endY = 10; // 给定终点的位置
bool int findEndPointer(int x,int y , Stack& stcStack/*一个栈的类*/)
{
if(x == g_endX && y == g_endY)
return true;
for(int i = 0 ;i<3;++i)
{
for(int j = 0 ;j < 3;++j)
{
if(true == findEndPointer(x+j,y+i,stcStack))
{
stcStack.push(x+j,y+i); /*将终点保存*/
return true; /*返回true , 让上一层函数也能保存一个点*/
}
}
}
return false;
}

复制代码

梦幻一生 · 发表于 2016-3-7 14:54:07

错过会难过发表于 2016-3-7 09:31
判断一个传入的点是不是汇点,是则将汇点入栈 ,
如果不是, 则将传入的点生成8个点 , 循环传入函数
代码 ...

不好意思，这个我没看懂，，如何找到符合v'集合中顶点的最短路径。。。也没见你输入来着

梦幻一生 · 发表于 2016-3-8 11:48:28

我自己找到办法，谢谢各位

丿絕 · 发表于 2016-3-20 10:51:12

楼主厉害我很崇拜

atmo · 发表于 2016-3-28 22:38:31

楼主厉害我很崇拜

小小小菜菜菜 · 发表于 2018-12-20 19:31:58

观摩

X用户 · 发表于 2018-12-22 08:45:23

顶一下

扩展阅读 · 发表于 2018-12-24 11:45:15

小白进来观摩

扩展阅读 · 发表于 2018-12-24 11:46:52

我都看不懂题目...

熊宝宝要当红军 · 发表于 2019-8-14 08:24:57

顶一下

snl · 发表于 2019-8-18 09:12:26

都不知道我还要学多久才有大佬们的水平

隔壁繁星吖 · 发表于 2019-8-20 20:56:53

自学ing......

心驰神往 · 发表于 2020-11-3 16:00:56

挑战不了

心驰神往 · 发表于 2020-11-3 16:01:52

拿个鱼币

心驰神往 · 发表于 2020-11-3 16:02:26

这运气···

账号		自动登录	找回密码
密码			立即注册

数据结构和算法《欢迎高手来挑战》回帖有奖哦

马上注册，结交更多好友，享用更多功能^_^

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币

回帖奖励 +5 鱼币


55 鱼币	回复本帖可获得 5 鱼币奖励! 每人限 1 次(中奖概率 40%)