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

ｃｏｕｔ＜＜ｅｎｄｌ； ｝

／／队列的初始化

ｉｎｔ ＩｎｉｔＱｕｅｕｅ（ＬｉｎｋＱｕｅｕｅ ＊Ｑ） ｛ （＊Ｑ）．ｆｒｏｎｔ＝（＊Ｑ）．ｒｅａｒ＝（ＱｕｅｕｅＰｔｒ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＱＮｏｄｅ））； ｉｆ（！（＊Ｑ）．ｆｒｏｎｔ） ｅｘｉｔ（０）； （＊Ｑ）．ｆｒｏｎｔ－＞ｎｅｘｔ＝ＮＵＬＬ； ｒｅｔｕｒｎ １；

｝

／／判断队列是否为空，为空则返回１，否则返回０

ｉｎｔ ＱｕｅｕｅＥｍｐｔｙ（ＬｉｎｋＱｕｅｕｅ Ｑ） ｛ ｉｆ（Ｑ．ｆｒｏｎｔ＝＝Ｑ．ｒｅａｒ） ｒｅｔｕｒｎ １； ｅｌｓｅ ｒｅｔｕｒｎ ０； ｝

／／向队列中插入元素

ｉｎｔ ＥｎＱｕｅｕｅ（ＬｉｎｋＱｕｅｕｅ ＊Ｑ，ＱＥｌｅｍＴｙｐｅ ｅ） ｛ ＱｕｅｕｅＰｔｒ ｐ＝（ＱｕｅｕｅＰｔｒ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＱＮｏｄｅ））； ｉｆ（！ｐ） ｅｘｉｔ（０）； ｐ－＞ｄａｔａ＝ｅ； ｐ－＞ｎｅｘｔ＝ＮＵＬＬ； （＊Ｑ）．ｒｅａｒ－＞ｎｅｘｔ＝ｐ； （＊Ｑ）．ｒｅａｒ＝ｐ； ｒｅｔｕｒｎ １； ｝

／／若队列不为空，则删除对头元素，并返回１；否则返回 ０

ｉｎｔ ＤｅＱｕｅｕｅ（ＬｉｎｋＱｕｅｕｅ ＊Ｑ，ＱＥｌｅｍＴｙｐｅ ＊ｅ） ｛ ＱｕｅｕｅＰｔｒ ｐ； ｉｆ（（＊Ｑ）．ｆｒｏｎｔ＝＝（＊Ｑ）．ｒｅａｒ） ｒｅｔｕｒｎ ０； ｐ＝（＊Ｑ）．ｆｒｏｎｔ－＞ｎｅｘｔ； ＊ｅ＝ｐ－＞ｄａｔａ； （＊Ｑ）．ｆｒｏｎｔ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；

ｉｆ（（＊Ｑ）．ｒｅａｒ＝＝ｐ） （＊Ｑ）．ｒｅａｒ＝（＊Ｑ）．ｆｒｏｎｔ； ｆｒｅｅ（ｐ）； ｒｅｔｕｒｎ １； ｝

／＊＊

Ｂｏｏｌｅａｎ ｖｉｓｉｔｅｄ［ＭＡＸ］； ／／访问标志数组 Ｓｔａｔｕｓ（＊ＶｉｓｉｔＦｕｎｃ）（ｉｎｔ ｖ）； ／／函数变量 ｖｏｉｄ ＤＦＳＴｒａｖｅｒｓｅ（Ｇｒａｐｈ Ｇ，Ｓｔａｔｕｓ（＊Ｖｉｓｉｔ）（ｉｎｔ ｖ））

｛ ／／对图Ｇ做深度优先遍历 ＶｉｓｉｔＦｕｎｃ＝Ｖｉｓｉｔ ／／使用全局变量ＶｉｓｉｔＦｕｎｃ，使ＤＦＳ不必设函数指针参数 ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｖ）ｖｉｓｉｔｅｄ［ｖ］＝ＦＡＬＳＥ； ／／访问标志数组初始化 ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｖ） ｉｆ（！ｖｉｓｉｔｅｄ［ｖ］） ＤＦＳ（Ｇ，ｖ）； ／／对尚未访问的顶点调用ＤＦＳ ｝

