| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 448 人关注过本帖
标题:求助大家一个图论的算法问题!求好心人指点!
只看楼主 加入收藏
wuyan08
Rank: 1
等 级:新手上路
帖 子:4
专家分:5
注 册:2010-11-10
收藏
 问题点数:0 回复次数:6 
求助大家一个图论的算法问题!求好心人指点!
我需要实现的功能是每加入一个顶点同时生成新顶点与图 G`所有顶点的有向路经,问题描述如下:
该图为有向图,一个点在图中就是A,两个点就增加了B,BA,即一个新点和一条路径,三个点的话就增加C,CA,CB,CBA,即一个新点,3条新的有向图路径,四个点就增加D,DA,DB,DC,DBA,DCA,DCB,DCBA,如果描述的不够明白的话大家画画图就知道我的意思了,每增加一个点到图中,生成所有的的有向路径,请问大家有没有什么好的办法可以推荐呢,新手真心求教!!谢谢好心人了!!
要求就是尽量能够快速的检索出来,节省内存,大概有1K+个点用什么方法最好,谢谢好心人!!!
搜索更多相关主题的帖子: 算法 图论 
2010-11-10 16:36
wujieru
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:1
帖 子:1108
专家分:1939
注 册:2010-10-9
收藏
得分:0 
好心人都死光了
2010-11-10 18:29
yxwsbobo
Rank: 5Rank: 5
等 级:职业侠客
帖 子:345
专家分:306
注 册:2007-10-29
收藏
得分:0 
全排列吧

How are you 怎么是你?
How old are you   怎么老是你?
2010-11-11 08:18
韭菜
Rank: 2
等 级:论坛游民
帖 子:51
专家分:94
注 册:2010-9-26
收藏
得分:0 
个人见解  欢迎点评
楼主说要有1000多个点 这都是要占据空间的的

另外一条路径也是要占据内存空间的啊  选取m项组合  按照组合公式就有C(m,n)=n!/m!*(n-m)!  1k 想想就恐怖
2010-11-11 11:08
韭菜
Rank: 2
等 级:论坛游民
帖 子:51
专家分:94
注 册:2010-9-26
收藏
得分:0 
我的想法就是 通过数组之间的拷贝来实现  但是在过程中会大量使用strcat
2010-11-11 12:19
wuyan08
Rank: 1
等 级:新手上路
帖 子:4
专家分:5
注 册:2010-11-10
收藏
得分:0 
继续顶,希望有知道的人帮帮忙!
2010-11-11 16:41
浩凡儿
Rank: 5Rank: 5
等 级:职业侠客
威 望:1
帖 子:101
专家分:394
注 册:2010-10-30
收藏
得分:0 
可用下图的深度遍历吧可先设个字符数组并作为结枸体的一个成员一个可这样式  
struct st
{
char a[];
int weight
other num;

} node;   且把这些结枸体的权值设为0;
放结点初始为空每加一个把结点加入就查找权值为0的与其形成边;
再循环把各结点权值设为0如此循环
对于这方面的要太简单的俺不太会也是刚接触可看下
2010-11-12 17:32
快速回复:求助大家一个图论的算法问题!求好心人指点!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029971 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved