查看: 1604|回复: 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' L4 Z/ Q. v$ L4 n1 H, n1 q
data域存储有关顶点的信息；
Y9 D0 X5 l6 U$ x1 n0 E$ \firstarc域是链接指针，指向第一条依附于该顶点的边。
U8 N) X1 m. z. S1 w5 U& 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;! H6 D5 {: `  i
for(int v=0; v<vexNum; v++)
! ~- y) d0 z$ f" X {4 ~5 d+ ]0 Q+ E# c% w
      if(tag[v]==0). e' L: f; F% ]: {% H  P5 }, O; m! Y
         DFS1(v);
1 o# Y! M& f3 {& A- e/ ` }$ l4 j4 T* a* J. N( l! V2 U* X
}" k$ m3 y% x0 d+ }2 `
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
, o$ t% O- j7 q7 D{- V. O% h; w% G) C5 s; L8 A3 P8 X2 p
stack<int> s;: p' {2 W' R" A, w# I* H
int tmp;' l# ^# [3 _. j8 e; n" |( s5 e
MultiAdjListNetworkArc<WeightType> *p,*q;% B3 Q8 p" q" d" x! Z" s( ^# p
for(int i=0; i<vexNum; i++)) Z" O) ?" X" o
      tag=0;
' d1 ^3 O' z% i; s) d) u for(int i=0; i<vexNum; i++)
" s& I# {- U  V! i+ H {
  L$ e0 h/ v0 Z0 a& @       tmp=i;
9 x* u/ }5 e- V: Y       while(tag[tmp]==0||!s.empty())
( b2 G& {/ D1 ]  R* ~! v       {
8 f9 z0 e, ]+ w2 L0 K          p=vexTable[tmp].firstarc;( Y- \/ S# v) d" v) T
         while(tag[tmp]==0)( s% z# }  {; p% I, a' }
         {' E& K4 q2 L9 t& f
            s.push(tmp);
/ }* m) @  a6 }4 d& ~8 J( Y3 d6 r) o             cout<<setw(3)<<vexTable[tmp].data;  s  O. {; }; m9 Z& M# m
            tag[tmp]=1;
% Z/ R/ A6 m5 [: p1 g" ^3 {             p=vexTable[tmp].firstarc;( c+ m& p8 r+ O4 R, E1 f
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for' y: J$ r. o1 b, o- p8 \+ [* Y- F
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);' T# z2 E- s: K  A* U" t4 M5 Y
            //cout<<" 1st    tmp="<<tmp<<endl;
* S& t" X* X1 w) y8 n9 J( g          }; ]$ e- G+ q+ @, f% A. Y
         if(!s.empty())8 K* c3 r5 A1 H1 k  i3 S9 \- @
         {
4 ?! b& {& A0 {4 C3 O             tmp=s.top();! S* Q0 K# {4 P
            s.pop();; F* a" g4 I2 r8 A
            q=vexTable[tmp].firstarc;1 q2 O( p+ h- \9 z1 n$ N
            int t=tmp;) @, m: q$ D3 K  o/ H' E) Z; f
            while(q&&tag[tmp]!=0)3 ]8 M; `" P% z& l) t; p
            {
+ g* e9 M9 M, z                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);* M- }( V  q9 V/ Y8 G
                  //cout<<" 2nd    tmp="<<tmp<<endl;; s0 C$ c) V$ E3 R% C) f
                  q=NextArc(t,q);
+ y$ ^5 `& M' M. Z2 k' h             }
* W7 D3 f5 g- T- B! ^: P* c             if(tag[tmp]==0)
$ d! n% P: P- r! |8 @( T                   s.push(t);
' N' V  V3 F3 f% s             ///1、对应上面连通分支只有1个点的情况$ @. s$ I8 [) p! {! ~7 J
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈' q2 [, G2 G8 G6 |% c) L1 v4 M
            ///tmp要么等于找到的第一个未访问节点，$ d: {8 B9 O* S6 \9 N# [
            ///要么等于与t相连最后一个点（已被访问过）
& S' x8 p# w: ~1 \             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
5 b, k' x7 T8 a% U) Z          }
: X. m$ _0 V4 L2 W7 I) s2 I       }; r8 j% T/ e1 C. }% k
}
) B9 m  e7 Z; s% x; T+ |% t}
9 z/ e8 L! @$ c# m//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1' F1 {, ]. B. |3 }" M8 X  m
template<class ElemType, class WeightType> int
9 ]$ g6 R  _. S- d1 c( A5 TMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)4 ], P- Z% D6 j  e  l
{- {4 M7 z% p2 H( d* {) ~
if(head==pre)
3 ~* Q  D0 W: ?( a: Q0 p, O9 n       return -1;
/ |1 ]4 x! k, l3 }: K; P2 X' |
7 R0 I( R+ A$ A/ t MultiAdjListNetworkArc<WeightType> *p;
$ B- F( w! F/ q/ a" V0 l% s p=vexTable[head].firstarc;1 F( @" q2 |% s
if(pre==-1&&p!=NULL)% X" W0 ]) k4 {! T
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
1 f( n% e) n- W, G8 P0 d5 B //pre!=-1&&p!=NULL
  _* v0 u- ^! D7 X) R. @ while(p!=NULL)
, T3 [; l4 K* t# ~& f. V {- X# n0 [4 ^+ s0 W0 K8 Y
      if(p->adjVex1==head && p->adjVex2!=pre)
) e. F9 E8 o) F& Z; T/ l6 g6 ~) M# C          p=p->nextarc1;
  g0 s. r6 r4 |! J( R' M1 d- A       else if(p->adjVex2==head && p->adjVex1!=pre)
! s, I  A4 \; e6 p( ]          p=p->nextarc2;
* N% u; a) r2 |+ i4 }       else if(p->adjVex1==head && p->adjVex2==pre)5 h  z) n6 q" U
      {
+ P& d1 q* W3 x* N+ Z$ Z- x7 T$ n1 }          p=p->nextarc1;( Z2 t5 ~& ]; g  O5 s% G# l: ^
         break;
