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

本文格式为Word版，下载可任意编辑——以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍／＊

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

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集＊／／／＿＿＿＿＿＿＿＿头文件＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＃ｉｎｃｌｕｄｅ＜ｉｏｓｔｒｅａｍ＞ｕｓｉｎｇｎａｍｅｓｐａｃｅｓｔｄ；

／／＿＿＿＿＿＿＿无向图的邻接多重表存储表示ｐ１６６＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ｃｏｎｓｔｉｎｔＮＵＭ＝２０；

ｃｏｎｓｔｉｎｔＤａｔａ＿Ｎｕｍ＝２；／／每个顶点所表示的数据ｔｙｐｅｄｅｆｃｈａｒＶｅｒｔｅｘＴｙｐｅ［Ｄａｔａ＿Ｎｕｍ］；

／＊

＃ｄｅｆｉｎｅＭＡＸ＿ＶＥＲＴＥＸ＿ＮＵＭ２０ｔｙｐｅｄｅｆｓｔｒｕｃｔｅｍｎｕ｛ｉｎｔｕｎｖｉｓｉｔｅｄ；ｉｎｔｖｉｓｉｔｅｄ；｝ＶｉｓｉｔＩｆ；

ｔｙｐｅｄｅｆｓｔｒｕｃｔＩｎｆｏＴｙｐｅ｛｝；ｔｙｐｅｄｅｆｓｔｒｕｃｔＶｅｒｔｅｘＴｙｐｅ｛｝；＊／

ｔｙｐｅｄｅｆｓｔｒｕｃｔＥＢｏｘ｛ｉｎｔｍａｒｋ；／／访问标记

ｉｎｔｉｖｅｘ，ｊｖｅｘ；／／该边依附的２个顶点位置ｓｔｒｕｃｔＥＢｏｘ＊ｉｌｉｎｋ，＊ｊｌｉｎｋ；／／分别指向依附这２个顶点的下一条边

／／ＩｎｆｏＴｙｐｅ＊ｉｎｆｏ；／／该边信息指针｝ＥＢｏｘ；

ｔｙｐｅｄｅｆｓｔｒｕｃｔＶｅｘＢｏｘ｛ＶｅｒｔｅｘＴｙｐｅｄａｔａ；ＥＢｏｘ＊ｆｉｒｓｔｅｄｇｅ；／／指向第一条依附该顶点的边｝ＶｅｘＢｏｘ；

ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＶｅｘＢｏｘａｄｊｍｕｌｉｓｔ［ＮＵＭ］；

ｉｎｔｖｅｘｎｕｍ，ｅｄｇｅｎｕｍ；／／无向图的当前顶点和边数｝ＡＭＬＧｒａｐｈ；

／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿队列的定义＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ｔｙｐｅｄｅｆｉｎｔＱＥｌｅｍＴｙｐｅ；ｔｙｐｅｄｅｆｓｔｒｕｃｔＱＮｏｄｅ｛ＱＥｌｅｍＴｙｐｅｄａｔａ；ｓｔｒｕｃｔＱＮｏｄｅ＊ｎｅｘｔ；

｝ＱＮｏｄｅ，＊ＱｕｅｕｅＰｔｒ；

ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＱｕｅｕｅＰｔｒｆｒｏｎｔ，ｒｅａｒ；

｝ＬｉｎｋＱｕｅｕｅ；

／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿寻觅指定数据＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／／寻觅输入的数据在图中的位置，若不存在则返回－１

ｉｎｔＬｏｃａｔｅＶｅｘ（ＡＭＬＧｒａｐｈＧ，ＶｅｒｔｅｘＴｙｐｅｕ）｛ｉｎｔｉ；ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）ｉｆ（ｓｔｒｃｍｐ（ｕ，Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ）＝＝０）ｒｅｔｕｒｎｉ；ｒｅｔｕｒｎ－１；｝

／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿构造无向图＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／／采用邻接多重表存储表示，构造无向图Ｇ

