找回密码
 注册
搜索
热搜: 回贴
  • 前程无忧官网首页 有什么好的平台可以
  • 最新的销售平台 互联网营销的平台有哪
  • 制作网页的基本流程 网页制作和网页设
  • 【帝国CMS】输出带序号的列表(数字排
  • 网站建设公司 三一,中联,极东泵车的
  • 织梦 建站 织梦网站模版后台怎么更改
  • 云服务官网 哪些网站有免费的简历模板
  • 如何建网站要什么条件 建网站要用什么
  • 吉林市移动公司电话 吉林省退休人员网
  • 设计类毕业论文 网站设计与实现毕业论
查看: 1116|回复: 0

请求各位高手帮忙 实现无向图的深度优先遍历、广度优先遍历

[复制链接]
发表于 2009-11-3 23:56:23 | 显示全部楼层 |阅读模式 IP:江苏扬州
要求:实现无向图的深度优先遍历、广度优先遍历。
输入:图的顶点及边的信息。
输入格式:
第一行输入一个正整数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.        存储结构:可采用数组表示法或邻接表表示法。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|最新主题|手机版|微赢网络技术论坛 ( 苏ICP备08020429号 )

GMT+8, 2024-9-30 19:26 , Processed in 0.285402 second(s), 13 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表