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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：9 d& f9 `) N7 d. B, d
data域存储有关顶点的信息；
- y* u( H4 T: `firstarc域是链接指针，指向第一条依附于该顶点的边。/ g. \1 T5 H6 i7 e) n: T
所有的顶点结点组成一个顺序表。

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;! k9 U9 i1 L: t3 J2 G
for(int v=0; v<vexNum; v++)
! x2 F/ p1 M. e {& ]) K. ?2 X- o4 O7 F  L
      if(tag[v]==0)
, V( [% A3 U. M" O& h9 y          DFS1(v);9 Q, N2 R$ {, B4 j
}
' n# V: H5 C- n; J- ]}
3 j! R, v1 P+ T1 _' u# ^) Ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
) U/ e7 o5 z& m4 t{
, c9 Z/ Q" G, { stack<int> s;9 @" M4 ]$ ?: l/ v
int tmp;! `0 }# B" O: P+ N8 a
MultiAdjListNetworkArc<WeightType> *p,*q;- f( O+ Z- C8 G4 ?0 a$ G
for(int i=0; i<vexNum; i++)6 g# I5 W% `1 o$ r$ e5 `' x- f% J2 J5 R
      tag=0;* w; s1 E& N9 e  J2 Q- ~
for(int i=0; i<vexNum; i++)) }6 H8 G% P& t, d% W. h! \
{, k# r' D( k$ O  i' I, D" m; @* G
      tmp=i;2 p( Z- g. C; k2 f
      while(tag[tmp]==0||!s.empty())6 E; s' A! |( J! w
      {0 y2 E* r- v1 _, K# Z9 }* B
         p=vexTable[tmp].firstarc;
1 G4 R' R% l5 i$ w1 k          while(tag[tmp]==0)1 t$ g& i9 x/ ]' Z$ }
         {) D" X. c. x& G" E5 }. H
            s.push(tmp);( _1 y9 m* j: b- `3 p4 C
            cout<<setw(3)<<vexTable[tmp].data;
( c. E+ v' i& ?6 B             tag[tmp]=1;% J* w' g, ?: |5 P1 b
            p=vexTable[tmp].firstarc;) w" z/ G4 [  T; `$ K1 D1 n
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
9 Q% X9 L& }6 q) M) H             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
! W+ E3 ^: `: K, D7 W             //cout<<" 1st    tmp="<<tmp<<endl;2 o- p: E. o5 K: m0 u9 t, o
         }4 Z: K3 {8 H6 F: G9 R0 `
         if(!s.empty())
+ `1 `2 T2 F+ o1 `5 |          {
! m) ~( P' O( \7 k             tmp=s.top();5 q( @6 O5 r5 P/ O. `
            s.pop();
