图的深度优先遍历

作者:袖梨 2022-07-02

/* 这是一个图的的深度优先搜索,我参考清华大学 c 语言版 1997年 4月第一版
   教材中没有构图的函数CreatGraph(),FirstAdjVex()和NextAdjvex(),我在这里写出来了
。
   图的存储结构采用邻接表存储。不过构图时的输入比较复杂,请读者认真读以下说明
   说明:

   假设有顶点 a(1) b(2) c(3) d(4) e(5)
   图如下:
                 (1)
                 (a)
                 /|^                 / |                 /  |                 /   |                 /    |                 /    |     /
        (2)(b)----|----->(c)(3)
                  |        
                 /             
                 (e)------>(d)
                 (5)       (4)
   请注意输入时依次输入5个顶点a b c d e,结束输入请输入0,0然后在插入邻接点,邻接
点为插头操作。
   插入邻接点的操作如下:
                       1,5(逗号也输入)1,3       1,2
                       2,3
                       
                       4,1
                       5,4
                       0,0(表示结束输入)

   其的存储结构是:
        (0)[][NULL]
        (1)[a][]-->[2][]->[3][]-->[5][NULL]
        (2)[b][]-->[3][NULL]  
        (3)[c][NULL]
        (4)[d][]-->[1][NULL]
        (5)[e][]-->[5][]-->[4][NULL]
   遍历的顺序如下:
   假如从1号顶点开始遍历:a b c e d

*/
/* 我没有写结点访问函数,因为在这个程序中结点的访问是输出其值,如果你要一个访问函
数可以稍加修改*,我还是一个,
   让高手见笑了
   这只是举一个例子,明白后你可以通过MAXVER ,注意要有5各顶点 MAXVER值应为6,依次
类推。的值构造任意个接点,
   在这里加一点我个人的看法:
   教材中给点的编号从0开始,我认为应该从1开始编号。
   如果那样的话教材的算法是有问题的。因为编号从0开始在判断某一顶点是否有邻接顶点
将会有错误(在我程序中是第ERR行
   w的表达式)如果用w>=0判断有邻接顶点那么在什么情况下不存在邻接顶点呢?,因为w>=0
这个表达式是永远成立的。
   
   顶点从0开始编号的算法我也写了出来,请参考:
   如果你认为我的理解有误还请不惜指教。 我的QQ:49186456 OR 358271030*/                            

相关文章

精彩推荐