查看: 1657|回复: 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 d$ h. `1 `. t+ b. A+ s3 rdata域存储有关顶点的信息；2 d+ D/ @9 y0 D, k6 I6 }, D% k" ~* R& r
firstarc域是链接指针，指向第一条依附于该顶点的边。
8 P) \ r% @/ a4 e3 H$ i, k所有的顶点结点组成一个顺序表。

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;. T$ w$ Y- {$ ?, B  N: J
for(int v=0; v<vexNum; v++), C  \/ J1 A+ z% W- z$ P
{
% u& W! m& S4 E       if(tag[v]==0)
1 d: P+ `! K3 C7 Q          DFS1(v);3 @( [7 |+ u3 h" c
}1 g- M, c, l* N5 S
}8 z& N: \; a. w& j
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()5 u( q( |! E7 w# `
{
; N) b: x& m6 k3 i  G stack<int> s;
8 q, C$ j) w1 H" h% m int tmp;/ Z. F- E4 z0 n+ x6 P
MultiAdjListNetworkArc<WeightType> *p,*q;
4 v( V$ [( W; p7 c7 B for(int i=0; i<vexNum; i++)
, ?; N2 O4 X8 ?- }2 x8 s% P9 A       tag=0;
; l$ g; z# O5 S8 |% \ for(int i=0; i<vexNum; i++)
9 S- I2 U% P; p2 p7 ~8 L% |0 D. H {
0 ^! y- e7 S; b1 Q       tmp=i;
# X: K9 Z/ X( ~. t; y  ?       while(tag[tmp]==0||!s.empty())
0 C3 L/ `% Z* j/ x' ^7 k2 Y       {
" T* r+ x* r9 f          p=vexTable[tmp].firstarc;
2 ^3 T. ~  B  c, R- F0 y5 p: @          while(tag[tmp]==0)% `! m/ p; ^4 I+ q' ?9 q6 J6 Z
         {
0 b( Q) R9 z: l. I% N/ U* N  r             s.push(tmp);
& Q5 n" G6 X& y5 M7 M             cout<<setw(3)<<vexTable[tmp].data;
+ n+ O/ o! N" C             tag[tmp]=1;
0 O; U+ ?) P( g             p=vexTable[tmp].firstarc;8 o# t) C! D$ K7 w% z
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for$ W( b& A; a) Q* f" v, [
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
, c: e1 _" i' g* h$ V& s0 J/ L             //cout<<" 1st    tmp="<<tmp<<endl;
/ A% p: s% A. ~& t3 |          }2 [: T$ ]( D. S
         if(!s.empty())9 [) T' L, K" A  ~" x
         {& Y4 M6 K2 p$ g1 `: f
            tmp=s.top();
& b% Z0 j$ [. \4 j. H9 C( Q             s.pop();
3 `5 b$ Q$ y, f             q=vexTable[tmp].firstarc;
$ Z1 a0 a/ F; ~! [1 K; d             int t=tmp;4 Y' m& v% J  b0 [
            while(q&&tag[tmp]!=0). N6 n9 g5 n- h) z" W% H/ I
            {  c% q8 w% |9 }& j0 k
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
+ x3 H+ f0 X& g                   //cout<<" 2nd    tmp="<<tmp<<endl;
' T* M" e% G8 j$ v  n5 s                   q=NextArc(t,q);, x& ?+ Z8 ]2 C
            }
. u* x9 A+ m* W             if(tag[tmp]==0)
; P' H) ~) ?: W) I2 E9 d9 P( r( f                   s.push(t);% {/ Q1 y) T: d
            ///1、对应上面连通分支只有1个点的情况  e+ h' N3 a: ]) f; P. r% x
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈5 X- k3 D8 ]. g- g* D: v8 [
            ///tmp要么等于找到的第一个未访问节点，( {% _5 e" x  ]: M8 |: t
            ///要么等于与t相连最后一个点（已被访问过）7 D8 ^; _/ }% F4 K0 E
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点* k# Y: f& h+ r+ K7 S6 C8 h
         }. T- B9 c# O6 y) ~& ~, q% H
      }& @( M/ i' K$ }" J: e; A5 n4 }
}
% u3 V, d0 }8 H! q2 ~3 k' r2 U0 {6 R}0 t2 _% Z* D0 c) y
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1% d+ M  T3 `- _" g4 ]! }6 s
template<class ElemType, class WeightType> int8 m7 o( _! s7 Q7 r9 |: c
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
2 G  {. I. ]& v  y{
* [& h7 y7 b% z if(head==pre)
& F  f5 n+ y3 t7 p       return -1;3 P* _& b! [! c7 K! ?9 |, v

. c0 o& C( J' M# f* X; z' `& i MultiAdjListNetworkArc<WeightType> *p;
; W/ A. t+ M3 y. ^# U2 H p=vexTable[head].firstarc;! q9 w+ k( x# }3 t& [
if(pre==-1&&p!=NULL)
( b/ `) O( q/ ?: k/ u; X2 [; ]  K5 r       return p->adjVex1==head?p->adjVex2:p->adjVex1;5 E" T# u5 y4 r! v  V7 s: c& ^" i
//pre!=-1&&p!=NULL
# u! s/ }8 Q5 G2 s/ Y2 G2 @ while(p!=NULL)
" Z( ]# M! \5 n* r. a {
+ ?7 |3 K; i1 P1 S       if(p->adjVex1==head && p->adjVex2!=pre)2 L: j, B( f* J
         p=p->nextarc1;9 p$ S! Z8 h, y- M0 m* a/ k* s
      else if(p->adjVex2==head && p->adjVex1!=pre)
6 I. m  k8 l$ W1 k) Z0 E& G          p=p->nextarc2;
5 ?" L& ]4 [" V9 F+ b5 w       else if(p->adjVex1==head && p->adjVex2==pre), @, G  p' `6 D" n% w
      {# t+ H: S: U1 R) S- F
         p=p->nextarc1;
* u& C8 w4 w6 \# d. a          break;
5 C" X5 [1 }( g       }
2 ]/ y" f- t- d. d- u  ?+ f       else if(p->adjVex2==head && p->adjVex1==pre)' H) a- k7 ?1 ]" |9 ?9 ]# j
      {
* ?9 }, ]+ D: U* ]+ ~          p=p->nextarc2;
/ ~$ q* j( j3 S6 I8 i- j& w4 a          break;$ U+ L4 r3 Y2 }* n
      }) O0 [6 O; `7 m* t6 m# t2 [
}# c2 T( P+ F: }  A- J
if(p!=NULL)& P1 i, v0 h. S2 d
{0 w% ^0 H' `6 m9 X6 Y& m" M
      return p->adjVex1==head?p->adjVex2:p->adjVex1;1 N3 D6 u5 x( C7 j2 ^# e
}* }+ H9 v8 V; `' @1 V9 t1 t/ }
else$ T& Z2 D7 _. }
      return -1;2 A/ h: _* D- `
}9 l; U* K4 _$ U" L

  p+ A! C2 ~3 c" d0 A: Z$ S5 t) q9 c0 `: L
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
- f% q- H$ _2 r. g+ h5 j. B" s& G{
  H* H" P4 ^8 O stack<int> s;