; \, H4 O( [8 {/ l% X             q=vexTable[tmp].firstarc;
9 `8 C& W. n# w0 ?6 [; v# D, R             int t=tmp;
/ I  r; R& E  t" T             while(q&&tag[tmp]!=0)
8 q2 C$ W# e5 I" P             {& {7 g- d: G+ p# t
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
" H7 `9 q2 x! Z" S/ W  @# ?                   //cout<<" 2nd    tmp="<<tmp<<endl;6 J8 _& i8 c7 Q  l9 j% S
                  q=NextArc(t,q);
9 b  T: w. h* b& f3 h& T             }
! D* e+ m# n; m! n% o             if(tag[tmp]==0)# s- p( f6 s- s; u6 U
                  s.push(t);; l% t0 e9 y7 g% h. b
            ///1、对应上面连通分支只有1个点的情况3 w. c9 Z- r# b: u9 d2 f' k
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
7 i$ z. i& C& h9 ]1 R' q' q+ |             ///tmp要么等于找到的第一个未访问节点，
* U& S7 G) ?0 W/ S3 T& T             ///要么等于与t相连最后一个点（已被访问过）& l% z$ @9 ^+ Y
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
3 r' h( H  n( h1 H% R          }
: c& \) H: r% `3 m% U3 A! P1 D) O       }) w& |! y4 V  }8 J+ `
}
" X# A" M' m; K4 \}
# d" w# d* A% ^& |# {//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1# e  |/ }7 d5 s1 u6 I
template<class ElemType, class WeightType> int- j# i0 W8 p- y1 A2 o' _' n0 \
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
6 L% [6 b9 E$ N  f6 M% c% h. B{
: n1 Z1 Q' n6 `! |, u/ Q4 r" s if(head==pre)9 y3 O! a0 J: {4 e+ T: }: M( f
      return -1;# `: R6 p6 o' H, b: G. o
0 n$ O9 M# T9 }* @; u* {
MultiAdjListNetworkArc<WeightType> *p;3 [! |( Y8 @! f* D4 e  l+ t1 _
p=vexTable[head].firstarc;; [% S9 V9 _2 I: G/ M
if(pre==-1&&p!=NULL)
9 E, G0 T1 m9 d; r0 V       return p->adjVex1==head?p->adjVex2:p->adjVex1;
1 w, f, Z  n( N& S7 v' W8 h' E //pre!=-1&&p!=NULL
7 W% m" {0 D) s7 h- g while(p!=NULL)* ^8 L3 T; W/ B# b) R5 k
{# z6 `9 x! ]. `( h
      if(p->adjVex1==head && p->adjVex2!=pre)# {0 M  n. j- ?/ O2 v
         p=p->nextarc1;' B' `* t' `  M. [5 Y! ~
      else if(p->adjVex2==head && p->adjVex1!=pre)
( S7 b$ P8 S2 W* E3 H- l" n          p=p->nextarc2;
; i" Z3 P1 ]* {3 l, x4 N       else if(p->adjVex1==head && p->adjVex2==pre)/ @9 q# s% M+ o7 M. W
      {
+ u' G; G8 k  O1 m  N: x7 Y          p=p->nextarc1;' q9 S; c& y& @! U5 E. D0 w$ r
         break;
$ s; n5 Z# j  K- v! l/ \* ^, a       }; J3 Q2 I% k, B
      else if(p->adjVex2==head && p->adjVex1==pre)
) X1 P" m! t2 M5 N- Z1 s. H       {
! d1 F* g  B# l# S! n/ u          p=p->nextarc2;1 S  F7 x- F/ N4 \# Q
         break;
2 q6 H, Y8 n0 p, V& ]/ i% U7 S9 _5 }       }
7 m2 s8 n# p; Z- P* T+ s }
* C! L' U9 A. E0 Z  D  `& Y! U if(p!=NULL)/ s5 K: c) o' f1 X8 o+ q
{
4 i8 {7 `& W( a) f/ A- ~, W& e       return p->adjVex1==head?p->adjVex2:p->adjVex1;( {  j3 ^7 R5 u) {! U
}
( S6 y8 h8 N# c) h8 e5 m  a3 A2 D else
6 \# q9 w. e$ |  a       return -1;
: V  u( \% [% ]* ^) k0 ]}
. b+ g$ {- N7 F- h) A7 k: ~& y( o. I1 Y
* J0 T5 Z( z( m1 n) ?
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(). W3 T' Y- J& k
{
- c0 P$ P  S' m' L1 {. ~ stack<int> s;" l2 d, C! o% N
int p,cur,pre;  d0 K* J. O1 s% V4 X0 }
//MultiAdjListNetworkArc<WeightType> *p,*q;
$ G- P4 \" ^+ T' H* M- K for(int i=0; i<vexNum; i++) tag=0;//初始化: u1 A4 @3 v0 t: k; c" S

- {9 y9 J6 w/ c for(int i=0; i<vexNum; i++)3 `/ |1 n5 e* o' D' S, x# C
{
# r- L; r% B* p5 p       cur=i;pre=-1;
; D) g% {2 F3 e       while(tag[cur]==0||!s.empty())8 R5 U8 H& B& v# X/ w$ Y
      {' u( S) x* ~& v. p/ ]3 ~0 K  W
         while(tag[cur]==0)/ r8 A* {  Y" n6 E5 Y: S' j! C+ O) }
         {4 Y  }3 g9 H) c7 X
            cout<<vexTable[cur].data<<"  ";% u9 @/ @* x2 A3 Y/ m
            s.push(cur);
/ B$ W1 V* m" @0 ?( s: q) r             tag[cur]=1;! h. S4 }- ~3 a" d
            //初次访问，标记入栈+ y3 Z7 P, D. w2 i3 M. y

9 w" j' S, o9 u' d5 k) G$ i             p=GetAdjVex(cur,pre);//p是cur的连通顶点
8 p7 g5 p6 q1 m$ o$ k             if(p==-1)" M, n6 a( i' @2 H! W
            {& o+ l2 l& D# q* H
               pre=cur;s.pop();
. X& x8 n( D. z9 z                break;: F5 G. |( I/ \5 @: J9 B
            }! N9 R1 S0 X5 A( q
            else
' N4 f! [. i( q6 q# A1 T* G3 Z             {" G1 W6 B; v3 A2 V
               pre=cur;
' A& A! G. P4 @/ w7 J                cur=p;
# ~- o0 E* r- o* C' \             }' C# q  L9 p& ~* W8 P2 l+ _( V% ^

( g: l8 {" S% M5 Z2 W1 }          }
  G$ j4 C0 w. B8 [8 Z          while(!s.empty())
3 l% x  q1 P) D/ Z3 U* ~          {
# N) E6 K% o) i( O             cur=s.top();
- K4 Y; q: e9 t$ l# I0 n4 ^; A             p=GetAdjVex(cur,pre);% h. C# d" ?! }8 B( w+ K
            if(tag[p]==0)
, @" V2 O8 P8 i5 A, y             {
7 m* O4 P2 C: x( r" L7 |3 M                   pre=cur;$ l, |7 `, f4 q
                  cur=p;
9 p+ i) I' I8 E                   break;* R1 d6 T2 z6 U6 @" m  b& U
            }& n* `5 I6 a7 @; q1 t
            else
6 r8 D( r9 M# W! f( o8 E/ r; K# B             {
+ [9 g6 U' i# `: v1 h  Q                   pre=s.top();1 V: J( I& i$ S) X* j
                  s.pop();2 |) N& g( I2 N& M! U# C$ a% R$ `
            }
- F! `: ~( @  p+ z5 f- I
3 Q: x3 B/ M5 x' D          }
' l- y. k: j: t2 H3 d6 @. |2 M! S! S0 z% S+ h2 A1 I6 X  C% Q* K/ l
      }# v  N! M( H9 C& G
}
9 Q0 Q0 G. F, u' m2 T}
( i* k4 z4 G" d. d6 q( e" @+ @' Qtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()- M0 B, C6 A% X
{+ [1 M+ N5 L  I+ V
for(int i=0; i<vexNum; i++)
" f1 @. a; A+ j2 x7 D8 s3 M" _- }% ^       tag=0;# \7 H" J4 g7 x7 R1 ~" |
queue<int> q;
+ _* y/ |) E0 | int tmp,t;. g0 Y7 S' h+ F" S1 W
MultiAdjListNetworkArc<WeightType> *p;
5 K; t0 q# d' T% W+ s for(int i=0; i<vexNum; i++)
" Q* m5 w; k$ g5 O0 h3 s/ m3 [ {0 _  q" T1 C/ ~3 u5 \5 B/ C% E; A
      if(tag==0)
4 m0 k3 U" Y) |4 y9 L, g. M       {* D% K3 A& e4 U  M5 X; k. E
         tag=1;9 x. [2 P4 k% M) ?9 i
         q.push(i);4 r0 l9 K7 Z8 R. d8 ^  H+ S
         cout<<setw(3)<<vexTable.data;' Q$ o4 L8 ]% X
      }
5 \( b5 V: G; B& l% n       while(!q.empty())
4 \3 z+ \' k1 c* d0 L       {2 X( f: c3 e7 t1 Y( Z/ `) R, U, K
         tmp=q.front();
0 j6 P9 U" ^( \: T% P" f7 E+ I          q.pop();8 I/ E) I" V6 B
         p=vexTable[tmp].firstarc;
6 z( ]: [/ [9 i; }) P6 A          while(p!=NULL)3 G, e0 v# f$ [+ U
         {
) v: A0 G3 X0 F. d4 p             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);8 \& U! [# B+ t( K6 b
            if(tag[t]==0)
) |7 z3 k' r+ ^6 h             {
2 t* Z% Z& Y9 C! E9 {, ^( ^                   cout<<setw(3)<<vexTable[t].data;4 ^4 Y' Q( H- L0 W
                  tag[t]=1;
; \& z; g* R6 H; J: C; b5 \                   q.push(t);% I% w& k9 m! m& X" f8 z9 U
            }5 ~  N6 h( N- Z& n, s
            p=NextArc(tmp,p);
8 }$ Z! D* T' Z: u          }
9 z2 L6 y6 n2 ~/ Q5 H: R$ _       }; R) Z' ?6 ?- {! s; v, a7 i
}% k& }* w4 l/ N) V8 w' s
}9 S" F& L+ H3 {' @0 z' l
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()9 Y" \9 _& P9 T
{
7 X2 p* i6 g- a2 g0 }6 T* F- u9 k MultiAdjListNetworkArc<WeightType> *p;1 n" ?, I! a# `  _8 V( I5 M5 q
cout << "无向图有" << vexNum << "个点，分别为:";1 d0 k% _- ]0 l3 e- h" I
for (int i = 0; i < vexNum; i++)$ H3 ^6 R6 [" q
      cout << vexTable.data << " ";
/ {5 z8 T) J3 U( R! F: h$ F1 V0 e: z& ^ cout << endl;7 b/ ]' k' E! ?- Z8 y
cout << "无向图有" << arcNum << "条边"<<endl;# y" T8 J1 o" a6 I# U7 T  |
for (int i = 0; i < vexNum; i++)/ H9 |, ^+ c0 ]$ R
{7 x& E( V: t; P2 Q5 {2 j4 G
      cout<<"和" << vexTable.data << "有关的边:";& c" V- b( P! i* X+ q, }. f* I; d0 Z. m; K
      p = vexTable.firstarc;
- c: O& w5 F: L       while (p != NULL)
$ }$ G% h1 E4 a5 x7 S       {$ L4 w$ a3 r% \( f& y
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
: ]  p8 S- }  G3 R% n          p=NextArc(i,p);0 G* p/ m; r9 K% H, _
      }
3 O; R* Y5 p+ M/ M       cout << endl;1 T# |5 d0 A- B
}* E" N/ V% L4 N8 J/ {. C
}
. g/ ]* r. O0 e( u- u: b3 I5 L0 S0 t

; k9 a; o. M1 x9 Y) t邻接多重表与邻接表的对比
2 W5 C+ u" V# r+ `8 J- e" d; m0 L) E: T0 Y5 Y; r
邻接表链接$ P: z: W& D+ T2 A
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。" P$ B) b$ O: P; N
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
" C+ u/ I  {2 h& @1 v% Q7 f* b6 o为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。/ n( O+ R! u+ R! U3 x
————————————————2 n, S/ Y& x4 c6 W
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ U, [' C; N! K. ?' N原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958' p) a( z% R1 B. H+ v7 ?
( ]: j5 r5 A- n+ E) C/ _  \+ }

& l+ Z5 i3 {0 {1 X( Y; q2 \) V8 X* G8 q
5 b/ q; d4 M8 k
————————————————
! x( U2 E3 h! w# F# Y版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 a2 v& `- |. v: K: Z原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* [$ D% E$ n% [+ W8 q4 q, z- z. h
8 Q/ t# q  F/ ^, |3 J
' ?, ~9 S3 x& B& U