查看: 1618|回复: 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)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：) b* `% q* H& l7 S
data域存储有关顶点的信息；
5 e! p* ^: Z. k- Y" y/ ?firstarc域是链接指针，指向第一条依附于该顶点的边。' t4 ]0 r$ z0 y1 {& p) G! Y+ d
所有的顶点结点组成一个顺序表。

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;9 n5 o" u* _. p/ H. \/ K
for(int v=0; v<vexNum; v++)  |4 q$ l( D+ X2 z: K8 l
{
6 h9 ^% K6 z5 n. e" G% y       if(tag[v]==0)
1 A3 o5 d$ ]# L1 R          DFS1(v);7 h  M9 x, M8 i1 O
}
* U3 O1 D) a1 x' E  w}
8 Q+ Z/ o7 {) f  T- itemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()" g7 T6 C* I) I5 {2 D" B
{
. V$ R0 t, v' V6 Z( R/ c stack<int> s;: x; b6 z, o1 Q2 r$ v
int tmp;4 s0 ?" |7 U* p
MultiAdjListNetworkArc<WeightType> *p,*q;7 X- Y5 i+ ^0 T; P
for(int i=0; i<vexNum; i++)
2 L( k; D, G( u       tag=0;' i2 y+ t* N6 ]* E
for(int i=0; i<vexNum; i++)
2 ^6 P4 M1 a- S& |8 n {
- s% \9 P' C" y8 P7 G       tmp=i;+ b( O7 d, [1 Q6 O
      while(tag[tmp]==0||!s.empty())
* t7 G* C9 D  e4 I       {9 z- a! L' b" E: M7 l
         p=vexTable[tmp].firstarc;
0 R/ j2 _. Z5 S5 S8 ~$ b: d          while(tag[tmp]==0)
, l# ~) k. G( q1 c          {
: o9 P7 k$ E) u1 v             s.push(tmp);
7 l' v' b/ E# s( A) ]             cout<<setw(3)<<vexTable[tmp].data;. v. x! C- t' u( i9 L% P, X& |
            tag[tmp]=1;. Q8 {1 M7 R) M. h2 |+ f
            p=vexTable[tmp].firstarc;( b( O8 k: a$ T
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
; g% Q0 ~2 Y. l, w" [( O6 [             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);# r! |9 Q* ?) b3 j4 U
            //cout<<" 1st    tmp="<<tmp<<endl;
/ \0 u, V& v# a, U3 T          }
$ D  E) T# ^) k6 }3 t" W' l          if(!s.empty())
; R! {5 ?" W5 p2 y" Y          {/ ?# L6 r2 @) O8 O5 E- K
            tmp=s.top();
- \" E2 o5 O: d; h" Y$ \             s.pop();8 p/ ?$ G/ N) z# T0 ^1 V3 `; E# U
            q=vexTable[tmp].firstarc;
6 G3 G) w. k' c- r5 u2 H% W             int t=tmp;  N+ J  _# J" k4 W7 x- A
            while(q&&tag[tmp]!=0)
7 P* L" R7 F0 m. y. }# g' |             {5 {" A. D, j/ n
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);7 e6 _' `/ \: J* x" R3 k- p7 w
                  //cout<<" 2nd    tmp="<<tmp<<endl;
) a- t  S2 h' r                   q=NextArc(t,q);: R: Z6 u- W. D  i" Z: m3 q
            }
