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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
) e; i. C. d$ n ~% tdata域存储有关顶点的信息；
) R! u6 X9 }& |! ]6 U/ b2 ]firstarc域是链接指针，指向第一条依附于该顶点的边。0 v4 }( N+ Q6 O: m! p 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;
* u3 w6 s' H* l- b: O3 F for(int v=0; v<vexNum; v++)' J$ P% D" O' p
{
. ~& _, T. a9 z# C& h       if(tag[v]==0)' l' N4 _9 d4 Z  j) K0 z) p3 W9 |; s
         DFS1(v);
# {5 s! ^7 B$ _5 C( i& j }
7 V8 q2 {8 U* B}
1 @( o7 j7 M5 h  ]template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()6 l% D  u) o8 [6 J, @2 ?5 I# ~
{
3 J) C2 X% m* _ stack<int> s;4 ^) p% i3 O6 d9 w2 s" D" W3 V4 k
int tmp;
. k4 C/ w3 b& g2 U5 o! w MultiAdjListNetworkArc<WeightType> *p,*q;0 J5 v7 d& ^5 D
for(int i=0; i<vexNum; i++)
2 J! ~% Z! i9 s  o' X2 M       tag=0;: ~1 [  i/ c) G4 N2 c
for(int i=0; i<vexNum; i++)9 U* J. \3 ?1 P0 h$ ~+ g
{
" p* J7 @# `4 T* Y, y2 ~+ R3 P3 ?       tmp=i;7 V9 x" r* f0 r3 ^
      while(tag[tmp]==0||!s.empty())9 B' h, ~1 G% }6 R: a. l
      {; K) ^' @* b1 ?& m3 }  R  S
         p=vexTable[tmp].firstarc;
' d+ w/ B( h* n3 c! b) i          while(tag[tmp]==0)
0 c' X' b2 Y( Z, d7 U          {# j5 X( v% I( F; H' d
            s.push(tmp);
: s, W) k* S( _. T             cout<<setw(3)<<vexTable[tmp].data;( A/ }0 f" a! q" W
            tag[tmp]=1;
2 c5 U: V, ]- t3 X1 w6 }, Z             p=vexTable[tmp].firstarc;
7 B; o5 }; R/ U' y# M; j8 |/ f8 u             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for! w  k, N$ K0 P
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
, r" R4 C# s4 s3 V$ @             //cout<<" 1st    tmp="<<tmp<<endl;$ E! [* b4 v' [' B5 a
         }
