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

／＊【基本要求】

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

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

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

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

／＊

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

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

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

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

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

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

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

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

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

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

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

｝ＬｉｎｋＱｕｅｕｅ；

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

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

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

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

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

／／返回Ｖ的值

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

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

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

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

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

｛

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

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

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

｝

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

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

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

｝

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

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

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍在线全文阅读。