( Y% Z, y9 W# d4 M; B4 S% I, c       }
3 Z9 R9 b1 M1 V) n% H$ {  [" w, a       else if(p->adjVex2==head && p->adjVex1==pre)6 T- i  G% q6 x; X) `% I
      {
' j- t7 U% }8 |. y          p=p->nextarc2;7 P! A, N/ \* O% B0 L% I9 x; v
         break;
: f. `% f+ H3 X+ u. D8 l       }  n  c( y2 n3 ]/ @5 G
}" @( [# T- ~9 |( \  c! \1 j
if(p!=NULL)8 N9 x5 I0 x+ d6 k
{
& u! H3 T% ]% @, a8 L6 `6 Y       return p->adjVex1==head?p->adjVex2:p->adjVex1;
' `- i. S9 }0 [. ?. g) g$ o }1 B% ?$ ^9 Z4 I  W
else
, n1 c8 l" H2 G- Q       return -1;
/ j) ~% g) N/ h$ @* h}
, ^  Z% Z8 {/ W4 Z2 j3 [9 `
$ m) ~  b, Q: y3 c# r* F& |1 o% X9 s9 K
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()6 Q* J# d1 I- u2 y' X
{7 ~: h" L* N. o! J; A
stack<int> s;
  u* ~3 ]) R7 O- e5 c4 `9 A int p,cur,pre;
' h: e& D# r4 \" m8 @6 K! s! y" S) a //MultiAdjListNetworkArc<WeightType> *p,*q;0 @5 R  e( w8 G
for(int i=0; i<vexNum; i++) tag=0;//初始化
+ X# D( |5 [' o6 w) m* Q) @3 P' T' i+ n. R: D8 k1 \
for(int i=0; i<vexNum; i++)
7 j7 y4 x5 g5 A: h8 z: E; a {
8 r  c. A) D9 p       cur=i;pre=-1;
2 j6 w3 a( @0 m. M: S0 O       while(tag[cur]==0||!s.empty())7 R3 j- c1 m& r, o  x9 s0 u0 Y% z/ |
      {, m$ M$ W; j# O& G$ e% U. r. c' Z
         while(tag[cur]==0)
- H/ Y$ r8 s* }. b# x6 V* u6 Q! k; z2 X          {
) N! ?- F2 b) t+ _) c; |             cout<<vexTable[cur].data<<"  ";- v* u, p- L8 o- i( W# s
            s.push(cur);
, ~, G* E/ a! }. ?6 w0 s" O- Y             tag[cur]=1;3 e9 ^" l& S6 D
            //初次访问，标记入栈. h* h  Y! d5 ^- w* A5 R1 f1 @
