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

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

问题描述：
对一个顶点数<=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
回溯算法。。。

要不写个代码试试，看得花多长时间{:5_109:}

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

{:10_245:}{:10_245:}我都看不懂题目...

熊宝宝要当红军 发表于 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

拿个鱼币{:10_256:}

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

这运气···
页: [1]
查看完整版本: 数据结构和算法《欢迎高手来挑战》回帖有奖哦