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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
3 d' a: n3 H& kdata域存储有关顶点的信息；
3 J5 r' X; ]5 G- O3 A8 pfirstarc域是链接指针，指向第一条依附于该顶点的边。& L2 ^' p% c/ I4 V3 j k! _ v
所有的顶点结点组成一个顺序表。

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;7 R) s, d& {: B, I2 R6 K
for(int v=0; v<vexNum; v++)+ p% h" y1 [$ G* B7 t7 Q& D8 c
{
3 ?9 D$ R" Y) }! _- a       if(tag[v]==0)" |0 d6 F  o8 X% E
         DFS1(v);$ v: [: S) h2 V' a
}
! n. _) i# o# @}7 h4 R. S9 e8 m' K
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
) x3 x1 _2 }6 S& n{
7 f6 X0 c4 U* u. P/ G) W9 J stack<int> s;
2 p! C) j1 g* a- Q! G3 B int tmp;+ y) I* O/ D4 u0 \
MultiAdjListNetworkArc<WeightType> *p,*q;
, B7 r0 r7 [& c7 |6 @ for(int i=0; i<vexNum; i++)" N* w# j1 B; T4 }1 M! {
      tag=0;
0 o/ h. z6 z( N! G for(int i=0; i<vexNum; i++)
, K7 `/ L# [) P( l% J {7 \5 R8 M$ O! V- k7 {2 f
      tmp=i;6 Z' U8 S0 u* r: ^( j& V* n
      while(tag[tmp]==0||!s.empty())" G1 @- s( y$ F0 ?  G, g
      {
0 i7 H9 G+ g" k7 I          p=vexTable[tmp].firstarc;- K, g6 o% O) `; {
         while(tag[tmp]==0)
" I3 k* w; J' c. Q+ @3 r( p          {6 n" g+ P8 [1 o, V8 W+ N$ i
            s.push(tmp);, @7 u6 }3 E; w( `6 E
            cout<<setw(3)<<vexTable[tmp].data;7 f1 }* s& z, e' \7 i5 a0 B0 {! p
            tag[tmp]=1;
$ b' P# ?* `5 p& G: t9 Q             p=vexTable[tmp].firstarc;
! @2 p/ h$ P. Y4 a+ F) V             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for! Y$ E; ^. d+ j, {% q4 R
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);& V& h1 g/ \( E* A
            //cout<<" 1st    tmp="<<tmp<<endl;8 ^5 g! u. L0 `3 P
         }
9 z1 X6 {8 B4 o) a          if(!s.empty())
6 M- p& e! o1 g/ M          {3 F* w$ u. V; R6 [% M8 E
            tmp=s.top();7 ^/ R' s" _4 x8 w' h6 I. t
            s.pop();
( I! m& w. d: e! g0 D% s             q=vexTable[tmp].firstarc;8 }/ A: y5 q. g( w9 |/ J! B1 n% @; x
            int t=tmp;, l0 F1 ?+ a3 S
            while(q&&tag[tmp]!=0)
( v# P+ o0 Y& L( P  ^: Q) v: C% J             {
; Q* b8 R" I  {; H* l0 D                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);6 ?% x! W1 T# i. r, e1 [8 H6 H
                  //cout<<" 2nd    tmp="<<tmp<<endl;7 y5 Z' T) e1 }$ ~. v* C6 a7 o
                  q=NextArc(t,q);
' ^3 R! E: F* p" k5 D             }: w" H% Z% v  _2 ?4 p, M- \& r
            if(tag[tmp]==0)
: A8 ~- X4 B' i& o0 ]' J' `# ^" N                   s.push(t);
( d; x7 ]4 c9 O0 `, n$ ^             ///1、对应上面连通分支只有1个点的情况
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
1 g5 r* l$ l) n% w& X$ ?             ///tmp要么等于找到的第一个未访问节点，( V$ P6 _* `  W
            ///要么等于与t相连最后一个点（已被访问过）
. w% j6 n$ _; ^$ E             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
6 j$ w. l1 \3 |2 B( X( p/ I          }, Q- s* C% n* w2 d& P, e0 s
      }
9 K3 f" m8 t6 X2 ?# A3 m/ ~ }
3 z( d  R) p  e* k' _* w: U2 Z}
9 g/ |" u2 s. B1 z6 s; R" S9 e; i//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1" L9 D. C5 x* ?0 t4 W. v% Q
template<class ElemType, class WeightType> int
6 C: |6 B: {" ?MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
# @! ?3 j; i# u4 `& s0 |( k{" @" k, ]' f4 s+ W& z& q
if(head==pre)) ~* Y4 J* @" L% i& N0 {
      return -1;
# M. J. ~: e. J; M/ H' A, ~% g. W9 D+ ~" ]
MultiAdjListNetworkArc<WeightType> *p;( O9 F  R( W) ?
p=vexTable[head].firstarc;, k6 U8 m& ^9 h$ h" U
if(pre==-1&&p!=NULL); B/ k! w* I( f+ c0 x1 ?
      return p->adjVex1==head?p->adjVex2:p->adjVex1;/ P9 ~6 q) Q9 D1 b- w% D; p
//pre!=-1&&p!=NULL. d6 `5 D' i. [1 b
while(p!=NULL)
) @; n( o" g' W/ L& Z3 s {
4 k6 V/ x& a6 d1 n5 ?- C0 P       if(p->adjVex1==head && p->adjVex2!=pre)
5 L: Y9 `6 A. q/ u# Y4 N4 f          p=p->nextarc1;3 `: q: a9 u; r/ i& C
      else if(p->adjVex2==head && p->adjVex1!=pre)
, l2 L, ?' q: z  y& o0 D3 ?/ B          p=p->nextarc2;3 O" A2 n4 w1 t
      else if(p->adjVex1==head && p->adjVex2==pre)
6 h* P& E2 r! V; e       {4 W9 [7 t/ e% G5 O1 I% f
         p=p->nextarc1;
$ V( g$ _- o5 E          break;3 z# @" _4 L9 Z9 p( ]" }* [. K7 t& D
      }
5 l' O# w/ \& V1 p' x8 w       else if(p->adjVex2==head && p->adjVex1==pre)
% n1 {, I( W# p9 U, S       {
8 u+ ~# n. v8 ~4 H5 \" A$ {          p=p->nextarc2;- W: \# f: e# _+ {3 V# v
         break;
; K+ \: m8 g3 {       }
5 v$ ]" b9 C1 \: \2 W: b }! ~2 E* n: i& F. [
if(p!=NULL)/ @" a* [6 H) J; }5 A. e( i) e
{/ e( f! R/ X$ K
      return p->adjVex1==head?p->adjVex2:p->adjVex1;7 ]& `1 `# k% D% i' J
}
3 G' a" l8 X7 X( x# ^# A else$ Z1 D" L6 N) [. d; x- z
      return -1;8 m- c& \& M' F7 \
}
  Z+ o/ n" F' {' z$ A$ h
4 D, |+ y3 a4 L' V, d# o" c) P+ @1 I8 f
4 }  i& D( W! N* htemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()- x, f! N' ~, x- K0 f
{4 [/ k9 \9 l$ C6 z: G* r
stack<int> s;
4 W; T' q. }; W) \9 J) {# ?4 f  [ int p,cur,pre;9 M  t' ^& w% t' M
//MultiAdjListNetworkArc<WeightType> *p,*q;
' m5 J# C% {! f0 x0 A for(int i=0; i<vexNum; i++) tag=0;//初始化7 l/ _  B( Y: z2 i8 p

3 [. s4 Y- F1 A for(int i=0; i<vexNum; i++)9 V7 c& U- @$ N$ O
{5 {6 h& K8 D1 f5 R8 Z& u2 _
      cur=i;pre=-1;/ G* |* M4 R* o; O
      while(tag[cur]==0||!s.empty())2 b. P  Q: J% t$ g1 }
      {% w% U, {% X6 W* a
         while(tag[cur]==0)9 i0 y" n  h( |
         {
$ ]+ e8 k: q, W# T* m! j             cout<<vexTable[cur].data<<"  ";
0 t. d6 J) W! M8 H; Y2 |6 k             s.push(cur);6 \& d4 {9 {8 F3 N+ @6 Q9 J
            tag[cur]=1;
/ V3 F" u! O6 M/ i8 Y2 b7 W. G8 E             //初次访问，标记入栈
: y" [# Z) g% j% l2 C4 V' |! g' m5 |, J- m3 K, i% `, g
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
9 i& I& @0 B- w( d; G             if(p==-1), P, x3 O( y. v7 w/ d2 |
            {$ ~3 D* l. ?' w7 B8 i9 }0 q
               pre=cur;s.pop();, A. F8 `; v7 @( O
               break;" E' p5 j) h3 ?/ i( f
            }6 P) @7 p2 |+ F3 O
            else, ~  W: R% r: @9 R1 _6 u# W& `  \
            {
1 k3 p4 [. b" {" ~! {. e                pre=cur;% `0 O: F- b' ^' h9 l) Y
               cur=p;/ U3 o) z/ E% ]7 p! ^. S* E
            }
' e; K  m* I6 a0 y6 c
5 F8 i! w3 K& W: e, x( U          }
* r# w9 Y, H" r9 `2 D5 H. Z% P0 z          while(!s.empty())
% |) j8 L7 B$ j' H1 v          {
9 r9 V8 [) {, S" ?3 F) K             cur=s.top();, G# @) ?; C$ F; a+ Y* T
            p=GetAdjVex(cur,pre);
* b' T+ Q4 k# n" T* P. C             if(tag[p]==0)
0 `1 J2 x2 e. O1 i2 {             {& a6 e* @* e; Y. W" B5 V, i
                  pre=cur;
. u+ K& z% c: D2 K                   cur=p;, ^  _, z3 a9 y: `! |% P' h
                  break;
1 z% s7 B- i1 `6 P& ]8 h             }
: i5 n  w9 e# j' {- d9 y             else
, c! C3 o' {# [5 c2 ?2 v             {
0 Q# x# ~) w4 I- g, `                   pre=s.top();
# @9 W' F0 g% o2 }                   s.pop();
) ?5 ~" W' [4 A  ?' A             }0 j9 G2 k- ]& @0 Z! c

7 H8 c5 z8 B7 ~/ F8 Q4 O          }
6 O' j, F7 Z0 z" \, Z1 l/ d4 H/ F5 e- ~& r8 F& ^3 J
      }
( ~; e  x7 I- J* e8 B7 x }8 |4 {& x- Z' N7 W) e6 U2 ~
}
' x( g/ P! p: I' t3 l! j2 ftemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()  k: D$ T, R8 m. s% m
{( M/ L( {5 X/ S  r
for(int i=0; i<vexNum; i++)% l8 ^! b* Y9 t& O. w, c
      tag=0;( I) m  h0 ]2 Z. h
queue<int> q;7 l! \& ^5 M3 P& I- Q- `- l) w/ P0 [
int tmp,t;! j7 K1 X& U2 `
MultiAdjListNetworkArc<WeightType> *p;
6 [, R9 o+ {' W9 Q, O! c for(int i=0; i<vexNum; i++)" F5 W- |9 {/ ^0 `" J% l
{
3 J4 S5 O2 p& K* y, P& w" u' X       if(tag==0)
9 C! W7 n6 F9 S- q! ]7 v       {
+ F2 T  k# o1 B' h7 K8 i; ?. c          tag=1;
9 S- w, i: W! O! Q9 l          q.push(i);
3 o9 b: g4 U8 {9 ~          cout<<setw(3)<<vexTable.data;7 h) Q  X/ ~' k; J% F) }0 U5 I. M1 Y
      }
+ @; r5 s, G- u/ g) s2 x3 |) C' f' u       while(!q.empty())
/ ]" X% C7 V! E5 d       {
  m' J+ j/ N2 b' c  t6 A          tmp=q.front();$ e0 K0 z/ N$ R
         q.pop();
* {6 i, }9 T6 F. m          p=vexTable[tmp].firstarc;
$ T6 T/ h3 L! ^+ j# X          while(p!=NULL)$ y9 L6 g- y/ G3 I
         {4 I" ^: o7 {1 l( _% W9 l
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);% E, e# h1 c$ F' J6 G7 z/ D
            if(tag[t]==0)# L8 Y8 l8 k4 e( `8 d
            {
0 O! Q, e7 j- y+ h  j+ D                   cout<<setw(3)<<vexTable[t].data;$ Y! i' g+ P6 \! L; ?2 z- f
                  tag[t]=1;
7 q1 x3 O- f+ ?2 C2 u                   q.push(t);
, J$ a5 Z- [/ `; \; U             }
. d% [- X) R; m2 u             p=NextArc(tmp,p);' x4 N) v& H' z7 G1 d
         }& {8 F" m$ v( ~. m
      }
' T7 i( d& [" N% B: K6 l }
3 F) w3 s) n1 E. I  O1 R# W5 c}
! D% J! e7 {) B! b1 [template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
1 y) F8 J5 R+ z) E& @$ X! w' E7 ^{* @1 B( v, u7 j) o
MultiAdjListNetworkArc<WeightType> *p;
9 B$ B6 v0 a5 t/ u- j cout << "无向图有" << vexNum << "个点，分别为:";
# z9 G1 Y) k$ @* k4 a9 U for (int i = 0; i < vexNum; i++); {5 b: b9 H8 b$ w( d* f8 Z3 G% O
      cout << vexTable.data << " ";. B9 \  b/ F1 t1 B) g' U
cout << endl;
5 O8 z2 i0 J9 L  k cout << "无向图有" << arcNum << "条边"<<endl;
; t7 y$ w( a' c, E8 k; ~3 ? for (int i = 0; i < vexNum; i++)
4 B" Y# C# x9 t* I4 m$ S {6 M4 s* N7 O. D( [3 Z# l/ {& f
      cout<<"和" << vexTable.data << "有关的边:";. J3 |8 q/ Y! d
      p = vexTable.firstarc;
7 j: g+ W# m! V1 D       while (p != NULL)
. H) d% S$ u2 K+ J5 }8 C       {
& I2 A) ?% H; n: i, Y& g          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";0 A+ z4 k" t! J' Z7 G) B: s% j
         p=NextArc(i,p);2 j+ A' g$ z, |
      }4 P* E5 G, n# Y
      cout << endl;
4 }' r4 n0 A9 W& j9 A7 n! e1 G }9 _3 z3 k$ g! ?
}. ], O$ a! e8 h( B2 w

6 T4 c* O6 z1 }6 O' }' M+ z, ~! Q0 Z: q$ l9 I, {
邻接多重表与邻接表的对比
4 s4 g8 t2 v3 d) O4 i) Z( h0 x4 `
/ h7 X0 @. I0 ^5 x邻接表链接$ z+ d1 v+ X7 q) U
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
& b4 m( c6 O) }& w& N# _& `, a$ @在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
. |+ o: y: K2 e/ a7 f6 d! M% }为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
3 g! h; M# b5 t————————————————
5 A/ }$ p" K0 {5 W3 j; r- L版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。2 R0 m6 @2 E: {# q# W; k/ k0 i
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669583 e* `4 Y7 G8 V$ C3 p5 @

) D) h/ u# x" ~8 W9 V6 u0 D- s0 N) T

6 f& x) v% L& C+ g% s4 o: w1 S2 T- v
————————————————
1 D2 }  ?, c/ n9 K版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。$ F% Z) n+ I2 Y" |, d9 O
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
& T6 B  q3 c# E! Q7 p, }; D0 f1 R- O
6 O; ~* S- l" q0 F