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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
6 t+ }& W' Z) S9 a2 t% A) D5 Hdata域存储有关顶点的信息；
# K3 P* N8 l, x7 I/ S+ }+ b* Vfirstarc域是链接指针，指向第一条依附于该顶点的边。
8 v q8 t% s2 k5 U u- \/ m所有的顶点结点组成一个顺序表。

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;0 V& m( S& r: a# A. y* j- a
for(int v=0; v<vexNum; v++)) a: e+ G& L$ {6 E$ j4 |" ^
{7 g9 m- Y( r3 @4 k" b3 X  W- p
      if(tag[v]==0)/ R3 `* _5 }4 G7 j' B1 f- T% k  M+ a
         DFS1(v);& b$ g# r/ P/ G* k( h' Z/ P
}7 w. n& t7 J4 v, c! {
}
/ w! V/ W) Y/ @' Q! P/ B: xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
& X. V$ X1 y  v4 ?7 V; |{
7 T3 Q' [2 x! K stack<int> s;
* x$ \3 p: X6 g* ] int tmp;
. R4 K! {& B1 G0 `" _" e2 v% d MultiAdjListNetworkArc<WeightType> *p,*q;
& y( [3 o/ B/ t. b3 L# B for(int i=0; i<vexNum; i++)
. Q0 J& R' w2 S5 O) U2 ?6 Q       tag=0;
+ H$ p6 I+ s  _" D. c for(int i=0; i<vexNum; i++)
$ x  N0 O+ [- w: [- C# L6 U {5 P9 x' m' x! O% W! k
      tmp=i;$ R  r0 o3 ?1 k3 X
      while(tag[tmp]==0||!s.empty())1 E3 R' @7 s! H/ U, p
      {
; k  B: f  p; e9 C& v* t# Q* x          p=vexTable[tmp].firstarc;
$ r8 m5 h& Q9 T2 v          while(tag[tmp]==0)4 \' g; _6 q. s3 b$ Y' r3 {
         {
, m( o+ l& ]+ |) x( B2 h             s.push(tmp);) M0 _9 K4 y$ s" g# O
            cout<<setw(3)<<vexTable[tmp].data;* B  h. D, J% N  \8 t
            tag[tmp]=1;
2 {" k6 \) W- a( H- a+ C( d7 t             p=vexTable[tmp].firstarc;" P( r# H* T8 y% a4 D! U: I
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for6 V8 v  }. P' g
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);3 \* [; a- B# ]  ]) Z/ \% I: r9 a
            //cout<<" 1st    tmp="<<tmp<<endl;
8 _; [0 x# k+ {. i& y4 P          }
" F' e1 ]  T! Z; k% G+ P          if(!s.empty())
2 `" R% i4 U& \4 P  ~. D( w' D          {
/ f" a# B8 w: ^( G( p             tmp=s.top();; l5 Q- y7 t( _8 y
            s.pop();
4 d( p# q1 u  N4 s             q=vexTable[tmp].firstarc;
% M" y% ~; S7 z% F; H$ X             int t=tmp;3 j8 r2 ~  o2 I$ ?6 D( y" q( ?  P
            while(q&&tag[tmp]!=0)
  k9 ~: J3 T+ @9 }$ W             {; |% m" D$ ?& b" _( k5 w
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
4 T. S0 w* K2 A                   //cout<<" 2nd    tmp="<<tmp<<endl;
' p  r& Q7 h, f8 X: Y0 C1 Q. Y9 \                   q=NextArc(t,q);* a# s; [) F9 @+ i9 l; `
            }
  g( _6 u) w* _             if(tag[tmp]==0)" S, n# i2 S' C4 b  Z0 {5 f' E
                  s.push(t);
  t  T) e8 q& S# w( I             ///1、对应上面连通分支只有1个点的情况/ M& d  G; k2 _1 l5 {( r, T
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
1 {; q5 W# d+ D' s: c) n             ///tmp要么等于找到的第一个未访问节点，
6 o4 n& L# j$ w6 z* S( t% ~             ///要么等于与t相连最后一个点（已被访问过）
+ S) Z( `8 \. R% c             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点. k6 x1 d/ y# d: d4 {7 F7 o
         }
% m" n5 K  l" k& J  p: t/ N       }, S! r9 O- c$ Q* v0 `' {
}
* p9 N; U& h) ~" Z$ V. N9 K2 S) W7 l' l}5 @- v9 E7 F# d5 Y! M
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
2 }& d5 _. i: q  r1 E9 g& u8 W4 m: _template<class ElemType, class WeightType> int+ H" f! ]+ G/ ]& y& E- n
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)8 i7 N$ d7 G0 n$ b  Z) I0 f
{
( a. O5 Q4 a# W2 d+ K* @: c if(head==pre)- {) I9 p: ^3 N6 d/ `- D9 y9 W
      return -1;  x7 J% p6 t' H; N

8 D1 I8 f) V' j# e MultiAdjListNetworkArc<WeightType> *p;9 U9 p( B1 ~7 d+ E0 m
p=vexTable[head].firstarc;; ]+ r, v( R' a  {
if(pre==-1&&p!=NULL)+ i( E0 h6 e+ l5 J4 e
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
$ S& q- o; H1 `; { //pre!=-1&&p!=NULL' U: X9 D5 V  A9 V- H: D' b
while(p!=NULL)
9 J6 U3 v5 Z- ]/ i, O% e/ ^ {
3 L9 G- [; R- }+ ^$ p       if(p->adjVex1==head && p->adjVex2!=pre)
1 K2 n& h/ F7 d0 C, J          p=p->nextarc1;
+ x4 w7 W6 D8 V$ r$ H       else if(p->adjVex2==head && p->adjVex1!=pre)
" c: y( n' F0 I5 A! o8 z% h' X          p=p->nextarc2;
; e0 R5 W: ^, I  s       else if(p->adjVex1==head && p->adjVex2==pre)
% L- b# e+ T/ C/ I4 {/ H       {
. d6 R) P6 {$ a7 ?          p=p->nextarc1;& ~& q9 _+ E, [
         break;. M* @* ^1 N1 N6 ~- ~: U
      }
" h/ ?$ s- G- r6 }: g       else if(p->adjVex2==head && p->adjVex1==pre)
3 ]/ N& u/ U8 i% E1 H$ d4 I       {
! N9 }1 M& q1 X0 L. ?1 y          p=p->nextarc2;
7 `1 A# w' A. ~9 w8 X          break;
# ^& D5 H8 E5 ~& n, y0 e, H       }
* f( M3 B0 ~' J7 w/ u* F }
2 |: i) f+ N. E  H! h9 o2 U if(p!=NULL)* g9 K2 D: b. ^& R) d
{! m# t4 f% S) G1 P3 v. e3 j4 J' ~) Z
      return p->adjVex1==head?p->adjVex2:p->adjVex1;1 V, r$ F9 B( E/ a) z
}( s( \! ?" }+ M; a9 T2 b+ s8 E
else
* Q- H3 l! l: _. H# x8 a6 }- E' d       return -1;, l1 A( D/ \( k" K& _: W$ C
}4 h0 Q; J8 Q: |! q3 g

: R9 e# }( C+ l, N% D5 l! [
8 j% Z* `5 y( B% _# b( ^, Qtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()9 C8 I8 M% l) c
{5 g3 s# Y/ ]* t$ `. c) o
stack<int> s;. G6 p  F8 i/ `' n# f
int p,cur,pre;) g- U! [7 L, s2 h/ M: r) g9 ?
//MultiAdjListNetworkArc<WeightType> *p,*q;
2 l9 b; S  V( M for(int i=0; i<vexNum; i++) tag=0;//初始化( o) D  U# u$ S3 T9 O( |
2 [0 l$ D3 U9 @. H* y
for(int i=0; i<vexNum; i++)
8 v, p# z6 w5 x+ N# K {
  Q1 k8 Q5 y7 s7 n3 C( D. m5 G       cur=i;pre=-1;
# z. D  E. H# Y! w9 `. P, x       while(tag[cur]==0||!s.empty())
6 G: W, K8 Y: p+ P       {" L* t+ R3 I: k1 \% V
         while(tag[cur]==0)
         {8 W4 c: N! l1 v: N5 ]& _: Q5 v$ P; c, s
            cout<<vexTable[cur].data<<"  ";7 L+ U5 ~8 G3 f+ _3 m
            s.push(cur);
, E, \; }0 A, v* e" W             tag[cur]=1;
( N) x7 n( N0 p0 z+ t8 n3 I( E             //初次访问，标记入栈1 X0 j6 X8 d: O) T$ u& y
- d3 {9 z; n. p, ]6 _
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
/ a1 F  R0 V+ W; i* f: e) T             if(p==-1)
! O4 O- G$ k; d* w             {
6 g% I: Z5 X9 F2 `# R                pre=cur;s.pop();1 \8 [+ p0 I& M: \
               break;
/ N* {1 X) M* z9 w4 X/ a             }
; j$ c+ `8 W, z$ s4 U- U             else
7 @4 I( L9 c9 r" h             {
9 o3 ]- Z' O0 m! Z4 i6 n                pre=cur;/ P* n9 J; z: d" N
               cur=p;9 h4 N( ^  D* ~5 q" F9 f
            }+ G+ S5 [- W4 E' t! k# G

  c% y) w) \1 o7 O' `3 S0 C          }) p, J; F/ }" d, A* F8 }4 u' f
         while(!s.empty())1 l; ?8 Y5 a) Q0 W' B& X; T9 O
         {. x* u* T: Q6 o
            cur=s.top();
$ ]6 ^5 D8 K. s             p=GetAdjVex(cur,pre);
& r3 U# t& e8 D0 w  k% S3 }             if(tag[p]==0)+ M, |: X# k6 D4 j& N1 o
            {4 v% R/ a; d, b3 {2 f# x
                  pre=cur;
$ q* n5 D9 w3 S1 {                   cur=p;
. T* c3 l' ?9 h) V: a* ^8 o                   break;
. f9 p! F7 n% h- V, ]0 i             }( c7 G# q* Q3 {! E( O% n" p6 G( z
            else
! ?/ B  V; f) f. G  ^: f7 e; p# `             {
5 s6 R0 m: _- m" V                   pre=s.top();: O% K+ A, y$ ?) ^8 W7 t
                  s.pop();% a; |6 v1 f5 m, Q. g
            }
; N8 ?) W( q' u' m. E4 i$ y4 g0 d' m/ `1 z- w1 o- R7 C
         }) M" h2 I( M: X& k( e

2 I, T' r% q4 k       }
0 K2 O0 Z& I1 c' O2 R0 \ }
+ a* o$ F+ ]) t5 K6 m, c4 U4 Q! V}
. ^- \5 k+ H2 M# t* g: gtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
% n6 m* @$ J  w" n9 Y. m3 o{( ~$ C9 N$ Y4 i3 P& e# `+ D+ U1 F
for(int i=0; i<vexNum; i++)3 j/ n5 |0 Q  m; O' ~
      tag=0;" F: ~% n2 c! l4 A! r
queue<int> q;  p0 _  P/ ]3 N; e. Q$ q5 Z& m
int tmp,t;
, Y  ^7 H( {, X) ~' ~1 A8 o$ ], O MultiAdjListNetworkArc<WeightType> *p;7 P' J# T; r3 x
for(int i=0; i<vexNum; i++)
8 N* A$ @. }9 f, g, x; o3 `- u {7 I& [# _( S) d0 _, A
      if(tag==0)
  r+ X: t. @+ J! E( ~/ y       {$ Z! m- Q0 X/ O+ W; \" N: Q
         tag=1;
- g4 R- k* C; l7 P2 t          q.push(i);
6 O5 R' d4 Y4 U6 U          cout<<setw(3)<<vexTable.data;
- u) y' ~- v% y, r- G       }
% J% H3 e" i3 P# |       while(!q.empty())- K2 d$ C  m6 Q5 Y# s! A
      {0 G  Z% S  W, E9 v. Q8 j
         tmp=q.front();# F& d7 M) q# |8 W! S0 }& z3 Z: |7 Q
         q.pop();9 I0 t0 N  x# n% q, l* C7 d
         p=vexTable[tmp].firstarc;
  r( }0 D" L4 g  d. |+ Q/ y' v9 G          while(p!=NULL)
% x$ N: W% x8 ?  e6 N/ y4 ]          {
" p  ]5 m3 B, K3 E! ]- Y" Y             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
$ c& ]7 |6 Y5 P5 t: r             if(tag[t]==0)
! h, V% n1 U, [3 O' y* U9 ?8 H! h             {9 C0 [. x* |4 a1 @% l  \
                  cout<<setw(3)<<vexTable[t].data;" Z: z; }$ E$ [* A. G  Y, \) w
                  tag[t]=1;
: X- b2 i" }8 G4 N0 k9 F                   q.push(t);% w, @6 ?7 A5 ?9 `
            }3 w0 s2 [: X6 D8 j' @% b: @
            p=NextArc(tmp,p);
, l2 h' D" M/ R, L          }
! C( t2 T* y' G  H+ M, e       }
% [& k" C* K  j8 E+ I }
; t. M7 a3 Z$ F}4 e5 b' ?( F2 x, {* x4 d+ N, r! X
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()$ ]# a0 Q; A5 a) C5 \# Z
{: k8 k* W4 q% L0 v
MultiAdjListNetworkArc<WeightType> *p;2 X$ F  C2 H' I1 R1 i2 u2 G- T8 i
cout << "无向图有" << vexNum << "个点，分别为:";
% N) b& W; _* w; r6 Y for (int i = 0; i < vexNum; i++)- B- b; B, l1 a. a
      cout << vexTable.data << " ";
& P% ~  m% e: n+ W cout << endl;
1 E1 {7 j, g7 z: o cout << "无向图有" << arcNum << "条边"<<endl;
; m0 f+ l  o& B, B* A% a for (int i = 0; i < vexNum; i++)! l/ g/ ^& O# a" u/ ^6 y
{
2 z( M4 l* j& N- J       cout<<"和" << vexTable.data << "有关的边:";
. c2 K' `6 U, z! I9 P0 N       p = vexTable.firstarc;2 B3 |+ y" Q" n  e
      while (p != NULL)4 B+ V* H" B5 g" i7 z1 s
      {
3 x+ e* I7 H7 N* s/ y' W6 `          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";- N9 R; \! {! V) R
         p=NextArc(i,p);
* [( G. u3 k( a4 G       }
. I3 f" h! O2 P' C1 d       cout << endl;
; ?: c, F9 Q; f% J% F1 ~ }9 X: L; ]! v# S$ R
}
# B; h7 I' Z' W  a
4 l1 V( r/ @# V- b6 N: ]. t4 H
% [0 T+ x, E) e邻接多重表与邻接表的对比
/ G! d" `+ G  d
. _( y; P9 I( W2 ~邻接表链接
9 q& A# y' M! D/ C在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
/ ^9 W3 [/ Q$ x( O0 L在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。" G. p6 e2 d  R% M  f' F3 a# U
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
- _$ l) k# G- \  ]) W————————————————4 I" M/ O- A% o
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# E" a* E% v0 L3 N% w# X2 ^原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
, `+ V# r5 {/ j# F! b/ I% u2 e. j7 D; Y
% T2 k) p, z; E6 l

$ b; ^0 i% G2 N$ p% t' K
  F% [& J: h  I+ l: O————————————————
2 ]0 f) D$ m, o5 X版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。- M' Q% y+ r8 v  a
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958) `$ [' {, G9 N) C! J( S
5 J/ e# f2 r8 x+ s4 y

( p1 Z5 M% T* \: j5 r9 y