泛型施用-图的深度(广度)优先遍历.成语接龙例子,含代码下载

泛型应用--图的深度(广度)优先遍历.成语接龙例子,含代码下载.

已知点集合 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，可以查找到所以他的上级的编号

SQL code

declare @ID int 
set @ID =15

declare @Level int 
set @Level = 0
declare @t table (ID int ,L  int )
insert into @t(ID,L )values ( @ID,@Level)


declare @ParentID int 
while @@ROWCOUNT >0
begin
    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<>0
ORDER BY A.L DESC
print @s

------解决方案--------------------
好厉害啊，收藏了

------解决方案--------------------
接分 学习

------解决方案--------------------
楼上不厚道
应该是
学习 接分

------解决方案--------------------
接分 学习

------解决方案--------------------
没有遇到过类似的问题,顶起来,关注

------解决方案--------------------
学习～

------解决方案--------------------
?   牛人一个呀  学习......   学习......

------解决方案--------------------
赞一个楼主强人啊

------解决方案--------------------
强贴,收藏了.

------解决方案--------------------
jf

------解决方案--------------------
学习

------解决方案--------------------
很不错，谢谢斑竹。
可是为什么你的原程序下下来不能用呢。
警告	1	未能找到引用的组件“System.Core”。	
警告	2	未能找到引用的组件“System.Xml.Linq”。	
错误	3	命名空间“System”中不存在类型或命名空间名称“Linq”(是缺少程序集引用吗?)	C:\Documents and Settings\linc\桌面\Idiom\Idiom\Form1.cs	6	14	Idiom
错误	4	命名空间“System”中不存在类型或命名空间名称“Linq”(是缺少程序集引用吗?)	C:\Documents and Settings\linc\桌面\Idiom\Idiom\Program.cs	3	14	Idiom
错误	5	命名空间“System”中不存在类型或命名空间名称“Linq”(是缺少程序集引用吗?)	C:\Documents and Settings\linc\桌面\Idiom\Idiom\Idioms.cs	3	14	Idiom

------解决方案--------------------
理论联系实际
:)

------解决方案--------------------

泛型施用-图的深度(广度)优先遍历.成语接龙例子,含代码下载

相关推荐