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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：' G" N. n/ ^# s4 I E
data域存储有关顶点的信息；4 z' j+ [' Y4 P2 U
firstarc域是链接指针，指向第一条依附于该顶点的边。
, v: J, L$ {# |/ 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;
. Q+ n/ z4 E* h# f( X7 w( `3 _& h for(int v=0; v<vexNum; v++)0 U! y% e! r2 M
{; F4 M- ?0 l* J. @( m
      if(tag[v]==0)1 M, o' D0 @1 _3 |
         DFS1(v);7 p3 u- y. P6 [) Q
}% r% d) d/ W. g4 i# H
}; W  H# z2 w, F4 X! M
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()" ]! n6 }& J' w  M
{
/ B5 N& l0 K6 N! r stack<int> s;
" \, K# E, s: j int tmp;
1 ^0 {- o: P! F$ P! H% [, m MultiAdjListNetworkArc<WeightType> *p,*q;
4 r  L( U: M' h4 u2 F for(int i=0; i<vexNum; i++)/ r8 ?# P2 e) |, r
      tag=0;' [* k# v* J' d/ ~8 H+ L
for(int i=0; i<vexNum; i++)' R, E- H( j6 e/ C4 ^, [
{8 H  n5 x* p# M2 B
      tmp=i;; y7 o0 _: C# C7 T5 D
      while(tag[tmp]==0||!s.empty())
2 k  ~. G$ ~2 a7 K! b       {
4 e- D+ U. ^$ I+ P, F& q! U          p=vexTable[tmp].firstarc;/ k  f- A7 Q+ q$ J! R" j8 [' w
         while(tag[tmp]==0)' i- `9 C! p' {0 w5 C
         {3 m1 `2 V+ L3 J- c  C  V
            s.push(tmp);
' ]: f5 L! o9 `: @# ~             cout<<setw(3)<<vexTable[tmp].data;- L+ y2 o1 L) `7 i/ L, T
            tag[tmp]=1;
, y, K$ `) o8 s' F2 N             p=vexTable[tmp].firstarc;& @6 }6 v( Y* x: D6 s  q
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for/ k) H# C2 x8 t+ J$ k
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 P( g! a! ?9 I2 H             //cout<<" 1st    tmp="<<tmp<<endl;0 @. z( t* z9 b
         }, c7 s/ ?" W3 p2 {! l8 w5 y
         if(!s.empty())
8 |7 n1 v+ A- o2 ^5 E          {
1 S3 P  i* l- E+ K             tmp=s.top();
( @2 Z' u6 I5 h             s.pop();  g8 r, w0 f* ]: Y0 p! P/ ?
            q=vexTable[tmp].firstarc;
1 G7 A' V" G2 K# x' g             int t=tmp;
) Z8 U( @# ^9 n& O: B* |& H& E             while(q&&tag[tmp]!=0)
+ N2 B7 D' R! u( }             {
2 }9 [$ W+ f6 h0 ^                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);# F: K+ b% {! G$ Q+ x
                  //cout<<" 2nd    tmp="<<tmp<<endl;
, A, ?( Q& ?  ?) k! H: y5 R                   q=NextArc(t,q);2 M! J: {) T1 X6 g1 W$ p
            }8 @5 b  ~; J, U4 U7 a* R
            if(tag[tmp]==0)0 }2 ~6 F2 b5 Z5 V  P* S6 c
                  s.push(t);
) `: U1 c5 B9 O' w, L5 H5 z             ///1、对应上面连通分支只有1个点的情况
+ G  P  W/ L: B9 O             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈+ V' L, O/ C, A
            ///tmp要么等于找到的第一个未访问节点，5 w1 W) b& F0 p; I9 d
            ///要么等于与t相连最后一个点（已被访问过）1 U# H- X+ E0 I' e- u
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点: `$ r+ d2 e- r; t: k  }7 j: S
         }
$ ?: E- Z0 M: Q) i* q1 T9 W( ~5 M       }
/ p1 A: l8 [: i: h3 Y0 }7 Y$ _& C }
! j+ r) |$ d2 H, u6 k}( H, l5 |8 D0 x1 C" n- E( N
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
0 l% {& u2 `2 h. f- s- ?% mtemplate<class ElemType, class WeightType> int
  h1 s; E0 \$ M9 lMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)4 e% G5 @7 ~6 l/ `3 [7 x0 _3 Z
{
, Z  E+ l) S5 ?6 R if(head==pre)
, K) Q; Q3 }+ ^+ g% d/ ]1 v8 D0 a       return -1;; l5 a5 l+ x5 w1 v9 g3 G

# d) n& P$ ^  R MultiAdjListNetworkArc<WeightType> *p;# \! i/ h  L+ ~! L
p=vexTable[head].firstarc;8 o9 B5 a) o% R
if(pre==-1&&p!=NULL)
  ]2 i2 H; M: |) ?       return p->adjVex1==head?p->adjVex2:p->adjVex1;
- F+ N/ }$ D" i4 `1 Q //pre!=-1&&p!=NULL
! K! x$ @) u- S* S- L while(p!=NULL)! ~" v1 ]  D+ `( s& J  r- ?
{
7 W2 i' }5 l7 x+ w- y       if(p->adjVex1==head && p->adjVex2!=pre)" M' R4 n  d+ K5 P, ~
         p=p->nextarc1;" f/ g" n( ^3 l3 l& D8 z
      else if(p->adjVex2==head && p->adjVex1!=pre)1 Z* }" d/ y- l% C/ c; ^
         p=p->nextarc2;
  K: L; {9 T' a7 _+ {, a, `) w       else if(p->adjVex1==head && p->adjVex2==pre)% h/ t- ?0 F: l
      {
8 f" F5 f+ q8 O/ N4 M4 n          p=p->nextarc1;9 @6 F6 @! E0 D8 C% G
         break;
: y5 _& U& k/ H5 }) B; n       }, M( _; W, z0 P$ v  `+ x8 |/ X
      else if(p->adjVex2==head && p->adjVex1==pre)8 r7 w2 ]* ^' u% n* B4 x
      {1 Y! S/ f# r( q8 C- g
         p=p->nextarc2;0 s* @& `+ N  Q7 q) D; K
         break;
$ Z9 m" M' ?! w2 H       }
% |2 I; A( P* y9 h* a9 Z }- d4 H! s  b0 T  S8 p9 Y' J$ F/ H
if(p!=NULL)
" O4 Y) y1 f2 f% [ {
% @& o1 W9 k& a. `% V       return p->adjVex1==head?p->adjVex2:p->adjVex1;, J' U! i0 H% a, W1 v5 K
}
! e- o3 W% B7 b, u& Z else$ U  t  j  L% H" x. g( _8 S% A
      return -1;; f) a2 V7 h. k9 Q
}$ B1 l( M: u" _8 O) u# H$ D

; b+ r# O: O) p! I) P' R* x; [7 A# t  `6 U) ~" w, P
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
5 s0 |; F4 J8 S{
2 L% D+ @" M: F: N" G7 t* e& F stack<int> s;
6 t& t( b# n2 w% \' H int p,cur,pre;4 f( ]% x2 f' Y2 [
//MultiAdjListNetworkArc<WeightType> *p,*q;
- l. Z9 l3 a3 M$ a7 e5 Q" u1 a for(int i=0; i<vexNum; i++) tag=0;//初始化/ Z: Y0 i) x- F6 f' R  z

' S+ s% j/ [5 ~) f& A/ w5 t$ n for(int i=0; i<vexNum; i++)* ?& G6 J7 E/ T# |2 ~* S
{
( N6 j7 R% V* z       cur=i;pre=-1;2 @- u7 y  v5 B' J4 r& N; A
      while(tag[cur]==0||!s.empty())) H0 _, u5 }" s/ B
      {
3 F# J' B) Q( C2 x9 l          while(tag[cur]==0)
( w; ?9 D$ q+ F5 f$ m& A          {
; R. J$ ]8 `& V* h, K             cout<<vexTable[cur].data<<"  ";4 n! x' T3 T( D) P3 i5 m
            s.push(cur);
% q: U! B3 ]" s             tag[cur]=1;
$ `+ L  p2 x- {: y             //初次访问，标记入栈6 {) H0 a; h* y2 {

' N5 l* H6 _2 L             p=GetAdjVex(cur,pre);//p是cur的连通顶点
% F- N/ I( P, r, p( i  d9 D             if(p==-1)9 L4 _# Z( K9 N3 I
            {
# H. Y/ p$ B  ^4 r( A                pre=cur;s.pop();
- B8 \0 b) V5 a3 Z7 K/ K! m' @                break;
- G& P1 o3 R  W9 H             }  ]+ A0 i) t# |/ u5 f7 o
            else1 J, ^* Y4 P- H8 d
            {1 k6 J- B0 z8 c3 Y
               pre=cur;& ]( C7 a7 A/ i* U( V* C
               cur=p;
# d3 k6 o  R& i4 Z             }
  t$ i% P2 b. A" v) |" U4 x/ z) b' ?2 _4 L
         }
! T, t7 R0 U6 R# R6 W          while(!s.empty())
6 I( ~- E/ V. D, F7 t          {: u$ c+ a+ R5 g1 x
            cur=s.top();6 l" ~2 ~$ ^% y2 P: ~  n
            p=GetAdjVex(cur,pre);
1 I$ L3 |; p6 M/ Z             if(tag[p]==0)9 |! H% W  R3 c5 `  o) f0 u4 @/ w* }
            {5 I7 R/ |) H( a# d8 j
                  pre=cur;
2 W% S- ?& F2 W" w$ w$ A                   cur=p;
6 J- |. l/ P2 b8 I; I                   break;2 N/ ~  L; p) ^# M
            }
- _0 b5 q: D# q" [4 d; O  N. f             else
3 \4 V+ H( Z) i( W7 q# L             {) t+ r* c/ e$ q4 u$ S7 i
                  pre=s.top();
' }9 B8 g3 i6 [3 g6 {! |                   s.pop();( B8 e7 f6 [) u, Y; M1 o
            }
4 h9 K- O: n+ @; j# H
% ~, }- ^# y2 t& [: n3 v9 t- {          }, l1 A% ]% P5 E8 X4 ~" e
1 ]  I: e% M$ g5 |) a; `
      }. n: ?; L" r% O( [' g5 a/ B
}4 t9 P& H% N& L7 m9 o
}
( `; G  K* Z* \* [. a3 i* @! M. Atemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
0 V/ m1 S" [. V& y{
! G& {9 {- }+ v for(int i=0; i<vexNum; i++)% J- D4 H. \1 Z, D: ?* w- d
      tag=0;
% S/ b4 K6 c. h$ w queue<int> q;7 L  e3 @' U" X( \
int tmp,t;
2 m' i: g/ T3 b) K- N. c MultiAdjListNetworkArc<WeightType> *p;3 L0 q9 x# ]4 U3 `3 h# e" @
for(int i=0; i<vexNum; i++)0 T( @. ?( n- {
{
. y$ _, G/ `9 `- ~" Z7 R( P- @       if(tag==0)& A. Z- M& G7 C6 \. R
      {
; E3 C( `! Q& Y. R5 t) ~  {- F! S          tag=1;
8 c! J7 v3 L6 [8 a3 I/ a' z          q.push(i);* o4 Q  \9 o1 d
         cout<<setw(3)<<vexTable.data;3 v3 J2 k: z/ a) m+ M0 S/ ~$ j1 \( ^' F
      }  p# Y$ m& K% G- G) b! I
      while(!q.empty())$ l$ E/ h+ R' a% i  d
      {  _7 Z& Q0 h. b, c
         tmp=q.front();0 R# ?: i/ i  v; n3 b) T; o6 k
         q.pop();
6 H, ]+ G" h; r' P: ~          p=vexTable[tmp].firstarc;, K5 ~6 ~# I( ^6 H
         while(p!=NULL)
/ a/ A+ Q1 I: A5 O4 E5 b' ?          {- l; V# e) s0 |! k$ ~
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);2 Y) T/ @0 K( y2 S( c, C
            if(tag[t]==0)
3 L2 |+ s6 N& ~5 e4 B: G             {
9 z5 U: }2 w: h9 ^+ Q; p                   cout<<setw(3)<<vexTable[t].data;7 {/ n( F% G( r9 c1 Q2 {
                  tag[t]=1;2 Q3 ]7 f& A# e* w" m
                  q.push(t);
8 s7 C! @- W! q2 G$ X' V; x: r             }
+ o6 Q. s: C, n* P. C- \             p=NextArc(tmp,p);$ I9 N' u3 N6 a  v! v+ B2 T0 r% T) V
         }
* M  Y0 A# @  O# q       }
; q: F& G+ e+ j }1 ~+ h3 [5 g+ m. ^
}
- ^. m0 R1 c3 itemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()0 A; B. R1 q2 O5 m5 n: I
{
1 j1 p4 O2 E* R& [6 J MultiAdjListNetworkArc<WeightType> *p;
8 l/ Q  R& |  s+ y$ L cout << "无向图有" << vexNum << "个点，分别为:";
; W; _, I) Z! `# y" a$ N* D for (int i = 0; i < vexNum; i++)
) ]& f2 `9 X0 k$ |9 B       cout << vexTable.data << " ";7 |9 o9 v( x$ A; q) R
cout << endl;; A+ V$ {' u9 }5 L5 v0 ~2 T! x' ~
cout << "无向图有" << arcNum << "条边"<<endl;
  K8 f" `& |1 N# r; @% U* d for (int i = 0; i < vexNum; i++)
7 G4 Q; C5 m9 K {, [9 f. j: M/ ~+ {, ~
      cout<<"和" << vexTable.data << "有关的边:";3 L8 N. j8 D7 {& b
      p = vexTable.firstarc;& |! _5 s- l6 b* E' t$ q, @- p
      while (p != NULL)9 q' m) n& J- w% }2 j
      {
# M7 x; Q/ X* Z6 |          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
9 ?! w9 Q% M0 B9 K4 V( N9 x- D9 ^          p=NextArc(i,p);5 K8 G8 ~7 ?7 o$ P2 I% F
      }
4 {, r2 H2 r- d5 M$ U       cout << endl;
. T: j: v( n% Y! C/ t, s5 G }
5 V' `, h) P3 g. c}
0 ?  I4 W4 o$ X$ B9 H2 u/ \6 i$ @2 P- r' U' W- O+ i

, [$ n& Z' C5 v0 F邻接多重表与邻接表的对比! \+ o- H3 [, t5 n" O5 a$ U
) s5 c- p1 |, `( O  H) k/ a" S
邻接表链接! F, f# X5 |/ c0 o* `% N
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。! Z9 H3 k4 Z% A" B
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
. }7 {1 j3 H$ [# E( e1 e3 P' O6 o为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
) H. W" T$ p+ l: K7 W: o% r! [————————————————
$ t, y4 c  N3 o# W6 n+ S/ ]# ~版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。. G1 ^! l7 N" Q( L4 ~, D, [* f
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669588 a8 T: J- a' R* B, R! j  c

+ O$ K% D( o5 e0 v' F1 C% S* R" \: z! A. I) H% \* P$ w% H; d5 L
- I( c# j/ G5 a* x0 P( m' L! J

1 p8 ~" @% y$ V; _& v0 J& b————————————————( }( ]) c6 H# P* i3 f$ C* {9 ?
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# k6 R6 G3 [/ B原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
% U% a: w* C2 \; a7 e1 [% E" K5 o" r7 ~! ~7 e: L) T0 J" v/ E' b
8 d! F) e5 a0 U5 w$ W% K8 O