# L4 O- A1 ]! r+ s  [3 W1 H) G          if(!s.empty())& Z- p0 `" z3 L( Y/ S
         {
  H) K+ J1 v( \7 U             tmp=s.top();
0 O2 W+ ]  ]4 e' D             s.pop();
5 B+ n: a5 R0 R  {2 e+ u1 V7 k             q=vexTable[tmp].firstarc;: L# b) [! _+ ^! ?4 i: z5 f$ {
            int t=tmp;! G7 r: S, s* g& X
            while(q&&tag[tmp]!=0)
: y1 w; X$ V& w$ N1 |( P6 K6 }4 B             {2 Y1 d2 x7 ?9 y3 w3 D7 @3 M; s
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
$ v; b. M0 m9 k. [                   //cout<<" 2nd    tmp="<<tmp<<endl;
% Z, W! |  o0 G9 R9 r: k                   q=NextArc(t,q);2 y4 {; ?1 \# P. V
            }
8 H" j4 `) J1 j" @/ F             if(tag[tmp]==0)
. N4 h9 G* {, S0 N. ]3 ^0 S/ x3 Z                   s.push(t);
: k0 |" Y8 v5 ?# e( z' K# Y+ d+ c             ///1、对应上面连通分支只有1个点的情况  K2 n# a- ^6 ]- t3 n/ R. @
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈+ T* j) J3 H/ {+ X
            ///tmp要么等于找到的第一个未访问节点，
! T4 l  ?8 ]: ?* t             ///要么等于与t相连最后一个点（已被访问过）9 @. X7 s' j9 i+ M  L$ W+ Q0 h
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
3 g6 J% P8 D$ E: X9 Z          }( r0 ?$ S" x/ X! L8 G3 s
      }
' l. s* u- D/ M7 E }
0 V% Q7 E  O& O/ ~! @}
, }2 |. X; N3 R8 J, [0 ?1 O$ l//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1+ D/ n' l6 X' L3 ]3 P1 a
template<class ElemType, class WeightType> int3 m0 z  V) D2 K; _- O  b0 c, z
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
) r5 g2 V/ Y+ q" q' I3 c{& p. t3 G5 f2 q( e, Y
if(head==pre)7 X4 L1 F/ I* B
      return -1;
) k5 Y" h8 \" _8 }3 t# u. L8 w! Q. [* u& Y/ I9 W+ U
MultiAdjListNetworkArc<WeightType> *p;
2 f7 A# }" {. _, r1 C( q6 E$ h p=vexTable[head].firstarc;
* ?; x% W$ {, S8 _  u7 W6 [* g: k if(pre==-1&&p!=NULL), f* O; ]7 P2 U
      return p->adjVex1==head?p->adjVex2:p->adjVex1;- L3 K( H6 h* |8 O  ]
//pre!=-1&&p!=NULL. [$ m7 ~* ]4 b6 r
while(p!=NULL)  `' G: r  W% y! Q+ D- B
{
& H( ^9 y2 [) B1 P: `8 y9 `       if(p->adjVex1==head && p->adjVex2!=pre). N+ T. H5 o; i  P2 z
         p=p->nextarc1;, `  \0 k$ `: K+ O% m
      else if(p->adjVex2==head && p->adjVex1!=pre)  k" i  @# U/ `) p, o
         p=p->nextarc2;
- n# Y' ?5 Z% ^9 A$ |6 U+ Y& ?       else if(p->adjVex1==head && p->adjVex2==pre)
( u: v. Y2 h* R" k6 I0 @  `6 D) j       {
( D3 R4 d5 ^. a8 D  _          p=p->nextarc1;
# h8 R1 r+ K8 Q6 R' @/ U          break;4 h1 Z' S1 y' ~2 @
      }
/ {# b: s# _; V* n       else if(p->adjVex2==head && p->adjVex1==pre)
7 P, q4 V1 ?1 L+ ~" f+ n       {
1 j) D& H; V# y) H          p=p->nextarc2;
  p% }8 D0 k) W1 G3 Z          break;