8 B+ e: x% {3 _             if(tag[tmp]==0)! |+ U% g# y  h$ z* p% _/ p) C
                  s.push(t);
( O5 \8 }1 _( T! D             ///1、对应上面连通分支只有1个点的情况- c  h3 H$ K, k
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈% f# [! y; l% N4 x, M& M
            ///tmp要么等于找到的第一个未访问节点，
. k; X+ n/ y/ P3 @$ ^) x! U             ///要么等于与t相连最后一个点（已被访问过）
7 a( ]! s/ a. @0 f9 g' X! M             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点0 D& W% c, J5 }' h+ r/ H6 i8 D
         }" [2 a" `' J! q3 \! q5 ?" |6 {! p5 p
      }
0 b  r+ w2 `- j4 n6 ~% Z& F }$ H& K: f2 w$ T2 ?! ~
}2 v6 a" D! y4 T
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1* D) p) D9 H; m5 C' e& w3 H
template<class ElemType, class WeightType> int
( D$ ^& W' P( D" EMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre): [- a. h5 T4 I% M
{- ^+ j/ C; U/ ^( p7 G; w' C
if(head==pre)
' Y3 n/ u  ]0 j6 X       return -1;
! ^0 q! ]: F' V# l2 O% p5 X) u2 V5 i- m5 V4 b! y* R
MultiAdjListNetworkArc<WeightType> *p;) `, o# A, G% @* S
p=vexTable[head].firstarc;& P- B1 X: ^. [: y! \
if(pre==-1&&p!=NULL)
, Q" ^1 c( w5 R; Q5 \       return p->adjVex1==head?p->adjVex2:p->adjVex1;
3 Y$ b% u: g4 P4 e$ f: A //pre!=-1&&p!=NULL9 e- k* \- e( i2 x2 p7 |" ~4 O
while(p!=NULL)8 r% r- W; q$ }" @' H
{
. }. n7 f: c2 M: \9 f8 Y8 L8 f# E       if(p->adjVex1==head && p->adjVex2!=pre)
/ \* `. n2 @4 c# S: ~, j          p=p->nextarc1;
4 {6 ?- H8 q+ `: _8 a, |       else if(p->adjVex2==head && p->adjVex1!=pre)
7 S& J1 V# j: [9 {/ y# ]          p=p->nextarc2;
8 h" w/ W* \' u" ~. U       else if(p->adjVex1==head && p->adjVex2==pre)
6 n+ l* {4 }% D. @) ?       {: w( K9 }7 i2 @
         p=p->nextarc1;
/ B4 Q3 p& d" ]- `! r          break;
3 }6 S4 M% r. a! G, a* ?* P2 v       }
+ v9 ^" o( s  m) G       else if(p->adjVex2==head && p->adjVex1==pre)
$ k( N& c/ x$ H4 c$ L5 Q* h- ]: p       {- }+ ^1 m! {% Y; K$ A: T
         p=p->nextarc2;+ y1 L' f/ n0 {' E5 I! v
         break;
8 T% y7 H4 N' ^       }9 G/ f9 b& O; {$ g9 L  L
}
- x! j" A. q8 S: b+ }% F if(p!=NULL). `7 ^  y4 X2 `& R
{$ x, p' ^% L) {6 \
      return p->adjVex1==head?p->adjVex2:p->adjVex1;9 j& Q9 `- g2 z7 ^: n
}
7 a0 k! k5 h, ?$ L% N( Z% B else
      return -1;
, \* }# l$ Z+ l( R}
2 O. V5 U3 ^7 ?) c4 h- ~/ r5 \7 ~
! ~8 N6 y! l# Z
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()3 W6 k. N. Q: R
{
- z& ^5 T6 y7 q) N4 ?5 A stack<int> s;
. G5 Y& R' m& |/ P6 s int p,cur,pre;. e* P$ V- {0 o+ [, W6 ^: x
//MultiAdjListNetworkArc<WeightType> *p,*q;7 |; s# Z1 N; K- \" X1 ]
for(int i=0; i<vexNum; i++) tag=0;//初始化# J4 c1 I4 k4 b# j5 ^" _5 C$ m

