| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3665 人关注过本帖
标题:请求各位高手帮忙 实现无向图的深度优先遍历、广度优先遍历
只看楼主 加入收藏
linzhaoshen
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2007-11-26
收藏
 问题点数:0 回复次数:2 
请求各位高手帮忙 实现无向图的深度优先遍历、广度优先遍历
要求:实现无向图的深度优先遍历、广度优先遍历。
输入:图的顶点及边的信息。
输入格式:
第一行输入一个正整数n,表示图的顶点个数。
第二行输入一个正整数e,表示图的边的条数。
接下来有e行,每行分别有两个数v1,v2,表示编号为v1的点跟编号为v2的边之间有一条边相连。(0<=v1, v2 <= n-1)
输出:图的深度优先遍历序列、广度优先遍历序列,要求输出顶点编号。(存在多种遍历序列,只需要输出其中一种即可。)
输出格式:输出有两行,第一行是深度优先遍历序列,第二行是广度优先遍历序列,顶点编号之间用空格隔开。

例:输入:
6
5
0 1
0 2
0 3
1 2
4 5
输出:0 1 2 3 4 5
      0 1 3 2 4 5
分析:上述输入数据,对应于以下的图:
   V1          V2                  V6
       |    \         |                      |
       |        \     |                      |
   V4          V3                  V5
其中一种深度优先遍历序列为V1 V2 V3 V4 V5 V6。对应的顶点编号为0 1 2 3 4 5。所以第一行输出0 1 2 3 4 5。
其中一种广度优先遍历序列为V1 V2 V4 V3 V5 V6。对应的顶点编号为0 1 3 2 4 5。所以第二行输出 0 1 3 2 4 5。
注意:
1.        可假设输入数据均为合法数据。
2.        存储结构:可采用数组表示法或邻接表表示法。
搜索更多相关主题的帖子: 遍历 深度 请求 
2007-12-09 14:56
用户名
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2005-3-3
收藏
得分:0 
先把图建起来,用数组方法要简单点,然后参考数据结构书上的深度优先和广度优先算法,题目不难,看看书把算法看懂的就可以写程序了,由于篇幅太大,你还得自己写的哦!
2007-12-10 10:41
zhou
Rank: 1
等 级:禁止发言
帖 子:429
专家分:0
注 册:2006-6-16
收藏
得分:0 
提示: 作者被禁止或删除 内容自动屏蔽
2008-03-30 17:00
快速回复:请求各位高手帮忙 实现无向图的深度优先遍历、广度优先遍历
数据加载中...
 
   



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

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