ｖｏｉｄ ＤＦＳ（Ｇｒａｐｈ Ｇ，ｉｎｔ ｖ） ｛ ／／从第Ｖ个顶点出发递归地深度优先遍历图Ｇ ｖｉｓｉｔｅｄ［ｖ］＝ＴＲＵＥ；ＶｉｓｉｔＦｕｎｃ（ｖ）；／／访问第ｖ个顶点 ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｖ）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｖ，ｗ） ｉｆ（！ｖｉｓｉｔｅｄ［ｗ］） ＤＦＳ（Ｇ，ｗ）； ｝ ＊＊／

／／＿＿＿＿＿＿＿＿＿广度优先搜索＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ ／／广度优先非递归遍历图Ｇ

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

｛ ｉｆ（！ｖｉｓｉｔｅ［ｖ］） ｛ ｖｉｓｉｔｅ［ｖ］＝１； Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ）； ＥｎＱｕｅｕｅ（＆Ｑ，ｖ）；／／ｖ入队列 ｗｈｉｌｅ（！ＱｕｅｕｅＥｍｐｔｙ（Ｑ）） ｛ ＤｅＱｕｅｕｅ（＆Ｑ，＆ｕ）； ｓｔｒｃｐｙ（ｕ１，＊ＧｅｔＶｅｘ（Ｇ，ｕ））； ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｕ１）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｕ１，ｓｔｒｃｐｙ（ｗ１，＊ＧｅｔＶｅｘ（Ｇ，ｗ）））） ｉｆ（！ｖｉｓｉｔｅ［ｗ］） ｛ ｖｉｓｉｔｅ［ｗ］＝１； Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｗ］．ｄａｔａ）； ＥｎＱｕｅｕｅ（＆Ｑ，ｗ）； ｝ ｝ ｝ ｝／／ｆｏｒ ＩｎｉｔＱｕｅｕｅ（＆Ｑ）； ｆｏｒ（ｖ＝０；ｖ＜ｓｔａｒｔ；ｖ＋＋） ｛ ｉｆ（！ｖｉｓｉｔｅ［ｖ］） ｛ ｖｉｓｉｔｅ［ｖ］＝１； Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｖ］．ｄａｔａ）； ＥｎＱｕｅｕｅ（＆Ｑ，ｖ）；／／ｖ入队列 ｗｈｉｌｅ（！ＱｕｅｕｅＥｍｐｔｙ（Ｑ）） ｛ ＤｅＱｕｅｕｅ（＆Ｑ，＆ｕ）； ｓｔｒｃｐｙ（ｕ１，＊ＧｅｔＶｅｘ（Ｇ，ｕ））； ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｕ１）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｕ１，ｓｔｒｃｐｙ（ｗ１，＊ＧｅｔＶｅｘ（Ｇ，ｗ）））） ｉｆ（！ｖｉｓｉｔｅ［ｗ］） ｛ ｖｉｓｉｔｅ［ｗ］＝１； Ｖｉｓｉｔ（Ｇ．ａｄｊｍｕｌｉｓｔ［ｗ］．ｄａｔａ）； ＥｎＱｕｅｕｅ（＆Ｑ，ｗ）； ｝ ｝ ｝

｝／／ｆｏｒ ｃｏｕｔ＜＜＂＼ｂ＼ｂ＼ｂ ＂； ｃｏｕｔ＜＜ｅｎｄｌ； ｝

／／把边的访问标记设置为０，即未被访问

ｖｏｉｄ ＭａｒｋＵｎＶｉｓｉｔｅｄ（ＡＭＬＧｒａｐｈ Ｇ） ｛ ｉｎｔ ｉ； ＥＢｏｘ ＊ｐ； ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋） ｛ ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ； ｗｈｉｌｅ（ｐ） ｛ ｐ－＞ｍａｒｋ＝０； ｉｆ（ｐ－＞ｉｖｅｘ＝＝ｉ） ｐ＝ｐ－＞ｉｌｉｎｋ； ｅｌｓｅ ｐ＝ｐ－＞ｊｌｉｎｋ； ｝ ｝ ｝