% e2 O8 u5 ~3 J. P' ^3 P for(int i=0; i<vexNum; i++)3 C. D* }6 \7 a% Y$ m0 N
{0 X; U) \. ?8 q
      cur=i;pre=-1;) C1 \- H, A+ @) p8 w& k- [1 N9 t
      while(tag[cur]==0||!s.empty())
7 c: c* [! \: d' N       {+ a' i0 ?) W' ^& ^4 m1 L
         while(tag[cur]==0)# ~: l* I2 {1 @5 s1 `
         {
5 C4 y1 L0 t& d" o             cout<<vexTable[cur].data<<"  ";' g0 j+ s) w" z& r$ U' S1 d
            s.push(cur);; m2 k# L. l2 Z/ N
            tag[cur]=1;) a! _+ h: I. W% G
            //初次访问，标记入栈
: ?  A* Y! T4 J/ M; O
  @4 K, O( g# }3 ^8 _             p=GetAdjVex(cur,pre);//p是cur的连通顶点
4 o* |; o) b; m# Q             if(p==-1)
$ r* N. ^! g! k             {. n; h; Q0 {1 Z* q
               pre=cur;s.pop();
) d0 ?, {' D$ F/ J! ~+ [                break;
7 t: S4 s* m- {             }
; K' L8 {# z1 ^% z! s, g             else
. |4 w' u8 k/ C4 H, C             {2 K9 I- m& E  _& M( r7 k+ ]6 b
               pre=cur;
, P2 F- k' M6 h% w" h. N                cur=p;
7 c# E% F1 {0 ~4 m4 i+ E5 D, N8 R             }' f1 v* ]" ~3 P9 k6 I+ ]

7 p7 M9 R) J3 a( s          }+ A, X5 n2 S7 N2 l, H
         while(!s.empty())& {* |9 k8 v& e1 l6 L
         {
  V4 S: K# l: |+ V4 L4 v$ L5 K             cur=s.top();7 e9 |- I; }, A! E8 T+ O- o* C% r
            p=GetAdjVex(cur,pre);
% R6 m$ r' T* h! T             if(tag[p]==0)
. d! F: S5 q* z. D; I5 y             {
- ?  B2 i6 x2 H. n6 n6 W                   pre=cur;
1 Y3 D- m5 a) [7 e9 Y6 V; V  o7 |                   cur=p;% D; e7 ^; l" Q- @' I& a% D- }5 G
                  break;
! t. K# E$ v; o; i# ^1 n7 k8 b4 v. Q             }
- U, g8 F4 ^8 C' {* b             else' d4 e  H7 K+ p: W4 T; O8 g
            {
( Z3 N) j8 p3 S4 Q/ M- m                   pre=s.top();- K! Q$ r, Z+ V( P7 a6 u
                  s.pop();
" A! A% K8 [" h) Z2 H. r2 g             }8 D4 v% t/ I% r/ Q& I. V- ~
" ^) @$ g! K! g' k' x; ]- O' U
         }, q6 y" L9 {7 H  x# N. q
9 X; k; U/ `* c  ~1 @4 @$ B
      }
" W2 B! q1 V! Y/ z5 \ }6 |) b! L9 j3 X; g. w0 x
}1 z+ d5 q: J' V$ f: v
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
( N$ q1 w' t1 }{) Z! p; c/ B! r
for(int i=0; i<vexNum; i++)% k( a. x$ g/ |7 R
      tag=0;
6 D: {5 ^( w& C' e' @# P8 D( H& H0 s queue<int> q;
3 T: d+ m" D2 k7 [9 i int tmp,t;6 j4 q: C6 @1 H* x9 n
MultiAdjListNetworkArc<WeightType> *p;& a' n0 z& i8 \6 d: I
for(int i=0; i<vexNum; i++)
3 @8 l, ^' _3 e% d {8 I$ m$ L3 }8 j2 H4 @9 z0 D8 D/ l
      if(tag==0)) ?+ L) x7 O; x- n: d* z% x
      {
( F4 V. s7 R: _$ Y8 z; s          tag=1;
9 L* ~: _+ F& N* D& x/ B          q.push(i);% c( r  z' `1 @
         cout<<setw(3)<<vexTable.data;; N. a+ t' G  H
      }' M" t7 u2 e& N3 D+ ^6 ?
      while(!q.empty())
( A' z$ r. Z- |       {
1 c- ^2 p, u3 O! Q8 m! y          tmp=q.front();
4 ~1 B5 H& U' x, g) M, L; |          q.pop();, m7 e2 v7 s4 H6 A# c- _
         p=vexTable[tmp].firstarc;
; I9 w) `$ o% ?8 x( _; S          while(p!=NULL)
; k9 n3 E6 W- S; N6 K          {5 Z7 f0 b/ O4 x7 f0 ?9 A) F1 \; v6 r: j
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);6 D5 E; ]' g4 I
            if(tag[t]==0)
/ U: U( G$ a* h1 B6 [3 U             {
0 f/ `2 J. F: |. T& W7 Y                   cout<<setw(3)<<vexTable[t].data;- {) `+ J; `" j5 R! V
                  tag[t]=1;& p4 W! ^7 M% P2 V, D- N
                  q.push(t);
- h/ u; V) s( j" K             }
$ d7 w+ n" L/ x  M: t             p=NextArc(tmp,p);
% r$ J  ]6 ?7 f! q          }3 ~3 r8 a' h: [9 D
      }8 H/ v# d5 F. L/ E
}( y& y" B% j4 v8 i" d) H* h
}  L  Z  T4 T! v* i# ]/ y) a
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
- g9 G& V' l* H; B& ?) q{
$ z! X/ g. V" a MultiAdjListNetworkArc<WeightType> *p;
0 c- Q8 ?& p. B8 X2 K3 A6 D# v cout << "无向图有" << vexNum << "个点，分别为:";
; [8 _$ Q9 f7 ^. D' h for (int i = 0; i < vexNum; i++)4 Z" m) m( E3 d5 t7 p
      cout << vexTable.data << " ";
3 G3 ?) M% C. }. f% C, m cout << endl;: W2 h& t( i) c( l
cout << "无向图有" << arcNum << "条边"<<endl;
7 R% r7 h. M" z3 q" h) c: A for (int i = 0; i < vexNum; i++)6 j4 c$ @& ~7 B5 @' X: B% y- U
{
1 T' f# `8 }2 h3 z4 E4 q& V       cout<<"和" << vexTable.data << "有关的边:";4 L" X5 y# _+ D4 Y
      p = vexTable.firstarc;
: x5 V& s4 J) G1 x% G2 I3 P       while (p != NULL)0 i! T8 [7 L# {  o. ]7 f
      {
- X) H) s2 x+ Y6 {$ S          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";/ ]) ]4 D! t) r* x$ l
         p=NextArc(i,p);/ y1 h! U* |9 M' M5 \. P$ R
      }, c3 X5 `% H) }9 P1 U& c
      cout << endl;
: s5 ?0 m9 x; {9 r }
5 H. I. u* a$ S3 H& `0 V/ |}) J( v& T- [/ I7 {3 K+ Y8 K( X
* @2 ?0 @( h/ [( s( j6 m5 p5 s

3 v( o6 p! y3 @+ W& \邻接多重表与邻接表的对比3 {! Z& u% v6 ~% A0 D! c" h& k1 R

; q5 P( i, ~* W邻接表链接
& K$ ]1 L& Z5 o" q+ v. t在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
- A0 _9 y+ }6 V* H  e% c7 Z在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。- H: c' g9 j/ h/ ?0 i7 j" L
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
————————————————5 k5 L" Z: U3 K/ I  y( O; m* @# ~, O
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。( |$ K$ y' {: t# J
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958) I+ W  g  y2 N: X
8 A7 `6 Q( C+ _3 R: R

- e1 V* K" Y; a) q/ F" P% s- D4 c( Y- s, c
! C0 X* p6 }  S) p+ K, \
————————————————2 H. g- [2 P2 x- g$ E
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  c6 a4 c& J3 |  Y原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958% s9 \0 Y0 z0 i; u8 y

" x* L2 t2 w0 F; |, n  Y/ ~, p2 J% v9 n