查看: 1639|回复: 0

图的存储结构——邻接多重表（多重邻接表）的实现

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-4-26 15:26 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

邻接多重表的顶点结点类模板

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：* Q+ C |+ g% Q& y
data域存储有关顶点的信息；% b# i1 S- ~# \: M
firstarc域是链接指针，指向第一条依附于该顶点的边。9 y' G v' ^ W6 U$ y
所有的顶点结点组成一个顺序表。

template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
{
public:
ElemType data;
MultiAdjListNetworkArc<WeightType> *firstarc;

MultiAdjListNetworkVex()
{
firstarc = NULL;
}
MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
{
data = val;
firstarc = adj;
}
};

邻接多重表的边结点类模板

在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
tag是标记域，标记该边是否被处理或被搜索过；
weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。

template <class WeightType>
class MultiAdjListNetworkArc
{
public:
int mark;                                     //标记该边是否被搜索或处理过
WeightType weight;                            //边的权重
int adjVex1;                                  //边的一个顶点
MultiAdjListNetworkArc<WeightType>* nextarc1; //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
int adjVex2;
MultiAdjListNetworkArc<WeightType>* nextarc2;

MultiAdjListNetworkArc()
{
adjVex1= -1;
adjVex2= -1;
}
MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
{
adjVex1 = v1;    adjVex2 = v2;
weight = w;
nextarc1 = next1; nextarc2=next2;
mark = 0;          //0表示未被搜索，1表示被搜索过
}

邻接多重表的类模板

1.类定义

template <class ElemType,class WeightType>
class MultiAdjListNetwork
{
protected:
int vexNum, vexMaxNum, arcNum;
MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
int* tag;
WeightType infinity;

public:
MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

void Clear();
bool IsEmpty()
{
      return vexNum == 0;
}
int GetArcNum()const
{
      return arcNum;
}
int GetvexNum()const
{
      return vexNum;
}

int FirstAdjVex(int v)const;
int NextAdjVex(int v1, int v2)const;
MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

void InsertVex(const ElemType& d);
void InsertArc(int v1, int v2, WeightType w);

void DeleteVex(const ElemType& d);
void DeleteArc(int v1, int v2);

MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

///深度优先遍历
void DFS1(const int v);
void DFS1Traverse();
void DFS2();

int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
void DFS3();

void BFS();
void Show();
};

2.函数的实现
研讨题，能够运行，但是代码不一定是最优的。

#include <stack>
#include <queue>

template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
if(vertexMaxNum < 0)
      throw Error("允许的顶点最大数目不能为负！");
if (vertexMaxNum < vertexNum)
      throw Error("顶点数目不能大于允许的顶点最大数目！");
vexNum = vertexNum;
vexMaxNum = vertexMaxNum;
arcNum = 0;
infinity = infinit;
tag = new int[vexMaxNum];
vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
for (int v = 0; v < vexNum; v++)
{
      tag[v] = 0;
      vexTable[v].data = es[v];
      vexTable[v].firstarc = NULL;
}
}
template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
if (vertexMaxNum < 0)
      throw Error("允许的顶点最大数目不能为负！");
vexNum = 0;
vexMaxNum = vertexMaxNum;
arcNum = 0;
infinity = infinit;
tag = new int[vexMaxNum];
vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
if (v < 0 || v >= vexNum)
      throw Error("v不合法！");
if (vexTable[v].firstarc == NULL)
      return -1;
else
      return vexTable[v].firstarc->adjVex1;
}

template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
MultiAdjListNetworkArc<WeightType>* p;
if (v1 < 0 || v1 >= vexNum)
      throw Error("v1不合法！");
if (v2 < 0 || v2 >= vexNum)
      throw Error("v2不合法！");
if (v1 == v2)
      throw Error("v1不能等于v2！");
p = vexTable[v1].firstarc;
while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
      p = p->nextarc;
if (p == NULL || p->nextarc == NULL)
      return -1;  //不存在下一个邻接点
else if(p->adjVex1==v2)
      return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
else
      return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
if (IsEmpty()) return;
int n = vexNum;
for (int u = 0; u < n ; u++)
      DeleteVex(vexTable[0].data);
return;
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
Clear();
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
vexMaxNum = copy.vexMaxNum;
vexNum = copy.vexNum;
vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
arcNum = 0;
infinity = copy.infinity;
tag = new int[vexMaxNum];