ｉｎｔＣｒｅａｔｅＧｒａｐｈ（ＡＭＬＧｒａｐｈ＆Ｇ）｛ｃｏｕｔ＜＜＂请输入图的顶点数：＂；ｃｉｎ＞＞Ｇ．ｖｅｘｎｕｍ；／／输入图当前的顶点数ｃｏｕｔ＜＜＂请输入图的弧数：＂；ｃｉｎ＞＞Ｇ．ｅｄｇｅｎｕｍ；／／输入图当前的边数ｃｏｕｔ＜＜＂请输入每个顶点所对应的值：＂＜＜ｅｎｄｌ；ｆｏｒ（ｉｎｔｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋）｛ｃｉｎ＞＞Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ；／／输入顶点值Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ＝ＮＵＬＬ；／／初始化指针｝ＶｅｒｔｅｘＴｙｐｅｖ１，ｖ２；ＥＢｏｘ＊ｐ；ｉｎｔｊ；／／每条弧所关联的两个结点ｆｏｒ（ｉｎｔｋ＝０；ｋ＜Ｇ．ｅｄｇｅｎｕｍ；ｋ＋＋）｛ｃｏｕｔ＜＜＂请输入第＂＜＜ｋ＋１＜＜＂弧的始点和终点：＂；ｃｉｎ＞＞ｖ１；ｃｉｎ＞＞ｖ２；ｉ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ１）；ｊ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ２）；／

／确定ｖ１和ｖ２在图Ｇ中的位置ｐ＝（ＥＢｏｘ＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＥＢｏｘ））；／／对弧结点进行赋值（＊ｐ）．ｍａｒｋ＝０；（＊ｐ）．ｉｖｅｘ＝ｉ；（＊ｐ）．ｊｖｅｘ＝ｊ；（＊ｐ）．ｉｌｉｎｋ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；（＊ｐ）．ｊｌｉｎｋ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｊ］．ｆｉｒｓｔｅｄｇｅ；Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｊ］．ｆｉｒｓｔｅｄｇｅ＝ｐ；｝ｒｅｔｕｒｎ１；｝

／／返回Ｖ的值

ＶｅｒｔｅｘＴｙｐｅ＊ＧｅｔＶｅｘ（ＡＭＬＧｒａｐｈＧ，ｉｎｔｖ）｛ｉｆ（ｖ＞Ｇ．ｖｅｘｎｕｍ｜｜ｖ＜０）ｅｘｉｔ（０）；ｒｅｔｕｒｎ＆Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ；｝

／／返回Ｖ的第一个邻接点的序号，若没有则返回－１

ｉｎｔＦｉｒｓｔＡｄｊＶｅｘ（ＡＭＬＧｒａｐｈＧ，ＶｅｒｔｅｘＴｙｐｅｖ）｛ｉｎｔｉ；ｉ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ）；ｉｆ（ｉ＜０）ｒｅｔｕｒｎ－１；ｉｆ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ）／／Ｖ有邻接结点ｉｆ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ－＞ｉｖｅｘ＝＝ｉ）ｒｅｔｕｒｎＧ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ－＞ｊｖｅｘ；ｅｌｓｅｒｅｔｕｒｎＧ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ－＞ｉｖｅｘ；ｅｌｓｅｒｅｔｕｒｎ－１；｝

／／返回Ｖ的（相对于Ｗ）的下一个邻接结点的序号，若Ｗ是Ｖ的最终一个邻接结点，则返回－１

ｉｎｔＮｅｘｔＡｄｊＶｅｘ（ＡＭＬＧｒａｐｈＧ，ＶｅｒｔｅｘＴｙｐｅｖ，ＶｅｒｔｅｘＴｙｐｅｗ）

｛

ｉｎｔｉ，ｊ；ＥＢｏｘ＊ｐ；

