以邻接多重表为存储结构-实现连通无向图的深度优先和广度优先遍历.docx

《以邻接多重表为存储结构-实现连通无向图的深度优先和广度优先遍历.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、／＊【基本要求】以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集＊／／／＿＿＿＿＿＿＿＿头文件＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＃ｉｎｃｌｕｄｅ＜ｉｏｓｔｒｅａｍ＞ｕｓｉｎｇ　ｎａｍｅｓｐａｃｅ　ｓｔｄ；／／＿＿＿＿＿＿＿无向图的邻接多重表存储表示ｐ１６６＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ｃｏｎｓｔ　ｉｎｔ　ＮＵＭ＝２０；ｃｏｎｓｔ　ｉｎｔ　Ｄａｔａ＿Ｎｕｍ＝２；／／每个顶

2、点所表示的数据ｔｙｐｅｄｅｆ　ｃｈａｒ　ＶｅｒｔｅｘＴｙｐｅ［Ｄａｔａ＿Ｎｕｍ］；／＊＃ｄｅｆｉｎｅ　ＭＡＸ＿ＶＥＲＴＥＸ＿ＮＵＭ　２０ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ｅｍｎｕ｛ｉｎｔ　ｕｎｖｉｓｉｔｅｄ；ｉｎｔ　ｖｉｓｉｔｅｄ；｝　ＶｉｓｉｔＩｆ；ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ＩｎｆｏＴｙｐｅ｛｝；ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ＶｅｒｔｅｘＴｙｐｅ｛｝；＊／ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ＥＢｏｘ｛ｉｎｔ　ｍａｒｋ；　　　　／／访问标记ｉｎｔ　ｉｖｅｘ，ｊｖｅｘ；　　　／／该边依附的２个顶点位置ｓｔｒｕｃｔ　ＥＢｏｘ　＊ｉｌｉｎｋ，＊ｊｌｉｎｋ；　　　／／分别指向依附这２个顶点的下一

3、条边／／ＩｎｆｏＴｙｐｅ　＊ｉｎｆｏ；　　　／／该边信息指针｝ＥＢｏｘ；ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ＶｅｘＢｏｘ｛ＶｅｒｔｅｘＴｙｐｅ　ｄａｔａ；ＥＢｏｘ　＊ｆｉｒｓｔｅｄｇｅ；　　　／／指向第一条依附该顶点的边｝ＶｅｘＢｏｘ；ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ｛ＶｅｘＢｏｘ　ａｄｊｍｕｌｉｓｔ［ＮＵＭ］；ｉｎｔ　ｖｅｘｎｕｍ，ｅｄｇｅｎｕｍ；　　　／／无向图的当前顶点和边数｝ＡＭＬＧｒａｐｈ；／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿队列的定义＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ｔｙｐｅｄｅｆ　ｉｎｔ　ＱＥｌｅｍＴｙｐｅ；ｔｙｐｅｄｅ

4、ｆ　ｓｔｒｕｃｔ　ＱＮｏｄｅ｛ＱＥｌｅｍＴｙｐｅ　ｄａｔａ；ｓｔｒｕｃｔ　ＱＮｏｄｅ　＊ｎｅｘｔ；｝ＱＮｏｄｅ，＊ＱｕｅｕｅＰｔｒ；ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ｛ＱｕｅｕｅＰｔｒ　ｆｒｏｎｔ，ｒｅａｒ；｝ＬｉｎｋＱｕｅｕｅ；／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿寻找指定数据＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／／寻找输入的数据在图中的位置，若不存在则返回－１ｉｎｔ　ＬｏｃａｔｅＶｅｘ（ＡＭＬＧｒａｐｈ　Ｇ，ＶｅｒｔｅｘＴｙｐｅ　ｕ）｛ｉｎｔ　ｉ；ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）ｉｆ（ｓｔｒｃｍｐ（ｕ，Ｇ．

5、ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ）＝＝０）ｒｅｔｕｒｎ　ｉ；ｒｅｔｕｒｎ　－１；｝／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿构造无向图＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／／采用邻接多重表存储表示，构造无向图Ｇｉｎｔ　ＣｒｅａｔｅＧｒａｐｈ（ＡＭＬＧｒａｐｈ　＆Ｇ）｛ｃｏｕｔ＜＜＂请输入图的顶点数：　＂；ｃｉｎ＞＞Ｇ．ｖｅｘｎｕｍ；／／输入图当前的顶点数ｃｏｕｔ＜＜＂请输入图的弧数：　　　＂；ｃｉｎ＞＞Ｇ．ｅｄｇｅｎｕｍ；／／输入图当前的边数ｃｏｕｔ＜＜＂请输入每个顶点所对应的值：＂＜＜ｅｎｄｌ；ｆｏｒ（ｉｎｔ　

6、ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）｛ｃｉｎ＞＞Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ；／／输入顶点值Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ＝ＮＵＬＬ；／／初始化指针｝ＶｅｒｔｅｘＴｙｐｅ　ｖ１，ｖ２；ＥＢｏｘ　＊ｐ；ｉｎｔ　ｊ；／／每条弧所关联的两个结点ｆｏｒ（ｉｎｔ　ｋ＝０；ｋ＜Ｇ．ｅｄｇｅｎｕｍ；ｋ＋＋）｛ｃｏｕｔ＜＜＂请输入第＂＜＜ｋ＋１＜＜＂弧的始点和终点：＂；ｃｉｎ＞＞ｖ１；ｃｉｎ＞＞ｖ２；ｉ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ１）；ｊ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ２）；／／确定ｖ１和ｖ２在图Ｇ中的位置ｐ＝（ＥＢｏｘ　＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＥＢｏｘ））；／／

7、对弧结点进行赋值（＊ｐ）．ｍａｒｋ＝０；（＊ｐ）．ｉｖｅｘ＝ｉ；（＊ｐ）．ｊｖｅｘ＝ｊ；（＊ｐ）．ｉｌｉｎｋ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；（＊ｐ）．ｊｌｉｎｋ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｊ］．ｆｉｒｓｔｅｄｇｅ；Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｊ］．ｆｉｒｓｔｅｄｇｅ＝ｐ；｝ｒｅｔｕｒｎ　１；｝／／返回Ｖ的值ＶｅｒｔｅｘＴｙｐｅ＊　ＧｅｔＶｅｘ（ＡＭＬＧｒａｐｈ　Ｇ，ｉｎｔ　ｖ）｛ｉｆ（ｖ＞Ｇ．ｖｅｘｎｕｍ