for (int v = 0; v < vexNum; v++)
{
      tag[v] = 0;
      vexTable[v].data = copy.vexTable[v].data;
      vexTable[v].firstarc = NULL;
}
MultiAdjListNetworkArc<WeightType>* p;

for (int u = 0; u < vexNum; u++)
{
      p = copy.vexTable.firstarc;
      while (p != NULL)
      {
         InsertArc(p->adjVex1, p->adjVex2, p->weight);
         p=NextArc(u,p);
      }
}
}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>:

perator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
if (this == &copy) return *this;
Clear();
vexMaxNum = copy.vexMaxNum;
vexNum = copy.vexNum;
vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
arcNum = 0;
infinity = copy.infinity;
tag = new int[vexMaxNum];

for (int v = 0; v < vexNum; v++)
{
      tag[v] = 0;
      vexTable[v].data = copy.vexTable[v].data;
      vexTable[v].firstarc = NULL;
}
MultiAdjListNetworkArc<WeightType>* p;

for (int u = 0; u < vexNum; u++)
{
      p = copy.vexTable.firstarc;
      while (p != NULL)
      {
         InsertArc(p->adjVex1, p->adjVex2, p->weight);
         p=NextArc(u,p);
      }
}
return *this;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
if(p==NULL) return NULL;
if(p->adjVex1==v1)
      return p->nextarc1;
else
      return p->nextarc2;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>:

astArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
if(p==NULL)return NULL;
MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
if(q==p)
      return NULL;
while(q)
{
      if(q->nextarc1==p ||q->nextarc2==p)
         break;
      q=NextArc(v1,q);
}
return q;
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
if (vexNum == vexMaxNum)
      throw Error("图的顶点数不能超过允许的最大数！");
vexTable[vexNum].data = d;
vexTable[vexNum].firstarc = NULL;
tag[vexNum] = 0;
vexNum++;
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
MultiAdjListNetworkArc<WeightType>* p,*q;
if (v1 < 0 || v1 >= vexNum)
      throw Error("v1不合法！");
if (v2 < 0 || v2 >= vexNum)
      throw Error("v2不合法！");
if (v1 == v2)
      throw Error("v1不能等于v2！");
if (w == infinity)
      throw Error("w不能为无穷大！");

p = vexTable[v1].firstarc;
while(p)
{
      if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
      {
         if(p->weight!=w)
            p->weight=w;
         return;
      }

      p=NextArc(v1,p);
}
p = vexTable[v1].firstarc;
q = vexTable[v2].firstarc;
vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
vexTable[v2].firstarc =vexTable[v1].firstarc;
arcNum++;
}

template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>:

eleteArc(int v1, int v2)
{

MultiAdjListNetworkArc<WeightType>* p, * q,*r;
if (v1 < 0 || v1 >= vexNum)
      throw Error("v1不合法！");
if (v2 < 0 || v2 >= vexNum)
      throw Error("v2不合法！");
if (v1 == v2)
      throw Error("v1不能等于v2！");

p = vexTable[v1].firstarc;
while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
{
      q = p;
      p = NextArc(v1,p);
}//找到要删除的边结点p及其前一结点q

if (p != NULL)//找到v1-v2的边
{
      r=LastArc(v2,p);
      if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
         if(p->adjVex2==v2)
            vexTable[v1].firstarc = p->nextarc1;
         else vexTable[v1].firstarc=p->nextarc2;
      else//不是第一条边
      {
         if(q->adjVex1==v1)
            q->nextarc1 = NextArc(v1,p);
         else
            q->nextarc2=NextArc(v1,p);

      }
      if(r==NULL)
         if(p->adjVex2==v2)
            vexTable[v2].firstarc = p->nextarc2;
         else vexTable[v2].firstarc=p->nextarc1;
      else
      {
         if(r->adjVex2==v2)
            r->nextarc2 = NextArc(v2,p);
         else
            r->nextarc1=NextArc(v2,p);
      }
      delete p;
      arcNum--;
}

}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>:

eleteVex(const ElemType& d)
{
int v;
MultiAdjListNetworkArc<WeightType>* p;
for (v = 0; v < vexNum; v++)//找到d对应顶点
      if (vexTable[v].data == d)
         break;
if(v==vexNum)
      throw Error("图中不存在要删除的顶点！");

for (int u = 0; u < vexNum; u++)//删除与d相连的边
      if (u != v)
      {
         DeleteArc(u, v);
      }
vexTable[v].firstarc=NULL;

vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
vexTable[v].data = vexTable[vexNum].data;
vexTable[v].firstarc = vexTable[vexNum].firstarc;
vexTable[vexNum].firstarc = NULL;
tag[v] = tag[vexNum];
//原来与最后一个顶点相连的边改为与v相连
for (int u = 0; u < vexNum; u++)
{
      if (u != v)
      {
         p = vexTable.firstarc;
         while (p)
         {
            if (p->adjVex1==vexNum)
                  p->adjVex1= v;
            else if(p->adjVex2==vexNum)
                  p->adjVex2=v;
            p = NextArc(u,p);
         }
      }
}
}
///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:

FS1(const int v)
{
tag[v]=1;
cout<<setw(3)<<vexTable[v].data;
MultiAdjListNetworkArc<WeightType> *p;
p=vexTable[v].firstarc;
while(p)
{
      if(tag[p->adjVex1]==0)
         DFS1(p->adjVex1);
      else if(tag[p->adjVex2]==0)
         DFS1(p->adjVex2);
      p=NextArc(v,p);
}
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:

FS1Traverse()
{
for(int i=0; i<vexNum; i++)
      tag=0;! t8 ?! ]) n0 `# G
for(int v=0; v<vexNum; v++)
3 q2 V. L# z  K {
8 M7 A) Z6 i, k& q' F" }3 |       if(tag[v]==0)9 \5 M7 C3 h; p
         DFS1(v);5 k$ k+ ?, ^3 n' J
}! x7 m  w4 J& K# A" `- X3 J# g
}' _) B" m" \/ c# Y- A: z$ Z
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
1 D9 L) ]& ?( G/ ]  X! A0 [{. [/ p8 T0 c8 z* v, e3 T$ s
stack<int> s;& P  E, i, {; s- G  {- b6 k; D  {
int tmp;0 Q( S. [3 e, O+ Z
MultiAdjListNetworkArc<WeightType> *p,*q;
: A' u2 U. L1 {+ Z" k, c! C, F5 h for(int i=0; i<vexNum; i++)
! R. N- r) l! {& ^" J( q       tag=0;3 l3 y) k9 f4 W( e+ [$ v
for(int i=0; i<vexNum; i++)6 A5 ^  Q+ ]% K+ Q5 C+ v  C
{
$ L/ B7 R& ^. v. N       tmp=i;  f; R- C0 V) Y: }% r
      while(tag[tmp]==0||!s.empty())
  W& x* q7 I* L  ?       {
- ?; i6 \* _' k$ r, c1 u          p=vexTable[tmp].firstarc;' \- z. |- U6 C# U6 y5 Y
         while(tag[tmp]==0)( t/ f- v$ T) z) D: i3 ~/ h& n
         {. i- N# l, f' t
            s.push(tmp);
0 r6 A/ Q- ^6 W) T! M2 k             cout<<setw(3)<<vexTable[tmp].data;7 |# Z) i+ L/ h
            tag[tmp]=1;+ X' R1 G& H( N3 |1 w
            p=vexTable[tmp].firstarc;
' b% x% a  D( I. N9 ?7 ^             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for! y$ k* e2 y+ s) R5 y
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);+ D8 w3 S7 C2 E9 Y( ?. k0 e
            //cout<<" 1st    tmp="<<tmp<<endl;
1 `; i! F, z2 Z1 Z6 ]0 B          }- ~/ d6 J. x; F' y$ l
         if(!s.empty()); y; K! S5 u) R& ^+ k) W4 X5 A
         {' b$ z8 G* b2 u, P  L& B1 M( |
            tmp=s.top();* ]& E3 C, h: H" W, S
            s.pop();
, x: _0 Y7 }% G, V             q=vexTable[tmp].firstarc;
- d' G7 S3 ~+ H8 c             int t=tmp;/ V! U% Z' x1 S; f: J6 @% f
            while(q&&tag[tmp]!=0)  R- x( E1 z% |! I" d9 @1 _
            {
  X) p; o  N# z% u+ v                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);3 U, n- Z  s- _1 J- p# b
                  //cout<<" 2nd    tmp="<<tmp<<endl;6 C# a4 \" Q$ m8 [6 z
                  q=NextArc(t,q);, N) N/ d1 Z$ U% X- c& W
            }
# A. N" L; s* i- K             if(tag[tmp]==0)
6 j$ i' H/ w. S4 \7 f; [3 l7 v; }                   s.push(t);
& N7 }% U2 j' ^7 K' Y) k             ///1、对应上面连通分支只有1个点的情况  B7 K" T+ [" o: l# D! V: X$ G/ e; E( k
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
7 U, M6 {  X6 c, }3 j2 J9 g) N' J             ///tmp要么等于找到的第一个未访问节点，
  W2 g6 [# R3 H             ///要么等于与t相连最后一个点（已被访问过）3 r2 i+ t3 Z: m# J
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
" h5 F7 D" H% ?  w' s# h# H0 Y          }
1 x1 u3 Y# t, v, x       }
$ {- ~5 g. ?/ a7 \: t9 @% S }
3 _# H& y" B1 C* I7 }* M}1 A0 y; T1 y$ I# H  P8 q1 \1 n
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
+ ]3 k& m: G  E. y% q8 ~1 `; Ctemplate<class ElemType, class WeightType> int& \7 L9 }$ L% K; t# u
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
8 X8 V6 \% H" u/ n9 I{
( W5 N  U$ u* Z2 x- f' n  B8 F if(head==pre)
0 F& B8 T+ ^# [# V( o1 J' M/ w% c       return -1;7 B3 K: f1 D" \# n; G2 i
6 G# x8 \, J$ O4 p
MultiAdjListNetworkArc<WeightType> *p;
" J* V* K- C/ n" w, M& o' _ p=vexTable[head].firstarc;
" q& {0 t' s2 U; Y) B% B3 ?* y if(pre==-1&&p!=NULL)
/ L" g; O( i8 m  a, [2 f$ x       return p->adjVex1==head?p->adjVex2:p->adjVex1;
# a, @, v) l) u0 I& g //pre!=-1&&p!=NULL
9 Q1 O' R) {7 N" X5 ^ while(p!=NULL)
* N+ h5 o5 r$ o" V3 p/ D" ] {6 h3 b. T1 ]  \' i1 l7 B) v# i
      if(p->adjVex1==head && p->adjVex2!=pre)" E0 Z) l& \: p7 ~* D( t! i
         p=p->nextarc1;
6 q/ d+ m  l; m* Z       else if(p->adjVex2==head && p->adjVex1!=pre)+ W: s  O( E6 k. b2 c' H
         p=p->nextarc2;
8 ~2 H! S7 z& z8 f, k/ C4 f) C- i/ d       else if(p->adjVex1==head && p->adjVex2==pre)6 F+ S7 [& o8 L  X& X6 c8 t
      {. Z! F: f% o0 w2 v1 x. w6 u- ~
         p=p->nextarc1;
, D9 t2 u. |' H* r/ ?          break;
+ T; N1 C: A: K) n3 Q  F       }
; h) z2 R; A9 `, l& D/ v! A# H6 @       else if(p->adjVex2==head && p->adjVex1==pre)
9 s) \/ K' ?, y# J; A8 Q9 V       {
/ _) o0 d2 i4 Q/ z          p=p->nextarc2;
% ~5 z& A9 z: x' |! o- n          break;+ c; q( {0 z& P% @3 K  X
      }' g& B% r0 ?# N+ K
}# G- l# H  C  t
if(p!=NULL). v" X. J* ]. b* K
{# n0 b$ O! _6 K) ~
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
1 c' ^& |6 Q) o }
+ }6 n3 S  U) @  }* u7 q else
" O* v5 c" T( h3 g       return -1;9 j" m) j& R; j% K$ }# s
}
+ U$ D& J2 q4 S0 n; l5 X. s, Z0 Q! r2 {: R, c2 V. s" q8 x% R. A2 h

% X- F5 e& I( s5 x( `1 B3 Otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(); P. V+ F' o- R- c7 u' w
{1 _; A0 G' w9 x+ @0 i; r
stack<int> s;/ ~6 B* q- ?5 s1 N! H' m, D7 n
int p,cur,pre;
5 Q* }) D8 v4 ]- t //MultiAdjListNetworkArc<WeightType> *p,*q;* L2 m" N2 N* i% M, J. n
for(int i=0; i<vexNum; i++) tag=0;//初始化4 w7 b. P2 ~; O# |# Z
& t7 |- u( `3 Z' F7 [8 @, m* ~! c% a
for(int i=0; i<vexNum; i++)2 r+ v7 @# v' j
{
5 u3 @# G4 \! q8 v8 ^       cur=i;pre=-1;
0 ?4 U7 r- e7 o! s" r# b' L       while(tag[cur]==0||!s.empty())% |' C  t3 I* g( Z+ @- X  y, d3 L2 `
      {) F1 Y6 R+ h0 g' j( w- T4 Z
         while(tag[cur]==0). j1 [. P; p9 T. \& B2 e# E
         {
# V. Q; T; j2 a/ a             cout<<vexTable[cur].data<<"  ";7 Z: U% w" i7 X) _9 R
            s.push(cur);
8 r% c& j7 I' j1 [3 g9 q8 Z             tag[cur]=1;
5 M1 K) L; v! \1 A1 n: X             //初次访问，标记入栈
- E8 J9 L5 d2 L; K+ r
1 q: R/ E1 W* f             p=GetAdjVex(cur,pre);//p是cur的连通顶点- a2 M* B3 b. K8 F" x/ f
            if(p==-1). x# h" U& G3 n# ?* H( P& D
            {
- a9 x6 {. q' Z. r6 c; s, F                pre=cur;s.pop();
% D* P; S) _4 H2 r                break;' q) P/ a) o/ c7 e; b
            }
: Q1 k( m% n# z- |" M' ^9 b             else: a9 d/ K7 h8 A3 E! n4 B& `
            {
+ T: B6 p1 P8 D$ P, B                pre=cur;. G1 h3 K4 _: o
               cur=p;" L+ \5 ?. k; R
            }4 j+ k6 X. Y: h' x% k

& p2 v; @3 ]* F' ]2 f" V5 `          }# b1 L. h1 b* i- r/ }
         while(!s.empty())7 E. X- \: |' Y4 n; D
         {
( ~0 T. D$ Q+ i% T& l1 b. P  b$ b             cur=s.top();" C7 v! J$ c* {9 m, K
            p=GetAdjVex(cur,pre);6 R, d* T8 \1 q; _
            if(tag[p]==0)3 ^. I9 y$ d; s
            {/ M5 G* L( a1 F$ F4 n. D7 m
                  pre=cur;
$ z0 ?+ {! G  [                   cur=p;
; h5 ]' _2 D" B, a; L% [# i+ _                   break;) {2 ?+ s' P9 Y  _% s
            }
: Z7 U# D9 Y, x+ L& R             else3 k: `" B' O/ F  w2 |2 ]' D# w9 X
            {* ?! o# k# v0 ?# K' C# E
                  pre=s.top();
) p& f# x% G8 K1 w) p% R                   s.pop();
) t2 @2 U5 @5 n; d( J' t4 H$ r, X             }
* ?& n% |' t5 w2 i+ P8 o3 U( f9 V4 A2 B$ V+ ]( J
         }9 p. d5 _$ N' N9 S9 v2 p- D+ Q9 M

1 \3 x* h8 _5 f3 S       }4 C7 e, T* s4 L/ F6 _7 z
}
: Q" j1 d, L% u6 w- c' H}
/ Z0 x$ M( D" e* ?: g6 k' ^template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()) B2 r  Q6 \; P- y& s8 r4 D
{$ |0 h) _; O: \1 V/ ^  v. i0 x
for(int i=0; i<vexNum; i++)
6 U+ H. P1 a: R! r- @9 @+ C2 G       tag=0;2 D+ [% J0 `0 r  `' S- a
queue<int> q;
1 z- f! g8 `+ _4 O  T int tmp,t;
9 S7 P9 w( U4 T+ V" h& g MultiAdjListNetworkArc<WeightType> *p;) T- s+ ?, d  P* A  R2 ]
for(int i=0; i<vexNum; i++)9 x4 F! e3 d/ \6 I1 a( V
{+ n, u# V( S/ L! ]0 e& o* ~4 O/ N
      if(tag==0)6 W) x) L) s6 [5 T2 s6 ^; v: u7 n
      {
. g5 g2 K& t! q' W          tag=1;9 y! @  w2 y/ G4 @' w0 a
         q.push(i);
, t! F! G  E" }          cout<<setw(3)<<vexTable.data;
. }1 p8 a# C: M' P2 ]- v7 D       }  D  N- F3 F3 O9 t+ ~8 r* ^3 H. ?
      while(!q.empty())' x- ?( F; T, u: }* C! h
      {
- e# i6 J7 R: s3 ^          tmp=q.front();
7 m# ~; Y4 ~& r7 s. {9 q; `7 G          q.pop();
9 Z4 u; s- x$ ?          p=vexTable[tmp].firstarc;
) E! v; A. v2 T+ N          while(p!=NULL)) Q) F$ ~6 |" ~+ D, P
         {
. D" {) C/ ]  X2 L             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 b6 L& w3 |/ b6 `% j) F7 w8 n             if(tag[t]==0)# {. W7 u  T. C. Q; v
            {0 \, N/ ~; {. r: d6 T. I
                  cout<<setw(3)<<vexTable[t].data;/ f5 W. K2 E9 L- Z0 B0 e! G! i# d
                  tag[t]=1;
' o  \1 P; {% E5 I                   q.push(t);  r+ M9 X- D  \$ D! ]
            }
' p- F% h3 ]9 U+ ?* H' ?/ k             p=NextArc(tmp,p);
2 C, S4 x: _0 ]& Z/ ^% N7 ]          }' G) E! i2 c/ T! V& L( Z  F
      }) V- |2 {, J! Z1 z1 D
}
! V' X$ }/ G# P5 H: P! U}$ g1 D/ e: V$ M; z$ R' e2 z
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()6 p& B. l2 N9 q0 K* m" L) E
{
, O* u4 a, g3 ~7 R9 g4 k MultiAdjListNetworkArc<WeightType> *p;
. ]0 p: r- a  `3 R" l4 z cout << "无向图有" << vexNum << "个点，分别为:";
" w% @- y3 L" |4 X; }( P' M- u for (int i = 0; i < vexNum; i++)
  C  n3 _0 r+ n       cout << vexTable.data << " ";
- ?# C) y9 _4 ?: I/ g; P cout << endl;3 j  R5 Q! O% q' `* k. R
cout << "无向图有" << arcNum << "条边"<<endl;0 k. [9 v* L. I  R" V/ r& ~/ q
for (int i = 0; i < vexNum; i++)
# w8 }/ @8 }3 ^& n( f {
# e6 K/ m2 q' _) O3 j       cout<<"和" << vexTable.data << "有关的边:";+ b0 y- a% J# M2 T  c& b+ e+ m" ?
      p = vexTable.firstarc;6 \! p/ N+ `/ J( Y+ K( L
      while (p != NULL)3 @2 V# Z0 u: Q. Z- S8 H5 o
      {
  j4 P2 g! M& T9 y$ h7 Y* u+ t0 A          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";- L# T+ D9 C+ N3 c
         p=NextArc(i,p);! U/ M+ d  D" C/ J: i6 T$ i6 {
      }+ z* G% r6 K6 d# S0 m
      cout << endl;  u+ }2 P0 r/ G% q3 l
}
3 h3 x- X5 v, [- M}
( J( m5 `& P" g( ?# v. c" M
  Y3 a- i+ K2 A; ]* b& v. ?- h. e& C3 {6 i9 ?( K4 d
邻接多重表与邻接表的对比8 G+ R4 t8 Z* i6 N2 K0 j' Q" Y
% x6 M3 ^3 F" `* r$ }9 V
邻接表链接
, T3 {$ d* P( z% v* L# c& @/ ]  f在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
& r( G# x0 B* q& M, G在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
( M) s/ g* \% s  o  W$ }为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
& v4 ]9 l4 X" H; ~————————————————9 ]! s% h, x. H6 Y
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' z( R# k) i2 o6 N# h原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669582 u8 L6 q/ z+ ?, ]2 R: _

- R. B* N" ]3 O3 P4 n9 n4 }! X: v5 y& B5 I: q

% S1 e. d- c  b; N& u. G: s# P6 v  U( m  J3 H
————————————————
8 C3 g) {3 v8 B# Q4 D0 R) ]版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。8 K6 ]4 }" u. `9 \
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958& [5 ?; ^0 b- M5 k, V" l- m

: q: L) |" T- l. U, M6 l2 N) m! T5 n% P8 N0 _