( e, e+ C* y% Z int p,cur,pre;
* f1 z" P7 f7 a& ~  H: P% U5 U //MultiAdjListNetworkArc<WeightType> *p,*q;
# Z# F7 W5 x  w. h5 P1 j2 M for(int i=0; i<vexNum; i++) tag=0;//初始化( s1 S" P& H/ B8 _- v9 T2 _
7 K$ J* b9 L8 f  [/ m3 [, K7 o
for(int i=0; i<vexNum; i++)" v% S1 h0 Y6 |! z  S
{
+ f9 [  D7 [( F       cur=i;pre=-1;
% ]7 k2 ~% i% o- @  z# O/ ^       while(tag[cur]==0||!s.empty()), t5 r( u! Y3 s, Z
      {- P1 K2 A+ n' d( P0 G
         while(tag[cur]==0)
9 f6 K' E, s: Y  o& D          {5 C* b1 m/ E6 J. W! N2 @
            cout<<vexTable[cur].data<<"  ";
) }+ b. S) U: e! B             s.push(cur);
  f, z" K% A5 h+ [( k5 b8 [             tag[cur]=1;
( f" K7 `3 K, m" E4 C  q5 e             //初次访问，标记入栈
2 z$ n3 X: k# b. C6 ^! d$ o, w9 a) q6 y3 _3 a
            p=GetAdjVex(cur,pre);//p是cur的连通顶点' @8 M/ ?4 [0 i/ p! y- X: v
            if(p==-1)
7 h* i+ K% _# V" n1 P( d) \6 Y; c" c             {* V: o+ _5 n8 r0 b' v% k$ ^) h: E
               pre=cur;s.pop();7 D5 i4 s0 Q5 d5 C
               break;/ E- @, q. h5 B1 x) X& T
            }# j3 w( I$ t' n# W- w' T
            else
5 v8 K6 U5 ~% s% F4 t; a# a4 K             {# Y7 v$ A1 j, N! K
               pre=cur;
5 D5 a1 }* I" M" r0 d9 L+ I                cur=p;
- L7 @  i: i3 D+ Y( q) I             }
- j* e3 [5 \1 K$ C/ M2 A, J4 w( T6 e( e2 T
         }
( y7 c. {$ _+ \- ?; T: _2 b0 R          while(!s.empty())6 v' J! Q3 F; R3 ]
         {
4 z0 Z; s# ]5 F" _             cur=s.top();
2 o+ U4 w' ]/ {. h$ Q/ \+ C             p=GetAdjVex(cur,pre);% m4 X# w  I. D' I4 P7 h
            if(tag[p]==0)
& T9 m0 C/ U. S% g- o             {
& }8 r: C" E8 h, x4 D                   pre=cur;
+ b# V' H3 d1 R5 s! i/ u                   cur=p;
5 I" c6 g8 V3 d+ {                   break;8 p/ v* p5 Z# c9 @6 X" T" F
            }, x; ^) ~6 G! |* R& x9 r1 E/ N
            else$ f7 o# j8 s: A# _, |
            {0 |) O! B2 A$ I: G
                  pre=s.top();
2 N4 G( b* J  \                   s.pop();
/ ?+ v( i2 p; g8 j             }+ H0 Q1 y1 R/ T

# m2 T1 N; B# _          }
+ T; J* B" o" R4 R; g% g7 e& a  D9 F. K0 q  A5 d0 l
      }
' ?- z( M$ ^8 g" |" i& j/ d }( a+ f8 m0 C% ]$ A' X
}: m* C% V; U+ T- ]3 C( _+ ^3 v* \( A& @
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()/ X- K/ b  E- e, J0 T4 v; R
{. Z) Q2 u1 G. D# }
for(int i=0; i<vexNum; i++)0 w- x! d; B6 [
      tag=0;. Z/ J. Z8 B0 v/ A9 @9 v# ]
queue<int> q;
7 j# f5 |$ Q! R( T( F* r int tmp,t;
; |: @5 x% f+ O4 T1 O+ D( P7 s MultiAdjListNetworkArc<WeightType> *p;5 O4 n5 K6 x% j+ H& r
for(int i=0; i<vexNum; i++)0 L, |/ y4 c: Q0 b3 l
{: x! i4 s4 k' t0 K- E3 t5 C
      if(tag==0)
1 e+ y- @$ T3 E! W: U; X7 B( t  s6 P       {+ g( z" i! Q' d* I4 @6 d
         tag=1;8 j0 f: r0 O" v/ v9 B# A
         q.push(i);
5 j# ], ?# ?" j! n! e          cout<<setw(3)<<vexTable.data;8 M  T/ ?: ^6 z3 o6 R" h6 L, I
      }7 \4 x# i3 j( ?, E
      while(!q.empty())* \! p, d/ v+ N) V4 C* @2 M$ w/ `
      {
! D1 h; `7 V" _/ y; P          tmp=q.front();
# B3 V- ~. u( x/ l( x; p2 {          q.pop();9 `" ~6 D% b( _/ f8 Y8 x
         p=vexTable[tmp].firstarc;
( K" {  F# w% Z! i, E" U" F          while(p!=NULL)5 S* \/ A1 L, v2 G
         {
- t& ]8 A/ m& O- d$ W             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);& U8 A$ e( k5 U6 R9 [4 q+ {
            if(tag[t]==0)0 P% D4 e# d, w. F
            {
# y+ d! \! y+ {9 y( C: U$ Q                   cout<<setw(3)<<vexTable[t].data;
5 E, I" s0 p5 u0 K- ?                   tag[t]=1;8 L+ T( O: ~- ~3 c3 X( {
                  q.push(t);
; H& C6 c* g5 I5 J. n8 ^             }
' G' F+ d; I6 [( d0 Z             p=NextArc(tmp,p);$ a6 b" P# N8 x9 c
         }
  g/ x* v, q/ \, k6 ]+ Q4 b       }
  p* K2 d7 p; m6 Y4 Q/ ~' E" e }
9 R( p6 p0 M0 C: K8 R8 }$ |}$ ^% y: y7 B$ U3 _$ _3 D
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
& y5 c9 n, H" k1 z4 ?/ b{! i7 ~2 S6 N2 }, [6 y8 t+ W
MultiAdjListNetworkArc<WeightType> *p;
  x- a' S  W5 \6 S- N( K9 y. y cout << "无向图有" << vexNum << "个点，分别为:";0 X4 Z  h% O  r% N
for (int i = 0; i < vexNum; i++)
  r8 C3 _2 |5 F; K% \2 z       cout << vexTable.data << " ";
9 Y: a2 ]2 ]* q! i( m; E cout << endl;+ F% h3 \" ]! a3 G
cout << "无向图有" << arcNum << "条边"<<endl;
1 k/ `* u+ v2 W3 O  M2 `% n for (int i = 0; i < vexNum; i++)8 v7 h6 T+ E2 u) O, G7 K
{
: d+ n+ ]- Y0 p! w7 T       cout<<"和" << vexTable.data << "有关的边:";
# p5 G6 p7 y7 m' L# `       p = vexTable.firstarc;4 _. Q$ Q- V/ v7 Z+ ]5 |6 P$ t
      while (p != NULL): c; g' L! M6 d# S
      {# [7 x5 ^$ \9 B7 x- \# |# L1 W! B
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
" b5 Q! N8 J! v0 q) M! R          p=NextArc(i,p);
5 e  F7 C1 s" T( _2 J+ @       }
1 h& B6 p  T# a4 a       cout << endl;8 P( m$ o  r, e- ~/ ~- u' C( e& H
}
  O% r2 b& E8 M7 s7 F7 _}/ F7 X, u9 y6 N

/ }: X# U( Z" ?; Y7 E. [4 s6 l' T6 r2 P: i
邻接多重表与邻接表的对比
. {; l. y1 A1 f7 ^+ D' H4 L/ N! Z& @+ U
邻接表链接
6 E4 x, B7 I/ m+ H' x7 R在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
7 E+ J7 A7 w! X% [在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
# _% y7 j3 \" l% C. M7 H/ s为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
6 @% f2 C1 N; G2 [) c7 J————————————————
0 ^. j; C- y# E$ Z7 I/ r; ^7 C版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* D3 f/ C: j' B( R原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958' b5 i1 i/ D: j  N3 }

& K$ q1 W4 J/ [5 Z- E! X6 y4 g+ Z+ c8 e! ]9 c6 S1 O, h

" C  l1 i, C- |: O  f
! i1 w- Z7 u( j" s2 ^5 ?————————————————
) A: j9 t5 v" ?/ F* N9 Y7 A6 v% y版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 B# C. k2 r% B9 p7 x" _9 y原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
& P8 I9 c/ g, G& u5 K" T# O* W! q7 u

% x1 B+ N. X9 i/ }6 o0 S