5 ^. \: t3 K) U, B
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
/ P; B3 x2 e2 z$ j: O             if(p==-1)
5 r7 b7 h. d  s. h             {* B1 |- O9 [/ W: R& e
               pre=cur;s.pop();6 Y' f3 [0 |9 H3 x  V' \! i
               break;
6 Y# D. v4 _+ ^/ N             }
2 c% B5 g# a. _/ U( X  }6 f% m! n9 R             else0 ?, u0 `/ Z, r: [" o
            {. w: e' w) U7 _( o0 K% A9 D
               pre=cur;
( M5 b! `, u0 w: |7 m  z                cur=p;
0 F2 a. I  H6 F8 y4 [             }
+ A1 X7 G: e7 n- X+ t! Y' o( e# `6 C, ~* Z: W; ^7 T2 [& W
         }5 x7 E4 ^& ~+ G
         while(!s.empty())2 K; T. w" X8 C9 F! v1 n. u; T* [
         {& t- z! @8 X: a  q
            cur=s.top();
: e/ q# e) k6 {1 Q( U* x  A             p=GetAdjVex(cur,pre);
: w6 d' C' G8 r, k( W4 ?/ z& {3 w             if(tag[p]==0)
) G/ |( W5 e* @& z, M             {4 f4 @) t2 d- |
                  pre=cur;
& b8 W- l& c+ Q+ Z4 F                   cur=p;
$ U* [6 }' k. A- x( h3 [9 p                   break;
6 J4 v! }9 u# [5 M& ?- b/ ]             }* r9 w/ T  [2 A8 k# Q# t5 ^  }, \
            else
- r# [' x) Y1 h" O2 J, ^             {: b" |' d0 p- `  @8 G: e$ N
                  pre=s.top();9 ]& ~% r+ J4 q
                  s.pop();
7 ~$ c& A* r8 @             }/ x  H5 H: b2 c, U3 c- \
% Q- y$ c5 d- a# d* |6 w3 f
         }
% Q  k& t6 E/ H( U# ?: ^8 G/ s, T2 ~, ^5 h( @4 \
      }  [1 ?3 c. F0 A4 e
}
, l$ s. n9 r: D9 P}3 t. ~$ y8 |/ r9 g" x: j. \
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
+ u- C/ y: A( e( [6 i- R{0 x3 C. R8 c) K/ d
for(int i=0; i<vexNum; i++)  b4 J( T+ ~1 `' \- q! W( p- g
      tag=0;0 q! r# j5 U1 |6 e* N. j7 r
queue<int> q;3 E! ~+ }/ s, {1 j
int tmp,t;
) J1 a8 y" F3 c8 u5 e9 W4 Q! \ MultiAdjListNetworkArc<WeightType> *p;  X5 |8 w: A2 v/ v
for(int i=0; i<vexNum; i++)0 b; `8 K5 n: H1 `: y. o
{
2 D8 A! D  w# _" K; g       if(tag==0)
  I4 w$ {5 B4 z& z2 V+ `: `       {
% z* n# ^: v* ^8 ~9 ^0 l! g          tag=1;
  @& t& i& ]; Q; c3 y          q.push(i);0 i$ I5 r: U9 W
         cout<<setw(3)<<vexTable.data;- w- S8 C3 c8 U, e
      }
  a' ]. D! B3 r( F; M+ h       while(!q.empty()); Q0 K" P% z6 r2 |# @
      {  B8 H( m/ c/ [8 z: F
         tmp=q.front();" p- O7 [9 ^1 i  _* o5 Y4 |- N
         q.pop();
0 u& T& J- t2 x6 \+ c% E* V          p=vexTable[tmp].firstarc;7 G* S- o! m3 v
         while(p!=NULL)9 e6 \0 X5 `" E
         {+ X+ o  t7 G6 u; l, C& J* u
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);" ^3 E9 E, r, U+ _
            if(tag[t]==0)
9 c/ V" h& E/ L+ R! Y             {/ Z9 D3 T; V7 ?
                  cout<<setw(3)<<vexTable[t].data;: Z! E$ ~6 q5 `) L
                  tag[t]=1;! y/ X& e) v( M
                  q.push(t);
: U. y/ ?# l' ?6 t9 r: D' w* I& s             }
2 Y  X- D# {, B* O7 U9 k. C             p=NextArc(tmp,p);
" @7 o. ~2 k/ P          }
8 O" x/ b$ t% m  D# N       }
) y" P) L- U, }6 G. R }4 W( k0 t! J  ]. X* @
}
7 I# t5 y$ s- B: U& ]6 o4 Gtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
# [+ M' w2 ?0 s) |{4 R" f4 F; Y2 E; b" d7 \/ x
MultiAdjListNetworkArc<WeightType> *p;) z6 Y0 m0 z5 M8 s2 V2 `
cout << "无向图有" << vexNum << "个点，分别为:";
+ `: ]" r( O) e9 w; ^- W: e for (int i = 0; i < vexNum; i++)
( g8 P& U$ w+ O0 u       cout << vexTable.data << " ";
0 l4 Z- z3 P( ]# i& L$ R' k: t cout << endl;; p. C3 s9 m7 c% D8 G+ t
cout << "无向图有" << arcNum << "条边"<<endl;
& J+ m! O# p% [8 j$ f* U( r, G3 F for (int i = 0; i < vexNum; i++)' E, R: {) Y+ D* K- u- W# D$ O
{
  q& w6 p5 }5 t# s0 }6 ^       cout<<"和" << vexTable.data << "有关的边:";
' _- q% ~3 o% x! V- `3 w       p = vexTable.firstarc;: h0 U; O8 V- X$ v' t6 p2 M
      while (p != NULL)
( J9 a3 N6 T& y# Q! h8 S' F       {; X$ z  Y1 p( m% o- o* ?
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
# U9 m$ ^6 H$ y; S4 k( j  ?# a          p=NextArc(i,p);
' q  A6 ^2 e. ~' j8 c: e1 y       }
6 ^1 H8 h2 u8 h       cout << endl;: @$ U7 Y) a# I9 j- O& u
}
6 l5 j! j8 }8 l}
( }9 o5 [* i4 v6 G* P, z$ }- r. A

0 l" N' L! T! M8 F邻接多重表与邻接表的对比: E5 ~, _  E9 p3 J
; B' m* F- X/ W( A% `/ n6 f
邻接表链接  `. l+ R! Q4 ^" _) b6 O
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。0 I) v. `3 n* E/ R4 ]
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
+ ^" S+ U5 |5 y7 o/ M4 e为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。0 _: K8 x" G/ \' y
————————————————
. y% p- |& A# ]版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
3 @6 |# U5 T" u* o: }原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
; n% L7 x7 r, U5 E! \  {( v
% Z& O: ^6 y  Q- v( I6 M0 N$ P" {% Z6 ^, j3 C9 @- ~8 g5 g. R
, r9 r3 S) W$ w' j
# B$ q1 x; n$ z2 R9 Z/ w9 y8 {
————————————————0 N! P3 L* A, r. R; {$ V
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。% a6 l* v; \1 t/ k8 u
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669587 _1 @1 \8 T8 w9 `

$ \9 t3 T- B" i8 a% y- I+ s: ^
# M$ {) ]6 N2 g) G7 C7 s. c6 D