以邻接多重表为存储结构实现连通无向图的深度优先和广度优先遍历.docx
《以邻接多重表为存储结构实现连通无向图的深度优先和广度优先遍历.docx》由会员分享，可在线阅读，更多相关《以邻接多重表为存储结构实现连通无向图的深度优先和广度优先遍历.docx（25页珍藏版）》请在冰点文库上搜索。
以邻接多重表为存储结构实现连通无向图的深度优先和广度优先遍历
／＊【基本要求】
以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集＊／
／／＿＿＿＿＿＿＿＿头文件＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
＃ｉｎｃｌｕｄｅ＜ｉｏｓｔｒｅａｍ＞
ｕｓｉｎｇ ｎａｍｅｓｐａｃｅ ｓｔｄ；
／／＿＿＿＿＿＿＿无向图的邻接多重表存储表示ｐ１６６＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
ｃｏｎｓｔ ｉｎｔ ＮＵＭ＝２０；
ｃｏｎｓｔ ｉｎｔ Ｄａｔａ＿Ｎｕｍ＝２；／／每个顶点所表示的数据
ｔｙｐｅｄｅｆ ｃｈａｒ ＶｅｒｔｅｘＴｙｐｅ［Ｄａｔａ＿Ｎｕｍ］；
／＊
＃ｄｅｆｉｎｅ ＭＡＸ＿ＶＥＲＴＥＸ＿ＮＵＭ ２０
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ｅｍｎｕ｛ｉｎｔ ｕｎｖｉｓｉｔｅｄ；ｉｎｔ ｖｉｓｉｔｅｄ；｝ ＶｉｓｉｔＩｆ；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＩｎｆｏＴｙｐｅ｛｝；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＶｅｒｔｅｘＴｙｐｅ｛｝；
＊／
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＥＢｏｘ｛
ｉｎｔ ｍａｒｋ； ／／访问标记
ｉｎｔ ｉｖｅｘ，ｊｖｅｘ； ／／该边依附的２个顶点位置
ｓｔｒｕｃｔ ＥＢｏｘ ＊ｉｌｉｎｋ，＊ｊｌｉｎｋ； ／／分别指向依附这２个顶点的下一条边
／／ＩｎｆｏＴｙｐｅ ＊ｉｎｆｏ； ／／该边信息指针
｝ＥＢｏｘ；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＶｅｘＢｏｘ
｛
ＶｅｒｔｅｘＴｙｐｅ ｄａｔａ；
ＥＢｏｘ ＊ｆｉｒｓｔｅｄｇｅ； ／／指向第一条依附该顶点的边
｝ＶｅｘＢｏｘ；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ｛
ＶｅｘＢｏｘ ａｄｊｍｕｌｉｓｔ［ＮＵＭ］；
ｉｎｔ ｖｅｘｎｕｍ，ｅｄｇｅｎｕｍ； ／／无向图的当前顶点和边数
｝ＡＭＬＧｒａｐｈ；
／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿队列的定义＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
ｔｙｐｅｄｅｆ ｉｎｔ ＱＥｌｅｍＴｙｐｅ；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＱＮｏｄｅ
｛
ＱＥｌｅｍＴｙｐｅ ｄａｔａ；
ｓｔｒｕｃｔ ＱＮｏｄｅ ＊ｎｅｘｔ；
｝ＱＮｏｄｅ，＊ＱｕｅｕｅＰｔｒ；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ
｛
ＱｕｅｕｅＰｔｒ ｆｒｏｎｔ，ｒｅａｒ；
｝ＬｉｎｋＱｕｅｕｅ；
／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿寻找指定数据＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
／／寻找输入的数据在图中的位置，若不存在则返回－１
ｉｎｔ ＬｏｃａｔｅＶｅｘ（ＡＭＬＧｒａｐｈ Ｇ，ＶｅｒｔｅｘＴｙｐｅ ｕ）
｛
ｉｎｔ ｉ；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）
ｉｆ（ｓｔｒｃｍｐ（ｕ，Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ）＝＝０）
ｒｅｔｕｒｎ ｉ；
ｒｅｔｕｒｎ －１；
｝
／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿构造无向图＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
／／采用邻接多重表存储表示，构造无向图Ｇ
ｉｎｔ ＣｒｅａｔｅＧｒａｐｈ（ＡＭＬＧｒａｐｈ ＆Ｇ）
｛
ｃｏｕｔ＜＜＂请输入图的顶点数：
＂；
ｃｉｎ＞＞Ｇ．ｖｅｘｎｕｍ；／／输入图当前的顶点数
ｃｏｕｔ＜＜＂请输入图的弧数：
＂；
ｃｉｎ＞＞Ｇ．ｅｄｇｅｎｕｍ；／／输入图当前的边数
ｃｏｕｔ＜＜＂请输入每个顶点所对应的值：
＂＜＜ｅｎｄｌ；
ｆｏｒ（ｉｎｔ ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）
｛
ｃｉｎ＞＞Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ；／／输入顶点值
Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ＝ＮＵＬＬ；／／初始化指针
｝
ＶｅｒｔｅｘＴｙｐｅ ｖ１，ｖ２；
ＥＢｏｘ ＊ｐ；
ｉｎｔ ｊ；／／每条弧所关联的两个结点
ｆｏｒ（ｉｎｔ ｋ＝０；ｋ＜Ｇ．ｅｄｇｅｎｕｍ；ｋ＋＋）
｛
ｃｏｕｔ＜＜＂请输入第＂＜＜ｋ＋１＜＜＂弧的始点和终点：
＂；
ｃｉｎ＞＞ｖ１；ｃｉｎ＞＞ｖ２；
ｉ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ１）；ｊ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ２）；／／确定ｖ１和ｖ２在图Ｇ中的位置
ｐ＝（ＥＢｏｘ ＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＥＢｏｘ））；
／／对弧结点进行赋值
（＊ｐ）．ｍａｒｋ＝０；
（＊ｐ）．ｉｖｅｘ＝ｉ；
（＊ｐ）．ｊｖｅｘ＝ｊ；
（＊ｐ）．ｉｌｉｎｋ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；
（＊ｐ）．ｊｌｉｎｋ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｊ］．ｆｉｒｓｔｅｄｇｅ；
Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｊ］．ｆｉｒｓｔｅｄｇｅ＝ｐ；
｝
ｒｅｔｕｒｎ １；
｝
／／返回Ｖ的值
ＶｅｒｔｅｘＴｙｐｅ＊ ＧｅｔＶｅｘ（ＡＭＬＧｒａｐｈ Ｇ，ｉｎｔ ｖ）
｛
ｉｆ（ｖ＞Ｇ．ｖｅｘｎｕｍ｜｜ｖ＜０）
ｅｘｉｔ（０）；
ｒｅｔｕｒｎ ＆Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ；
｝
／／返回Ｖ的第一个邻接点的序号，若没有则返回－１
ｉｎｔ ＦｉｒｓｔＡｄｊＶｅｘ（ＡＭＬＧｒａｐｈ Ｇ，ＶｅｒｔｅｘＴｙｐｅ ｖ）
｛
ｉｎｔ ｉ；
ｉ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ）；
ｉｆ（ｉ＜０）
ｒｅｔｕｒｎ －１；
ｉｆ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ）／／Ｖ有邻接结点
ｉｆ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ－＞ｉｖｅｘ＝＝ｉ）
ｒｅｔｕｒｎ Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ－＞ｊｖｅｘ；
ｅｌｓｅ
ｒｅｔｕｒｎ Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ－＞ｉｖｅｘ；
ｅｌｓｅ
ｒｅｔｕｒｎ －１；
｝
／／返回Ｖ的（相对于Ｗ）的下一个邻接结点的序号，若Ｗ是Ｖ的最后一个邻接结点，则返回－１
ｉｎｔ ＮｅｘｔＡｄｊＶｅｘ（ＡＭＬＧｒａｐｈ Ｇ，ＶｅｒｔｅｘＴｙｐｅ ｖ，ＶｅｒｔｅｘＴｙｐｅ ｗ）
｛
ｉｎｔ ｉ，ｊ；
ＥＢｏｘ ＊ｐ；
ｉ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ）；
ｊ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｗ）；
ｉｆ（ｉ＜０｜｜ｊ＜０）
ｒｅｔｕｒｎ －１；
ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；
ｗｈｉｌｅ（ｐ）
ｉｆ（ｐ－＞ｉｖｅｘ＝＝ｉ＆＆ｐ－＞ｊｖｅｘ！
＝ｊ）
ｐ＝ｐ－＞ｉｌｉｎｋ；
ｅｌｓｅ ｉｆ（ｐ－＞ｊｖｅｘ＝＝ｉ＆＆ｐ－＞ｉｖｅｘ！
＝ｊ）
ｐ＝ｐ－＞ｊｌｉｎｋ；
ｅｌｓｅ
ｂｒｅａｋ；
ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｉ＆＆ｐ－＞ｊｖｅｘ＝＝ｊ）
｛
ｐ＝ｐ－＞ｉｌｉｎｋ；
ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｉ）
ｒｅｔｕｒｎ ｐ－＞ｊｖｅｘ；
ｅｌｓｅ ｉｆ（ｐ＆＆ｐ－＞ｊｖｅｘ＝＝ｉ）
ｒｅｔｕｒｎ ｐ－＞ｊｖｅｘ；
｝
ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｊ＆＆ｐ－＞ｊｖｅｘ＝＝ｉ）
｛
ｐ＝ｐ－＞ｊｌｉｎｋ；
ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｉ）
ｒｅｔｕｒｎ ｐ－＞ｊｖｅｘ；
ｅｌｓｅ ｉｆ（ｐ＆＆ｐ－＞ｊｖｅｘ＝＝ｉ）
ｒｅｔｕｒｎ ｐ－＞ｊｖｅｘ；
｝
ｒｅｔｕｒｎ －１；
｝
／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿队列的操作＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
ｉｎｔ ｖｉｓｉｔｅ［ＮＵＭ］；／／访问标志数组
ｉｎｔ （＊ＶｉｓｉｔＦｕｎｃ）（ＶｅｒｔｅｘＴｙｐｅ ｖ）；
ｖｏｉｄ ＤＦＳ（ＡＭＬＧｒａｐｈ Ｇ，ｉｎｔ ｖ）
｛
ｉｎｔ ｊ；
ＥＢｏｘ ＊ｐ；
ＶｉｓｉｔＦｕｎｃ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ）；
ｖｉｓｉｔｅ［ｖ］＝１；／／该顶点已经被访问
ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｆｉｒｓｔｅｄｇｅ；
ｗｈｉｌｅ（ｐ）
｛
ｊ＝ｐ－＞ｉｖｅｘ＝＝ｖ？
ｐ－＞ｊｖｅｘ：
ｐ－＞ｉｖｅｘ；
ｉｆ（！
ｖｉｓｉｔｅ［ｊ］）
ＤＦＳ（Ｇ，ｊ）；
ｐ＝ｐ－＞ｉｖｅｘ＝＝ｖ？
ｐ－＞ｉｌｉｎｋ：
ｐ－＞ｊｌｉｎｋ；
｝
｝
／／＿＿＿＿＿＿＿＿深度优先搜索＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
ｖｏｉｄ ＤＦＳＴｒａｖｅｒｓｅ（ＡＭＬＧｒａｐｈ Ｇ，ｉｎｔ（＊Ｖｉｓｉｔ）（ＶｅｒｔｅｘＴｙｐｅ））
｛
ｉｎｔ ｖ，ｓｔａｒｔ；
ＶｉｓｉｔＦｕｎｃ＝Ｖｉｓｉｔ；
ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；ｖ＋＋）
ｖｉｓｉｔｅ［ｖ］＝０；
ｃｏｕｔ＜＜＂请输入你要开始进行查找的位置：
＂；
ｃｉｎ＞＞ｓｔａｒｔ；
ｃｏｕｔ＜＜＂按广深度优先搜索的结果是：
＂＜＜ｅｎｄｌ；
ｆｏｒ（ｖ＝ｓｔａｒｔ；ｖ＜Ｇ．ｖｅｘｎｕｍ；ｖ＋＋）
｛
ｉｆ（ｖ＞＝Ｇ．ｖｅｘｎｕｍ）
｛
ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；ｖ＋＋）
｛
ｉｆ（！
ｖｉｓｉｔｅ［ｖ］）
ＤＦＳ（Ｇ，ｖ）；
｝／／内层ｆｏｒ
｝／／ｉｆ
ｅｌｓｅ
｛
ｉｆ（！
ｖｉｓｉｔｅ［ｖ］）
ＤＦＳ（Ｇ，ｖ）；
｝／／ｅｌｓｅ
｝／／外层ｆｏｒ
ｃｏｕｔ＜＜＂＼ｂ＼ｂ＼ｂ ＂；
ｃｏｕｔ＜＜ｅｎｄｌ；
｝
／／队列的初始化
ｉｎｔ ＩｎｉｔＱｕｅｕｅ（ＬｉｎｋＱｕｅｕｅ ＊Ｑ）
｛
（＊Ｑ）．ｆｒｏｎｔ＝（＊Ｑ）．ｒｅａｒ＝（ＱｕｅｕｅＰｔｒ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＱＮｏｄｅ））；
ｉｆ（！
（＊Ｑ）．ｆｒｏｎｔ）
ｅｘｉｔ（０）；
（＊Ｑ）．ｆｒｏｎｔ－＞ｎｅｘｔ＝ＮＵＬＬ；
ｒｅｔｕｒｎ １；
｝
／／判断队列是否为空，为空则返回１，否则返回０
ｉｎｔ ＱｕｅｕｅＥｍｐｔｙ（ＬｉｎｋＱｕｅｕｅ Ｑ）
｛
ｉｆ（Ｑ．ｆｒｏｎｔ＝＝Ｑ．ｒｅａｒ）
ｒｅｔｕｒｎ １；
ｅｌｓｅ
ｒｅｔｕｒｎ ０；
｝
／／向队列中插入元素
ｉｎｔ ＥｎＱｕｅｕｅ（ＬｉｎｋＱｕｅｕｅ ＊Ｑ，ＱＥｌｅｍＴｙｐｅ ｅ）
｛
ＱｕｅｕｅＰｔｒ ｐ＝（ＱｕｅｕｅＰｔｒ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＱＮｏｄｅ））；
ｉｆ（！
ｐ）
ｅｘｉｔ（０）；
ｐ－＞ｄａｔａ＝ｅ；
ｐ－＞ｎｅｘｔ＝ＮＵＬＬ；
（＊Ｑ）．ｒｅａｒ－＞ｎｅｘｔ＝ｐ；
（＊Ｑ）．ｒｅａｒ＝ｐ；
ｒｅｔｕｒｎ １；
｝
／／若队列不为空，则删除对头元素，并返回１；否则返回 ０
ｉｎｔ ＤｅＱｕｅｕｅ（ＬｉｎｋＱｕｅｕｅ ＊Ｑ，ＱＥｌｅｍＴｙｐｅ ＊ｅ）
｛
ＱｕｅｕｅＰｔｒ ｐ；
ｉｆ（（＊Ｑ）．ｆｒｏｎｔ＝＝（＊Ｑ）．ｒｅａｒ）
ｒｅｔｕｒｎ ０；
ｐ＝（＊Ｑ）．ｆｒｏｎｔ－＞ｎｅｘｔ；
＊ｅ＝ｐ－＞ｄａｔａ；
（＊Ｑ）．ｆｒｏｎｔ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；
ｉｆ（（＊Ｑ）．ｒｅａｒ＝＝ｐ）
（＊Ｑ）．ｒｅａｒ＝（＊Ｑ）．ｆｒｏｎｔ；
ｆｒｅｅ（ｐ）；
ｒｅｔｕｒｎ １；
｝
／＊＊
Ｂｏｏｌｅａｎ ｖｉｓｉｔｅｄ［ＭＡＸ］； ／／访问标志数组
Ｓｔａｔｕｓ（＊ＶｉｓｉｔＦｕｎｃ）（ｉｎｔ ｖ）； ／／函数变量
ｖｏｉｄ ＤＦＳＴｒａｖｅｒｓｅ（Ｇｒａｐｈ Ｇ，Ｓｔａｔｕｓ（＊Ｖｉｓｉｔ）（ｉｎｔ ｖ））
｛ ／／对图Ｇ做深度优先遍历
ＶｉｓｉｔＦｕｎｃ＝Ｖｉｓｉｔ ／／使用全局变量ＶｉｓｉｔＦｕｎｃ，使ＤＦＳ不必设函数指针参数
ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｖ）ｖｉｓｉｔｅｄ［ｖ］＝ＦＡＬＳＥ； ／／访问标志数组初始化
ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｖ）
ｉｆ（！
ｖｉｓｉｔｅｄ［ｖ］） ＤＦＳ（Ｇ，ｖ）； ／／对尚未访问的顶点调用ＤＦＳ
｝
ｖｏｉｄ ＤＦＳ（Ｇｒａｐｈ Ｇ，ｉｎｔ ｖ）
｛ ／／从第Ｖ个顶点出发递归地深度优先遍历图Ｇ
ｖｉｓｉｔｅｄ［ｖ］＝ＴＲＵＥ；ＶｉｓｉｔＦｕｎｃ（ｖ）；／／访问第ｖ个顶点
ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｖ）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｖ，ｗ）
ｉｆ（！
ｖｉｓｉｔｅｄ［ｗ］） ＤＦＳ（Ｇ，ｗ）；
｝
＊＊／
／／＿＿＿＿＿＿＿＿＿广度优先搜索＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
／／广度优先非递归遍历图Ｇ
ｖｏｉｄ ＢＦＳＴｒａｖｅｒｓｅ（ＡＭＬＧｒａｐｈ Ｇ，ｉｎｔ（＊Ｖｉｓｉｔ）（ＶｅｒｔｅｘＴｙｐｅ））
｛
ｉｎｔ ｕ，ｖ，ｗ，ｓｔａｒｔ＝０；
ＶｅｒｔｅｘＴｙｐｅ ｗ１，ｕ１；
ＬｉｎｋＱｕｅｕｅ Ｑ；
ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；ｖ＋＋）
ｖｉｓｉｔｅ［ｖ］＝０；
ＩｎｉｔＱｕｅｕｅ（＆Ｑ）；
ｃｏｕｔ＜＜＂请输入你要开始进行查找的位置：
＂；
ｃｉｎ＞＞ｓｔａｒｔ；
ｃｏｕｔ＜＜＂按广度优先搜索的结果是：
＂＜＜ｅｎｄｌ；
ｆｏｒ（ｖ＝ｓｔａｒｔ；ｖ＜Ｇ．ｖｅｘｎｕｍ；ｖ＋＋）
｛
ｉｆ（！
ｖｉｓｉｔｅ［ｖ］）
｛
ｖｉｓｉｔｅ［ｖ］＝１；
Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ）；
ＥｎＱｕｅｕｅ（＆Ｑ，ｖ）；／／ｖ入队列
ｗｈｉｌｅ（！
ＱｕｅｕｅＥｍｐｔｙ（Ｑ））
｛
ＤｅＱｕｅｕｅ（＆Ｑ，＆ｕ）；
ｓｔｒｃｐｙ（ｕ１，＊ＧｅｔＶｅｘ（Ｇ，ｕ））；
ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｕ１）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｕ１，ｓｔｒｃｐｙ（ｗ１，＊ＧｅｔＶｅｘ（Ｇ，ｗ））））
ｉｆ（！
ｖｉｓｉｔｅ［ｗ］）
｛
ｖｉｓｉｔｅ［ｗ］＝１；
Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｗ］．ｄａｔａ）；
ＥｎＱｕｅｕｅ（＆Ｑ，ｗ）；
｝
｝
｝
｝／／ｆｏｒ
ＩｎｉｔＱｕｅｕｅ（＆Ｑ）；
ｆｏｒ（ｖ＝０；ｖ＜ｓｔａｒｔ；ｖ＋＋）
｛
ｉｆ（！
ｖｉｓｉｔｅ［ｖ］）
｛
ｖｉｓｉｔｅ［ｖ］＝１；
Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ）；
ＥｎＱｕｅｕｅ（＆Ｑ，ｖ）；／／ｖ入队列
ｗｈｉｌｅ（！
ＱｕｅｕｅＥｍｐｔｙ（Ｑ））
｛
ＤｅＱｕｅｕｅ（＆Ｑ，＆ｕ）；
ｓｔｒｃｐｙ（ｕ１，＊ＧｅｔＶｅｘ（Ｇ，ｕ））；
ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｕ１）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｕ１，ｓｔｒｃｐｙ（ｗ１，＊ＧｅｔＶｅｘ（Ｇ，ｗ））））
ｉｆ（！
ｖｉｓｉｔｅ［ｗ］）
｛
ｖｉｓｉｔｅ［ｗ］＝１；
Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｗ］．ｄａｔａ）；
ＥｎＱｕｅｕｅ（＆Ｑ，ｗ）；
｝
｝
｝
｝／／ｆｏｒ
ｃｏｕｔ＜＜＂＼ｂ＼ｂ＼ｂ ＂；
ｃｏｕｔ＜＜ｅｎｄｌ；
｝
／／把边的访问标记设置为０，即未被访问
ｖｏｉｄ ＭａｒｋＵｎＶｉｓｉｔｅｄ（ＡＭＬＧｒａｐｈ Ｇ）
｛
ｉｎｔ ｉ；
ＥＢｏｘ ＊ｐ；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）
｛
ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；
ｗｈｉｌｅ（ｐ）
｛
ｐ－＞ｍａｒｋ＝０；
ｉｆ（ｐ－＞ｉｖｅｘ＝＝ｉ）
ｐ＝ｐ－＞ｉｌｉｎｋ；
ｅｌｓｅ
ｐ＝ｐ－＞ｊｌｉｎｋ；
｝
｝
｝
／＊＊
ｖｏｉｄ ＢＦＳＴｒａｖｅｒｓｅ（Ｇｒａｐｈ Ｇ，Ｓｔａｔｕｓ（＊ ｖｉｓｉｔ）（ｉｎｔ ｖ））｛
／／按广度优先非递归遍历图Ｇ。
使用辅助队列Ｑ和访问标志数组ｖｉｓｉｔｅｄ
ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｖ） ｖｉｓｉｔｅｄ［ｖ］＝ＦＡＬＳＥ；
ＩｎｉｔＱｕｅｕｅ（Ｑ） ／／置空的辅助队列Ｑ
ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋Ｖ）
ｉｆ（！
ｖｉｓｉｔｅｄ［ｖ］）｛ ／／ｖ尚未访问
ｖｉｓｉｔｅｄ［ｖ］＝ＴＲＵＥ；Ｖｉｓｉｔ（ｖ）；
ＥｎＱｕｅｕｅ（Ｑ，ｖ）； ／／ｖ入队列
ｗｈｉｌｅ（！
ＱｕｅｕｅＥｍｐｔｙ（Ｑ））｛
ＤｅＱｕｅｕｅ（Ｑ，ｖ）； ／／对头元素出队并置为ｕ
ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｕ）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｕ，ｗ））
ｉｆ（！
Ｖｉｓｉｔｅｄ［ｗ］）｛ ／／ｗ为ｕ的尚未访问的邻接顶点
Ｖｉｓｉｔｅｄ［ｗ］＝ＴＲＵＥ； Ｖｉｓｉｔ（ｗ）；
ＥｎＱｕｅｕｅ（Ｑ，Ｗ）；
｝／／ｉｆ
｝／／ｗｈｉｌｅ
｝／／ｉｆ
｝／／ＢＦＳＴｒａｖｅｒｓｅ
＊＊／
／／显示构造的无向图（包括定点数、顶点、边数、边）
ｖｏｉｄ Ｄｉｓｐｌａｙ（ＡＭＬＧｒａｐｈ Ｇ）
｛
ｉｎｔ ｉ；
ＥＢｏｘ ＊ｐ；
ＭａｒｋＵｎＶｉｓｉｔｅｄ（Ｇ）；
ｃｏｕｔ＜＜Ｇ．ｖｅｘｎｕｍ＜＜＂个顶点：
＂；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）
ｃｏｕｔ＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ＜＜＂ ＂；
ｃｏｕｔ＜＜＂； ＂＜＜Ｇ．ｅｄｇｅｎｕｍ＜＜＂条边：
＂＜＜ｅｎｄｌ；
ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）
｛
ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；
ｗｈｉｌｅ（ｐ）
ｉｆ（ｐ－＞ｉｖｅｘ＝＝ｉ）
｛
ｉｆ（！
ｐ－＞ｍａｒｋ）
｛
ｃｏｕｔ＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ＜＜＂－－＞＂＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｐ－＞ｊｖｅｘ］．ｄａｔａ＜＜＂ ＂；
ｐ－＞ｍａｒｋ＝１；／／已经被访问过了
｝
ｐ＝ｐ－＞ｉｌｉｎｋ；
｝
ｅｌｓｅ
｛
ｉｆ（！
ｐ－＞ｍａｒｋ）
｛
ｃｏｕｔ＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｐ－＞ｉｖｅｘ］．ｄａｔａ＜＜＂－－＞＂＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ＜＜＂ ＂；
ｐ－＞ｍａｒｋ＝１；／／已经被访问过了
｝
ｐ＝ｐ－＞ｊｌｉｎｋ；
｝
ｃｏｕｔ＜＜ｅｎｄｌ；
｝
｝
ｉｎｔ Ｖｉｓｉｔ（ＶｅｒｔｅｘＴｙｐｅ ｖ）
｛
ｃｏｕｔ＜＜ｖ＜＜＂－－＞＂；
ｒｅｔｕｒｎ １；
｝
／／＿＿＿＿＿＿＿＿＿＿深度优先遍历下的节点访问序列＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
／／＿＿＿＿＿＿＿＿＿＿广度优先遍历下的节点访问序列＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
／／＿＿＿＿＿＿＿＿＿＿深度优先遍历生成树＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
／／＿＿＿＿＿＿＿＿＿＿广度优先遍历生成树＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿主函数＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
ｉｎｔ ｍａｉｎ（）
｛ｉｎｔ ｃｈ，ＹＥＳ＝０；
ＡＭＬＧｒａｐｈ ｇ；
／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿主界面＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
ｃｏｕｔ＜＜＂－－－－－－－－实验四 图遍历的演示－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂基本要求：
＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。
－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。
＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（１） 创建无向图－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（２） 打印无向图－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（３） 深度优先遍历并输出深度优先遍历下的节点访问序列－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（４） 广度优先遍历并输出广度优先遍历下的节点访问序列－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
／／ｃｏｕｔ＜＜＂（３） 输出深度优先遍历下的节点访问序列－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
／／ｃｏｕｔ＜＜＂（４） 输出广度优先遍历下的节点访问序列－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（５） 输出深度优先遍历生成树的边集－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（６） 输出广度优先遍历生成树的边集－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（７） －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（８） －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（９） 检查ｓｗｉｔｃｈ语句－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＂＜＜ｅｎｄｌ；
ｃｏｕｔ＜＜＂（０） 退出－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
升级会员 