黑马程序员技术交流社区

标题: 图的遍历问题 [打印本页]

作者: 周磊 时间: 2012-7-16 19:35
标题: 图的遍历问题
一个大于2000个节点的图，求遍历所有节点的最短路径（过每一个节点），实在想不出来啊，求教下

作者: 陈世涛 时间: 2012-7-16 19:42
这涉及到图的存储表示问题，
假如图中每个节点只能有不超过n条边，
那么对应的结构体至少应该含有n个指向该类型节点的指针，
这时可以通过遍历此图获得距离和路径信息。
路径数组（2维）：
若有n个节点，数组可定义为int a[n][n]，
若第i个节点跟第j个节点连同，则执行a[i][j]=1；否则a[i][j]=0。
距离数组（2维）：
同理，定义为b[n][n]，对第i个节点跟第j个节点，
若a[i][j]=1，表示两点相连，那么b[i][j]赋以正确的距离（值记录在节点信息中或者已知），
否则，令b[i][j]=100000，“100000”表示无穷的近似值。

希望对楼主有帮助。

作者: 周磊 时间: 2012-7-16 19:49
不是这样的啊，20000多个节点，任意两个节点都可以相连，数据量太大了，有没有什么算法可以解决？

作者: 张_涛 时间: 2012-7-16 20:09
首先，认为每个节点之间是没有连接的。
1.将所有节点之间的距离按照从小到大进行排序
2.依次取出最小距离，将最小距离的两个节点作标记，若出现了与前面已经作了标记的点相同，则同时作之前的标记，即每次将联通的点作同一的标记。
3.不断重复2步骤，直到所有的点的标记相同。
还有一种方法，如下
1.取任意一个点开始，找连接该点最短的距离，将连接的两个节点放到一个集合中。
2.接着以1步骤中连接的另一个点重复1步骤，直到集合包含了所有的节点。
希望对你有所帮助，在算法中，这是两个主要的思想，具体的你可以网上搜素下资料。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2