ｉ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｖ）；ｊ＝ＬｏｃａｔｅＶｅｘ（Ｇ，ｗ）；ｉｆ（ｉ＜０｜｜ｊ＜０）ｒｅｔｕｒｎ－１；

ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；ｗｈｉｌｅ（ｐ）ｉｆ（ｐ－＞ｉｖｅｘ＝＝ｉ＆＆ｐ－＞ｊｖｅｘ！＝ｊ）ｐ＝ｐ－＞ｉｌｉｎｋ；ｅｌｓｅｉｆ（ｐ－＞ｊｖｅｘ＝＝ｉ＆＆ｐ－＞ｉｖｅｘ！＝ｊ）ｐ＝ｐ－＞ｊｌｉｎｋ；ｅｌｓｅｂｒｅａｋ；ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｉ＆＆ｐ－＞ｊｖｅｘ＝＝ｊ）｛ｐ＝ｐ－＞ｉｌｉｎｋ；ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｉ）ｒｅｔｕｒｎｐ－＞ｊｖｅｘ；ｅｌｓｅｉｆ（ｐ＆＆ｐ－＞ｊｖｅｘ＝＝ｉ）ｒｅｔｕｒｎｐ－＞ｊｖｅｘ；｝ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｊ＆＆ｐ－＞ｊｖｅｘ＝＝ｉ）｛ｐ＝ｐ－＞ｊｌｉｎｋ；ｉｆ（ｐ＆＆ｐ－＞ｉｖｅｘ＝＝ｉ）ｒｅｔｕｒｎｐ－＞ｊｖｅｘ；ｅｌｓｅｉｆ（ｐ＆＆ｐ－＞ｊｖｅｘ＝＝ｉ）ｒｅｔｕｒｎｐ－＞ｊｖｅｘ；｝ｒｅｔｕｒｎ－１；

｝

／／＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿队列的操作＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

ｉｎｔｖｉｓｉｔｅ［ＮＵＭ］；／／访问标志数组ｉｎｔ（＊ＶｉｓｉｔＦｕｎｃ）（ＶｅｒｔｅｘＴｙｐｅｖ）；

ｖｏｉｄＤＦＳ（ＡＭＬＧｒａｐｈＧ，ｉｎｔｖ）｛

｝

ｉｎｔｊ；ＥＢｏｘ＊ｐ；

ＶｉｓｉｔＦｕｎｃ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ）；ｖｉｓｉｔｅ［ｖ］＝１；／／该顶点已经被访问ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｆｉｒｓｔｅｄｇｅ；ｗｈｉｌｅ（ｐ）｛ｊ＝ｐ－＞ｉｖｅｘ＝＝ｖ？ｐ－＞ｊｖｅｘ：ｐ－＞ｉｖｅｘ；ｉｆ（！ｖｉｓｉｔｅ［ｊ］）ＤＦＳ（Ｇ，ｊ）；ｐ＝ｐ－＞ｉｖｅｘ＝＝ｖ？ｐ－＞ｉｌｉｎｋ：ｐ－＞ｊｌｉｎｋ；｝

／／＿＿＿＿＿＿＿＿深度优先探寻＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ｖｏｉｄＤＦＳＴｒａｖｅｒｓｅ（ＡＭＬＧｒａｐｈＧ，ｉｎｔ（＊Ｖｉｓｉｔ）（ＶｅｒｔｅｘＴｙｐｅ））｛ｉｎｔｖ，ｓｔａｒｔ；ＶｉｓｉｔＦｕｎｃ＝Ｖｉｓｉｔ；ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；ｖ＋＋）ｖｉｓｉｔｅ［ｖ］＝０；ｃｏｕｔ＜＜＂请输入你要开始进行查找的位置：＂；ｃｉｎ＞＞ｓｔａｒｔ；ｃｏｕｔ＜＜＂按广深度优先探寻的结果是：＂＜＜ｅｎｄｌ；ｆｏｒ（ｖ＝ｓｔａｒｔ；ｖ＜Ｇ．ｖｅｘｎｕｍ；ｖ＋＋）｛ｉｆ（ｖ