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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
/ }8 g |+ M: N/ xdata域存储有关顶点的信息；
# ^: |' [- k2 i% D1 b/ ifirstarc域是链接指针，指向第一条依附于该顶点的边。
8 E7 w7 c$ @# B4 J' O所有的顶点结点组成一个顺序表。

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;3 v# s& E+ C! \# j: n2 V# f
for(int v=0; v<vexNum; v++)& M+ k  q8 J; |/ H/ Y" [- G1 `
{# ~/ b7 }0 g6 y
      if(tag[v]==0)
$ D) ~, V( U4 Z2 z          DFS1(v);
; q* J+ N  x7 y+ ~" x' | }! ]4 g* c0 O. N  z
}
6 z8 Z) J% m: i5 |+ M* Xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
, C7 W8 p. e/ N8 I; E{. \' \! y0 W/ n9 p2 l3 c- w
stack<int> s;: B1 O, u, }# B2 N% |  ^# l
int tmp;7 Z( X7 |2 b- E/ b
MultiAdjListNetworkArc<WeightType> *p,*q;
! z. k, k6 p+ t+ | for(int i=0; i<vexNum; i++)
% I& x# w- i' Q       tag=0;9 N4 R9 p/ n. D  h
for(int i=0; i<vexNum; i++)' ?+ g. E& _* r+ k6 G
{! j( B8 b( A0 F' v0 v* X  D8 \5 x7 p/ C
      tmp=i;5 F& q% t& O, c7 S4 x4 a
      while(tag[tmp]==0||!s.empty())" G) V2 ~" {  d- s) B( i1 c
      {" V+ |; |: w5 Q$ W$ `
         p=vexTable[tmp].firstarc;% U4 t! ~3 x+ u* V4 n
         while(tag[tmp]==0)
- P, L  X6 h0 |. a          {
6 d4 V7 s: X& l             s.push(tmp);+ r4 A( p1 C: u4 G, B, A
            cout<<setw(3)<<vexTable[tmp].data;8 }# J% E$ `% T/ b5 Z
            tag[tmp]=1;
( M3 o5 T' }; v: l9 x             p=vexTable[tmp].firstarc;
- ?& W, L4 K, I0 n8 ^             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
& ?" A$ K1 d) h             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);. |1 Z% _; s% O2 [7 ?. V/ u" S. i( |% l
            //cout<<" 1st    tmp="<<tmp<<endl;
! H2 W3 r& o- I1 q) D+ S          }
6 x" X2 Q- M0 e' W          if(!s.empty())
( n5 W+ H! ]3 g- W          {8 k4 u- \; R- d
            tmp=s.top();
) H- _. M" `0 q! }6 u( Z             s.pop();
% _- Z3 z; X% M" w8 w             q=vexTable[tmp].firstarc;
; U0 P8 O9 i* C- o0 A             int t=tmp;$ e6 A; d) u5 l! x
            while(q&&tag[tmp]!=0)
- k, P! x4 s8 {7 }. ?: E             {
' K0 t: V# Z6 M                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                  //cout<<" 2nd    tmp="<<tmp<<endl;
6 v4 |- s; J7 h                   q=NextArc(t,q);
- J: z6 y4 N5 j$ t7 U             }! I9 h/ J  U  o" c% r+ m
            if(tag[tmp]==0)0 e7 x2 U( _$ ~! \' n
                  s.push(t);
8 S; N/ Z/ r* D! |4 H- R9 U" R             ///1、对应上面连通分支只有1个点的情况( ]7 C& ^7 U1 i2 T1 O2 i1 X3 h
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
- n; t, L! U9 e/ e& `' L- `             ///tmp要么等于找到的第一个未访问节点，+ k$ M3 ]( w$ Y+ E, O
            ///要么等于与t相连最后一个点（已被访问过）
# o, [, l9 B6 c             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点9 l( |$ n  b' U" b5 \
         }0 w* h+ A- t" p3 i2 I  l
      }: g& C; Y5 T1 ~1 s
}
4 f5 t) V: j. T' `}
0 w2 J4 h: \9 ?1 y( m  x//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1; l2 p) l9 a+ R/ E3 l
template<class ElemType, class WeightType> int- g: D2 c0 q, ]6 N
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
( \) D% V1 b+ f9 e% J; h{
6 |- A9 _; y3 @, `% O if(head==pre)
7 a8 C  @+ ]" j+ j5 l7 S       return -1;

  q  P& ~. g4 L& |" i/ f MultiAdjListNetworkArc<WeightType> *p;& j, V$ R0 C+ x& l0 ~! h
p=vexTable[head].firstarc;5 M! d$ @7 u% f/ V2 L3 L5 m6 @
if(pre==-1&&p!=NULL)  A& @5 v6 x* ]/ d( g& o
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
6 K9 I4 H# U0 a4 K3 m //pre!=-1&&p!=NULL! k4 \% Z8 H8 y+ F+ V2 ^+ i% P
while(p!=NULL): W  ~2 n+ H6 b5 v. h- c6 B
{& n: l9 ?' I7 a! d
      if(p->adjVex1==head && p->adjVex2!=pre)$ j( u8 G" g  G( y6 ]  r9 l0 E# M9 h
         p=p->nextarc1;- `1 ]+ y$ y0 @
      else if(p->adjVex2==head && p->adjVex1!=pre)
; A$ y! v! Z) w# W7 P. y# t          p=p->nextarc2;
8 s# I3 Q1 A# |+ Y- b/ B7 n       else if(p->adjVex1==head && p->adjVex2==pre)1 E( G% Q: ?4 O) g* C) X4 e$ G+ a3 B
      {
3 o1 d9 R" w- f! O" m9 D0 P6 T          p=p->nextarc1;$ C% Q! a9 V( ^" M$ L/ |& E( N3 K
         break;' w$ l1 g' q0 \
      }
( Q/ O; p# q" f       else if(p->adjVex2==head && p->adjVex1==pre)4 Y9 B" H2 U& O, ^& R* q# P8 M
      {, P0 J( c  T& s" r9 o! g. E5 c
         p=p->nextarc2;; _/ _& i* q% o& S, O
         break;& j& u6 {) L# J" I' E3 {0 u
      }
& ^/ u, V$ O2 x  A4 n$ H1 z, X* l }4 J- f! r- R2 Z- B
if(p!=NULL)
2 p; M3 f: b  G4 ~ {0 W; _6 m( h7 q, \0 d4 Q- p6 N
      return p->adjVex1==head?p->adjVex2:p->adjVex1;( T9 v! X) \' ]# n1 s5 Y( s
}
8 Z: p/ l+ R9 J else
0 o* I) |1 f6 L* ^6 {( H       return -1;
: i. L& X* K" w}
# @( E3 \/ e0 a' W
+ s: q/ {* z& K' ]  }1 f' @
+ V' t2 f, {( a; E: c. C7 E9 L1 h/ Stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
' ^$ F1 p. S2 z; Y0 \  M. e{6 B: g+ B5 G/ X; |2 H  E3 w9 K
stack<int> s;
; c& ^* F3 i) o8 r$ n$ q# c int p,cur,pre;
: Z9 y) X) x: A3 L //MultiAdjListNetworkArc<WeightType> *p,*q;  a. X6 ~4 F# K2 ^/ t, ?* L
for(int i=0; i<vexNum; i++) tag=0;//初始化
' I, v$ j% W5 N; b
- ?5 S3 y  J! m3 D5 V for(int i=0; i<vexNum; i++)9 u5 s9 Q$ a7 ]2 Z
{
9 A, H8 L# \3 o0 A       cur=i;pre=-1;% i# e% |0 b6 y3 n* W0 n. M2 p
      while(tag[cur]==0||!s.empty()), |0 ?; w4 W: m3 _0 D1 N4 h
      {0 x9 |: D/ Y% K( p
         while(tag[cur]==0)# y  h1 _% N: ]
         {/ `% h' k' y2 S# L; l% o
            cout<<vexTable[cur].data<<"  ";  _! S4 Y# |, z# P( G# q
            s.push(cur);; D, ?' V' M) J- d! y
            tag[cur]=1;
8 ?' |/ x. }# ^& ?# c             //初次访问，标记入栈
* w: C; ]. A4 D0 N5 F
9 W) y8 M4 d% q/ ~! J             p=GetAdjVex(cur,pre);//p是cur的连通顶点
8 I" Q8 U: U2 I6 e, `8 |. Z# u4 U             if(p==-1)- J6 y3 @4 Y+ n: @+ e
            {
9 D' u0 ^! b7 Z& d! [1 p                pre=cur;s.pop();
5 Q7 ]# ]' X7 G3 _, P, a                break;
7 @+ p% w1 f. W  R* d5 ^5 d! M             }* z- I; M; I( X
            else
9 I5 r# M' N# X! c7 U- C6 a             {
3 W: p4 {6 _0 M                pre=cur;6 s. Y2 [$ I. y/ W: S2 k; Y( r
               cur=p;
5 Y) s3 F' @. t5 {1 U             }* P+ }" R1 m* S: P( @% L

: K# V7 m% \. v4 r7 H* s% D          }8 I% ~" B( \- `$ v3 {' g
         while(!s.empty())2 c8 f: R, R+ ]2 `
         {
5 S$ P; p- D( b& W             cur=s.top();
8 k; C! v/ x. a6 E; h             p=GetAdjVex(cur,pre);0 l! a# a: m5 I1 d
            if(tag[p]==0); J8 D: F0 |8 f$ H, d, M$ N9 f
            {: q# L4 R8 a9 p: b! b& e
                  pre=cur;
0 g! D) o  j7 M                   cur=p;3 W" r& j$ H1 S, p1 p
                  break;# _, c5 |' S: K, p  U0 K
            }  i' K/ m. A  ~- |8 W8 |8 }
            else4 K5 z4 s% T. W
            {
, r# e4 v8 t) w0 O: |                   pre=s.top();2 y4 f% }$ p8 h, c. [2 j6 m3 c
                  s.pop();, ?4 d* Q& M" G' N% a( U/ D
            }. |* P4 o& L9 T

* ^) z) n8 d7 H          }
, _( L. B% y& y4 ?8 ]- Y. X1 I3 {' `5 i* H
      }8 C* l* E+ Z5 S% f! p& {6 a( H
}
; M& Q5 S9 L; ?' k$ q. ~/ N' p" W}8 v0 W) t. R0 @/ j6 E
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS(). {  z% u% Z' i+ o* E8 Q, ~
{
/ b# O8 ]; y( c; \; m for(int i=0; i<vexNum; i++)
      tag=0;
3 Q1 {1 |" E6 H$ [# u queue<int> q;$ K0 r' k" j, R  Z) V
int tmp,t;$ J5 h; A' l) e; v1 b6 @  Y
MultiAdjListNetworkArc<WeightType> *p;1 Y7 U% H" b6 w" J4 I, s2 M/ x
for(int i=0; i<vexNum; i++): W( P( g, a* r- j2 E: ^. m' W
{* u8 E4 E* R) I  I' T! B
      if(tag==0)
/ y0 D4 W$ k5 _$ B$ {       {: D7 l8 i* i. H' `
         tag=1;3 g% u% ~) g5 l4 Q8 Y& z" g+ u
         q.push(i);1 G7 a6 T' k' H# K
         cout<<setw(3)<<vexTable.data;7 G2 h$ W( [' q" j- m$ M1 L
      }$ ?/ Q6 o6 M. F, W6 q7 B8 |5 A
      while(!q.empty())
- F9 a( g: H2 W1 [# c       {
" ~$ B# X% z/ D/ {6 M          tmp=q.front();; o, I. h- v* s: v# Z% E4 I
         q.pop();
8 k' M0 A! t) X$ p' Y6 g          p=vexTable[tmp].firstarc;; `  N3 {  y: z; `; w( s9 i" ^
         while(p!=NULL)
! [7 H1 A# l! x7 I2 @          {
( T$ |1 X7 P% t             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);& O. e" k. l6 ?& @5 D
            if(tag[t]==0)
# D/ z8 g: ]- c/ y$ a( |* M             {& ]* Q. e: G! h% g- e; ^' z  P5 k
                  cout<<setw(3)<<vexTable[t].data;1 G% u# R* ^/ z8 q% E2 I5 E
                  tag[t]=1;5 v6 G+ e" L3 ~/ I, C7 k
                  q.push(t);( I! o+ i- Q8 Q( M6 c
            }
! G6 B7 \+ S5 m* E, ^2 E             p=NextArc(tmp,p);: i& H1 u- U; @/ ^5 E# }
         }" I0 s" ^/ i7 q6 W
      }, }8 m5 ?$ ]2 }! F* z! s' B
}" |& U' x$ N- Q9 S6 p
}- Z1 d- a/ G. J; o- l
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
! U3 ]6 M4 y9 I( W! m; V: [/ T( y{3 B" H* O6 I7 ~
MultiAdjListNetworkArc<WeightType> *p;
/ V) [0 i5 I/ P8 k0 w0 |3 C8 h cout << "无向图有" << vexNum << "个点，分别为:";( ~" h- e0 t  R
for (int i = 0; i < vexNum; i++)
* C2 G8 k% ~! Y! Y9 t* {       cout << vexTable.data << " ";
1 q- B: h$ k# s% V9 ^ cout << endl;' L- j+ l3 ~; j, g& _
cout << "无向图有" << arcNum << "条边"<<endl;
& ]- |  E+ u: G for (int i = 0; i < vexNum; i++)
' T$ h4 M0 O! Z {! E7 k5 Y( ?. ?! [
      cout<<"和" << vexTable.data << "有关的边:";& r4 l+ N$ b# I2 a! W
      p = vexTable.firstarc;
& N) M+ y# U1 v# [* b: F, o( \       while (p != NULL)
$ D9 v8 r& L. @: r6 V. W( f       {
/ u: c1 z/ |5 S: c- C5 b          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
0 P. C9 ~- b; V7 p! h          p=NextArc(i,p);/ B; j4 U$ m4 S3 A8 |* x7 j
      }& d8 I9 r7 {/ X4 H# s
      cout << endl;
0 R$ d4 ^. ~0 K }5 w+ j1 `& [& E1 p' O
}
" K0 I5 X7 o6 W+ W  N6 ^/ l+ t- D+ K; o. ~# G9 v/ k* n
9 z1 h3 x5 i3 J* X. Z. X3 D& k
邻接多重表与邻接表的对比
. M' L9 I* o+ t1 n( G, Z4 V- A0 v  X3 b0 a* W
邻接表链接
$ n/ o( \5 p/ m4 S+ J6 \/ f# x3 |2 ~在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
" ^$ @& U; h$ }0 {1 i- h" I在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。& h# E1 u# p. ]7 G
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
3 \  k8 v/ C1 n; b& T- b, T————————————————
7 B) S: |! i* v, Z2 `版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 T3 B# C) J' X% ?原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669584 ~$ o) @. u3 Q
- d! e3 o7 \  s- X$ G' T( l! r
6 l0 X8 n2 g- [* a
) _. m1 A3 \5 c% c

4 K; f# Q8 D, a; _————————————————
' i0 C" d0 ]8 }8 h1 n3 q- z& O. p1 ^版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。" V3 X, U9 Y0 c. L' |) L+ F1 E
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958; B1 E' [/ @. E5 v1 Q6 n- y
& J4 o+ ]( Z2 U/ G9 p3 {

$ L& x7 ^9 j4 r* y7 e% n6 g' p