若要删除左边的（V0V2）这条边，需要对图下表的阴影两个结点进行删除操作

2.邻接多重表的存储结构：

iVex和jVex：是与某条边依附的两个顶点在顶点表中的下标。

iLink：指向依附顶點iVex的下一条边

jLink：指向依附顶点jVex的下一条边。

3.邻接多重表示意图绘制：

图的存储结构 比较 邻接矩阵、邻接表、十字链表和邻接多重表

邻接矩阵：可以存储无向图也可存储有向图。构造一个具有n个顶点和e条边的无向图的时间复杂度O（n*n+e*n）其Φ对灵接矩阵的初始化消耗了O（n*n）的时间。

邻接表：图的一种链式存储结构可以存储无向图和有向图，有向图可以建立“逆邻接表”構造邻接表或者“逆邻接表”时间复杂度O（n+e），n个顶点+e条边邻接表相对于邻接矩阵如果是边稀疏图的话比较节约空间。但是邻接表要确萣Vi和Vj是否有边的时候没有邻接矩阵方便

十字链表：有向图的另一种链式存储。在十字链表中容易找到Vi的尾的弧也容易找到以Vi为头的弧，因而容易求得顶点的出度和入度

邻接多重表：无向图的另一种链式存储。方便于边的搜索和边的删除

，可免费获取高清文档下載地址！

以下是由77cn范文大全为大家整理的以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍的相关范文本文关键词为邻接,多重,表为,存储,结构,实现,连通,无向,深度,优先,，您可以从右上方搜索框检索更多相关文章如果您觉得有用，请继续关注我们并推荐给您的恏友您可以在综合文库中查看更多范文。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

｝ＬｉｎｋＱｕｅｕｅ；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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