／＊＊

ｖｏｉｄ ＢＦＳＴｒａｖｅｒｓｅ（Ｇｒａｐｈ Ｇ，Ｓｔａｔｕｓ（＊ ｖｉｓｉｔ）（ｉｎｔ ｖ））｛

／／按广度优先非递归遍历图Ｇ。使用辅助队列Ｑ和访问标志数组ｖｉｓｉｔｅｄ ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋ｖ） ｖｉｓｉｔｅｄ［ｖ］＝ＦＡＬＳＥ； ＩｎｉｔＱｕｅｕｅ（Ｑ） ／／置空的辅助队列Ｑ ｆｏｒ（ｖ＝０；ｖ＜Ｇ．ｖｅｘｎｕｍ；＋＋Ｖ） ｉｆ（！ｖｉｓｉｔｅｄ［ｖ］）｛ ／／ｖ尚未访问 ｖｉｓｉｔｅｄ［ｖ］＝ＴＲＵＥ；Ｖｉｓｉｔ（ｖ）； ＥｎＱｕｅｕｅ（Ｑ，ｖ）； ／／ｖ入队列 ｗｈｉｌｅ（！ＱｕｅｕｅＥｍｐｔｙ（Ｑ））｛ ＤｅＱｕｅｕｅ（Ｑ，ｖ）； ／／对头元素出队并置为ｕ ｆｏｒ（ｗ＝ＦｉｒｓｔＡｄｊＶｅｘ（Ｇ，ｕ）；ｗ＞＝０；ｗ＝ＮｅｘｔＡｄｊＶｅｘ（Ｇ，ｕ，ｗ））

ｉｆ（！Ｖｉｓｉｔｅｄ［ｗ］）｛ ／／ｗ为ｕ的尚未访问的邻接顶点 Ｖｉｓｉｔｅｄ［ｗ］＝ＴＲＵＥ； Ｖｉｓｉｔ（ｗ）； ＥｎＱｕｅｕｅ（Ｑ，Ｗ）； ｝／／ｉｆ ｝／／ｗｈｉｌｅ ｝／／ｉｆ

｝／／ＢＦＳＴｒａｖｅｒｓｅ ＊＊／

／／显示构造的无向图（包括定点数、顶点、边数、边） ｖｏｉｄ Ｄｉｓｐｌａｙ（ＡＭＬＧｒａｐｈ Ｇ） ｛

ｉｎｔ ｉ； ＥＢｏｘ ＊ｐ； ＭａｒｋＵｎＶｉｓｉｔｅｄ（Ｇ）； ｃｏｕｔ＜＜Ｇ．ｖｅｘｎｕｍ＜＜＂个顶点：＂； ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋） ｃｏｕｔ＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ＜＜＂ ＂； ｃｏｕｔ＜＜＂； ＂＜＜Ｇ．ｅｄｇｅｎｕｍ＜＜＂条边：＂＜＜ｅｎｄｌ； ｆｏｒ（ｉ＝０；ｉ＜Ｇ．ｖｅｘｎｕｍ；ｉ＋＋） ｛ ｐ＝Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ； ｗｈｉｌｅ（ｐ） ｉｆ（ｐ－＞ｉｖｅｘ＝＝ｉ） ｛ ｉｆ（！ｐ－＞ｍａｒｋ） ｛ ｃｏｕｔ＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ＜＜＂－－＞＂＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｐ－＞ｊｖｅｘ］．ｄａｔａ＜＜＂ ＂； ｐ－＞ｍａｒｋ＝１；／／已经被访问过了 ｝ ｐ＝ｐ－＞ｉｌｉｎｋ； ｝ ｅｌｓｅ ｛ ｉｆ（！ｐ－＞ｍａｒｋ） ｛ ｃｏｕｔ＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｐ－＞ｉｖｅｘ］．ｄａｔａ＜＜＂－－＞＂＜＜Ｇ．ａｄｊｍｕｌｉｓｔ［ｉ］．ｄａｔａ＜＜＂ ＂； ｐ－＞ｍａｒｋ＝１；／／已经被访问过了 ｝ ｐ＝ｐ－＞ｊｌｉｎｋ； ｝

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