/ d: ^6 w, ?+ J0 ?       }4 \) T/ T! g# @! h( o
}
9 I+ R' K4 D/ W& g& H1 p. G5 e3 n if(p!=NULL)
: Y/ \' S$ x( ^  @ {
2 p% r7 D) p& N1 V$ b       return p->adjVex1==head?p->adjVex2:p->adjVex1;3 S5 B: I( J% X  b9 n* C# |3 x
}
0 w3 U9 `* e9 n else
" k  J5 C" l  f       return -1;3 U5 T5 v6 f, {0 D$ N. ~
}
! b& ?8 y4 {' q* _0 d) r, C* E+ P) q' N7 ?  y
' p1 O7 u! @3 \) M: ?: ^
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
4 j% r: d! o0 D) R# `  Y{7 `& b; f# T2 }5 `8 f3 Z( j" Y7 k" p
stack<int> s;
1 V& S" g$ {; G! Q0 T int p,cur,pre;
, W5 z/ b8 p9 [& c //MultiAdjListNetworkArc<WeightType> *p,*q;
  s4 j* G' y- |  A) M* a$ { for(int i=0; i<vexNum; i++) tag=0;//初始化
2 S7 `' Z8 C: Z
0 ^, l$ O9 H9 w" M for(int i=0; i<vexNum; i++)2 g( o% A# l7 r' v+ R
{3 X% `. m5 }. y# Z8 d9 \2 k
      cur=i;pre=-1;
5 b9 k4 s3 [  M* E6 q4 z2 o) s       while(tag[cur]==0||!s.empty())
* l. K( }* p* x* `6 J& b# V- \       {% d6 `& ^5 a7 A; H% ]
         while(tag[cur]==0)
3 b8 t3 o4 L; P8 U. W! c. W6 r          {
3 C. k3 O! B% m             cout<<vexTable[cur].data<<"  ";
! n# b2 ?5 N, w; m. Z0 G* C             s.push(cur);) b% E& Y# W; x6 C) p
            tag[cur]=1;
1 z( {4 q9 H# _: k             //初次访问，标记入栈8 ^/ z4 m0 F1 i! ~) g* o
1 ^% n/ n* I& C" p
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
* b, Y1 V: z1 Q3 Y             if(p==-1)0 B$ e  l) o( \9 A
            {5 {8 p9 }+ l- @+ M& g3 j
               pre=cur;s.pop();
9 J  Z9 _: Y: d0 t7 P                break;
  `7 w; ^& Z& F8 V3 ]' x             }
6 B* S: j. \" P             else# `/ {' n4 [7 w+ b
            {0 \- u- x: \2 X0 Y: v
               pre=cur;
( u+ I1 z* a9 m  l$ j                cur=p;
$ I+ R) i% O9 U             }
% w3 t( r7 s# \5 p8 I) E" n2 N8 h3 t6 c
         }+ J; F& E* R/ e4 z
         while(!s.empty())
) }4 g( M6 z& e1 G  c          {
. A# s& i* ^3 M             cur=s.top();* G8 ]7 f8 ?  r# b1 @/ @  Q. `1 ?
            p=GetAdjVex(cur,pre);! b% c" D* P6 u1 O/ g
            if(tag[p]==0), w4 b; U5 K+ {3 n# p
            {
4 W* i: b) R, Q0 S2 F+ ~                   pre=cur;# }; m. _9 z% P6 l1 Y
                  cur=p;
! U* I: f: O$ p/ C5 B( D                   break;$ b9 v; ~0 [8 g3 t% C
            }7 D; Z3 J+ b; r8 _4 J: D
            else/ @# G" T) s; }+ j2 Q" r3 g( g. f
            {# v2 S$ I- `/ ]$ L5 u* w
                  pre=s.top();
: d- y0 [% K7 u. p* y                   s.pop();: _0 }- a" t% x
            }1 e8 e. y: S3 ?7 E

& U) \$ C4 t! ~% i. Q. \          }+ W* a& ~3 z7 _; J3 D" x' U

4 j" O& E& ]- S8 C" U       }
$ S: K; J+ e; S5 C% d  ~6 a }
" \; w0 z/ }6 u, I/ j}) P! y1 P0 {) Q0 I0 O8 L9 X
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()4 L; R- V0 L7 m4 u7 @7 M: c" X
{
! Q9 b; H* W8 q( Z/ p7 z, y* T for(int i=0; i<vexNum; i++)" O# j5 m6 z/ Z
      tag=0;
6 y& H: ^% g3 V queue<int> q;
; ?$ H3 y, ]+ K. j# V int tmp,t;) D$ @# S, H9 C# H
MultiAdjListNetworkArc<WeightType> *p;
# A1 j3 j8 v* V for(int i=0; i<vexNum; i++)/ ]8 l" o2 I8 L  d9 X3 d  ?
{
! e9 f1 r" t# |" x  d2 S/ I       if(tag==0)
$ D2 P1 G) A8 q6 ~  h4 P       {
2 m( I  D& N* s3 m& q  a% k) K          tag=1;
! q4 ~$ f4 S8 p7 Q          q.push(i);
8 Q( \  [2 s: q. g0 @5 N2 Z  {3 `          cout<<setw(3)<<vexTable.data;
3 j3 r* m3 i/ J$ ~. X       }/ ?4 W  q" E4 D8 D
      while(!q.empty())
0 D4 Y# I6 a/ j8 B# A       {
6 H* b5 |7 R7 _# ?& K9 W          tmp=q.front();2 E$ m- a4 W, W  ]4 u, X0 ?9 m  |
         q.pop();
: I/ M1 n: X4 R1 U7 B          p=vexTable[tmp].firstarc;
6 Y! f9 d) U5 E7 h9 o9 ]          while(p!=NULL)
: M7 a1 |7 G5 i# N          {  I$ I% _( _5 P4 w+ ^( j2 K, q
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);8 n" G0 H& [# t1 L% d  A# s
            if(tag[t]==0)% v3 P8 F/ y7 Y
            {
+ ^  Z  t; ~3 X# y' e7 _                   cout<<setw(3)<<vexTable[t].data;0 L+ e5 `  k  d' h) E
                  tag[t]=1;
+ {; s% Q) i3 D* U' q$ S3 U                   q.push(t);# W% x$ B5 B# V! }
            }/ G0 U( Q/ W  M
            p=NextArc(tmp,p);' G# _  z3 d- B8 B! z; \5 n0 L; _. C
         }: v6 x7 e4 L5 }! V6 m. ^$ D
      }
4 f: B0 \8 r; k6 ] }2 S5 W7 a0 k; r. k4 [$ }
}
6 D; l7 Y5 [# s/ Ntemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()7 T% v9 \5 J, N% T
{
" [- \1 [7 t0 Z4 k MultiAdjListNetworkArc<WeightType> *p;
# Y# o0 Z+ z! G2 T, b; ]4 u3 M) U cout << "无向图有" << vexNum << "个点，分别为:";! E* y; K, d8 |9 {! w
for (int i = 0; i < vexNum; i++)9 W! d% c/ z4 T2 s
      cout << vexTable.data << " ";
7 t, [! ~6 l4 o cout << endl;
7 x$ V9 x- A2 h+ }2 g cout << "无向图有" << arcNum << "条边"<<endl;( p  M; P/ z+ C4 B  s  Q' r
for (int i = 0; i < vexNum; i++)
& g" N1 u, u; r/ D/ `7 \" c2 n/ n8 Y$ Q {' z; C' O- Q4 {7 Y9 b1 _
      cout<<"和" << vexTable.data << "有关的边:";8 P% O4 U6 c. T3 F, r8 F; K/ p& s2 e
      p = vexTable.firstarc;
( e5 F- `6 d8 H2 f% P3 t5 {1 a       while (p != NULL)
# b$ V2 a: ]. F       {( W& O+ T1 q1 V1 O$ {
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";9 G! u" I. j  b8 g6 T( C1 M
         p=NextArc(i,p);$ Z) b& j2 {2 ~, t
      }1 [* r0 H* g/ P* K6 n
      cout << endl;- o& I! Y4 }. j3 l2 f2 L/ V7 d. o
}
, O6 s& t/ t3 f5 }}9 B4 i& L. P- ~* N. N; w$ ~+ Q
" p3 l7 T( ~9 m% B$ P. K3 D
; E% v& g4 n/ S. G+ p
邻接多重表与邻接表的对比
( }$ d/ X" A$ g; d) `
; t% p% p2 q) E) |6 C) }% V邻接表链接9 n, Q& s# I4 m5 L
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。3 e. H* L4 e# o
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。" A: J8 `: F6 h1 Q0 v" E- K$ A3 i
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。; B* U4 T2 G" f) `& N' c
————————————————5 G$ g9 }7 F8 T
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% w- W7 X. w) ~# ?原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
& o. |! \! S/ a0 B& j2 W7 w+ Y7 N

4 L2 }8 _8 i5 U+ f$ d8 c2 Z1 \7 W2 ^
  p4 p1 E1 k0 t1 ]- a2 a
————————————————: H5 N- p: V+ ]$ R
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。. l8 i! R8 S1 @4 W) g8 U/ U+ e
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* \1 e9 z, M3 h$ g$ @- K" U$ q" X
, P: J6 f/ s. ~7 @/ m$ x  w3 k' ?+ c2 V( U* U1 Y  C7 i