泛型应用--图的深度(广度)优先遍历.成语接龙例子,含代码下载.
已知点集合 V={v1,v2,v3...vn}通过边连接起来
深度优先模型：
void Find1(v)
{
while(广度++)
{
Find1(新找到的点);//递归
}
}
可以看出他先把某一分支的第一分支一直搜到底，再搜第2分支的第一。。。。
广度优先模型：
声明全局点集合 R={r0}初始为出发节点。
void Find2(r)
{
while(广度++)
{
R.添加(新找到的点);
}
R.移除(旧的点);
while(新广度++)
{
Find2(r);//递归
}
}
以下边图为例：
1
/ \
2 3
/ \ |\
4 5 6 7
深度优先的执行顺序是：
1245367
广度优先是：
1234567
深度优先一般适合查找最长路径。成语接龙例子就是深度优先.
广度优先一般适合查找最短路径或者找到就退出，比较常用。
成语接龙的思路是:
0,分析全部成语,把头尾汉字用Unicode转成数字,再减去short.Maxvalue使其分布在short范围内,以节省内存.如果用string是比较废内存的.
1,利用泛型容器Dictionary查找Key速度是O(1)的哈希散列特点,建立两个字典,一个是全部成语,一个是头索引的多个成语.
2,输入一个成语后点按钮,把尾节点作为头,深度优先搜索.(排除环,检测有环复杂度O(1))
3,每一分钟检查一下是否有更长的龙出现.
代码下载
http://www.dullwolf.cn/Idiom.rar
本程序肯定有不足之处,希望大家友好的批评指正.
[解决办法]
顶，非常有用
举个深度查询在数据库中运用的例子 ：
下面是SYS_Organ机构表，包含ID\SuperiorID\Name 等字段，输入任意一个机构编号ID，可以查找到所以他的上级的编号
declare @ID int set @ID =15declare @Level int set @Level = 0declare @t table (ID int ,L int )insert into @t(ID,L )values ( @ID,@Level)declare @ParentID int while @@ROWCOUNT >0begin set @Level =@Level+1 insert into @t select SuperiorID,@Level from SYS_Organ AS A,@t as b where A.ID =b.ID and B.L=@Level-1 end select * from @t where ID<>0 ORDER BY L DESC declare @s nvarchar(500) set @s =''select @s=@s+ISNULL(B.Name,'')+'->' from @t AS A LEFT JOIN SYS_Organ AS B ON A.ID =B.ID where A.ID<>0ORDER BY A.L DESCprint @s
[解决办法]
好厉害啊，收藏了
[解决办法]
接分 学习
[解决办法]
楼上不厚道
应该是
学习 接分
[解决办法]
接分 学习
[解决办法]
没有遇到过类似的问题,顶起来,关注
[解决办法]
学习～
[解决办法]
? 牛人一个呀 学习...... 学习......
[解决办法]
赞一个楼主强人啊
[解决办法]
强贴,收藏了.
[解决办法]
jf
[解决办法]
学习
[解决办法]
很不错，谢谢斑竹。
可是为什么你的原程序下下来不能用呢。
警告1未能找到引用的组件“System.Core”。
警告2未能找到引用的组件“System.Xml.Linq”。
错误3命名空间“System”中不存在类型或命名空间名称“Linq”(是缺少程序集引用吗?)C:\Documents and Settings\linc\桌面\Idiom\Idiom\Form1.cs614Idiom
错误4命名空间“System”中不存在类型或命名空间名称“Linq”(是缺少程序集引用吗?)C:\Documents and Settings\linc\桌面\Idiom\Idiom\Program.cs314Idiom
错误5命名空间“System”中不存在类型或命名空间名称“Linq”(是缺少程序集引用吗?)C:\Documents and Settings\linc\桌面\Idiom\Idiom\Idioms.cs314Idiom
[解决办法]
理论联系实际
:)
------解决方案--------------------
关注
[解决办法]
学习...
[解决办法]
来, 仰慕下下
[解决办法]
下载 学习 接分
[解决办法]
顶
[解决办法]
学习.接分
[解决办法]
学习 接分
[解决办法]
收藏！
[解决办法]
学习学习
[解决办法]
学习 接分，同时
[解决办法]
收藏了
[解决办法]
收藏收藏 学习学习
太厉害了
[解决办法]
mark
[解决办法]
学习， 接分
[解决办法]
关注...
[解决办法]
收藏
[解决办法]
学习.
[解决办法]
学习中，好强
[解决办法]
向大笨狼学习。
[解决办法]
好贴，顶一个先。
[解决办法]
再顶.
[解决办法]
向大笨狼学习。
[解决办法]
受益了
[解决办法]
学一下..
[解决办法]
这个程序最大的亮点不是标题中的"深度优先,广度优先".而是将成语的头和尾拿出来,并且做一个减法运算,进而减少内存的使用量.看起来是这样,只是在程序初始化的时候所消耗的资源是比较可观的.还有就是既然以成语接龙为例子,这个程序忽略了一点:成语接龙只需要音同/相近即可,所以你可以把头尾转换成拼音,虽然会比现在要多耗一点资源,但是更能贴近实际一点.不管是深度优先还是广度优先,都可以算是递归的一个应用.只是要套用遍历的规则而已,所以最根本的还是对递归的理解,而不要迷失在程序中
[解决办法]
学习 接分
[解决办法]
收藏
[解决办法]
收藏不了
[解决办法]
mark
[解决办法]
up
[解决办法]
Study
[解决办法]
up
[解决办法]
2楼的SQL也是相当强悍啊~
[解决办法]
学习!
------解决方案--------------------
学习
[解决办法]
关注中,回头研究!
[解决办法]
一个简单的树形查找！
技术难度有如此之深么？
如果涉及组合优化数据建模不是要惊为天人啦？
做人要厚道些
[解决办法]
会不会出现死循环？
如：
...->善者不来->来者不善->善者不来->来者不善->...
或
...->善者不来->来去自如->....->善者不来->...
[解决办法]
学习...... 学习......
[解决办法]
mark,mark
必须得mark一下
[解决办法]
mark
[解决办法]
理解了就能应用了
不错
[解决办法]
收藏！
[解决办法]
TO:gxj760998
拜托 你要看这是在那，在CSDN这算有水平的了。
回头来个用冒泡来眩的 也有一大群人说高手的。
[解决办法]
顶
[解决办法]
学习、接分
[解决办法]
学习
[解决办法]
up
[解决办法]
收藏!
[解决办法]
bucuo o
[解决办法]
有人说2楼数据库牛~~
俺就不服气了就那点简单的代码,基础啊...
现在的风气啊....
顺便说下楼主给怎么高的分想干什么........
[解决办法]
与42楼同感，不过真的很佩服楼主，俺咋就想不出来这么个算法捏~ ~|||
[解决办法]
S收藏一下
[解决办法]
学习，收藏了。
[解决办法]
自己写的成语接龙只接了几十个成语....学习...
谢谢我们老大都是无私的精神.把自己写的比较实用的程序都在CSDN同大家分享.....
[解决办法]
mark
[解决办法]
不错不错
[解决办法]
飘过
[解决办法]
极品,有内涵,下了在说.
[解决办法]
看看
[解决办法]
mark
[解决办法]
这么多年了，挖坟的人还是这么热心啊。
[解决办法]
up~
[解决办法]
学习.接分
[解决办法]
MMARK
[解决办法]
不懂，但是还是留名。
------解决方案--------------------
学习
[解决办法]
学习
[解决办法]
学习中。。。。
[解决办法]
强学习
[解决办法]
错误3'System.Collections.Generic.Dictionary<short,short>' does not contain a definition for 'Last'C:\Documents and Settings\Administrator\桌面\Idiom\Idiom\Form1.cs6533Idiom
我人品有问题？
学习学习
[解决办法]
学习中。。。。
[解决办法]
mark
上次去华为面试 面到最后一个 ，面试官问的就是树的广度优先遍历：
想了老久，才反应过来 用一个队列就能搞定了了
先将树的根进队列
然后 循环出队列(得到一个子树) 直到队列为空
{
1、DoSomething( 子树的根)
2、左树进队列
3、右树进队列 (如果不是二叉树，就依次进队列)
}
[解决办法]
好的是分享技术，而不是技术本身，技术更好，那叫什么？出彩嘛
说闲话的可以歇歇了
[解决办法]
Mark
[解决办法]
关注
[解决办法]
根本没有涉及到 如何判断成语可以最长的代码，其实可以最长的代码的算法也很简单，根本不需要每分钟计算一次，
我不知道现在大家都学不学功课，可能用贪婪算法就可以基本找出比较长成语不重复的算法。
当然了，贪婪法在这个问题上得不到最大解，可能只会接近。
我也学的不好，没有分析出如何找最长应该用什么方法，但是剪枝算法肯定不行，动态规划也够呛，找最短路径应该很容易可以实现
找最长在这样大数据量下的问题还真不太清楚。
可以考虑如下结点结构
struct point
{
next[]
in[]
next_count = next.count;
in_count = in.count;
}
当使用过一个结点后，删除这个point，同时遍历所有的in，删除里面next[]对应的元素，且对应的next_count --
至于用什么算法就不知道了，我想只要是计算机系学过算法的研究生应该比我明白吧？
[解决办法]
抢个100楼，呵呵
