查看: 1664|回复: 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 n' f7 ^7 u- e8 t! x1 V. ldata域存储有关顶点的信息；& f; {3 `6 n7 E! x* Q; [6 H$ Y0 }
firstarc域是链接指针，指向第一条依附于该顶点的边。
; m; U! [* M1 j. E1 i: ]4 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;4 c1 E$ @8 Y) R9 i
for(int v=0; v<vexNum; v++). C% U. `0 C1 A  E  s
{
. b' D1 b& s. |$ u1 [       if(tag[v]==0)
! H1 R/ u0 v8 w2 L& g9 r0 O          DFS1(v);
' D3 w5 _2 b3 j }( V, L) Y& E* W+ c
}
4 S1 T4 K  c% L: Q/ I- |template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
- \) L; ]/ `5 \$ L: ]3 Y{( X. X0 A, l9 L
stack<int> s;
, I1 {% A) Q. f# X7 i+ z int tmp;8 j5 P; _  ]8 h. u  I  {) s
MultiAdjListNetworkArc<WeightType> *p,*q;3 V/ ~% ]2 \. o0 I  I* n4 `
for(int i=0; i<vexNum; i++)9 A1 O. g1 ]0 r: c, \
      tag=0;7 O% y2 W/ {% y: a0 |
for(int i=0; i<vexNum; i++)
+ j. K+ r, g8 [7 L2 C8 A {
7 Y1 D7 P, ~8 O) |. I) {' X# I" ^       tmp=i;# J+ ]3 S3 C9 t) d  y: Q/ y4 @
      while(tag[tmp]==0||!s.empty())% H' j, r# u/ K7 j( T8 g
      {
% Z1 D4 D1 p" U6 M/ c$ A. Q          p=vexTable[tmp].firstarc;! C+ t0 D/ m7 l' |/ {, ]
         while(tag[tmp]==0)+ d$ y* Z. B) Z8 M# q6 b; Y
         {8 C/ ~5 b/ E2 ~: s9 t
            s.push(tmp);' C# D9 X6 z2 |6 H- ^# {. T
            cout<<setw(3)<<vexTable[tmp].data;6 v1 y2 |+ i* k
            tag[tmp]=1;) O! p5 h9 `2 w5 J/ f. \5 R
            p=vexTable[tmp].firstarc;- h  B! U& K* }& R  b
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for$ O+ b( |1 }" r9 q* O( S5 D
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);- l) m( \' W  N
            //cout<<" 1st    tmp="<<tmp<<endl;" s; z, U0 t* Y! O5 U
         }
7 F& U1 F- e* Q* }1 n) ?          if(!s.empty()): T+ h; ~/ X' n' p
         {/ _3 ]% g5 k" G$ O% K$ z- x
            tmp=s.top();
0 [' @8 s+ p' i1 w) a             s.pop();
: m) k0 g* C5 I6 |+ p6 F2 c, b0 N6 f' q             q=vexTable[tmp].firstarc;- S9 K9 @/ m+ j$ i0 M
            int t=tmp;) W6 W1 s. \' i4 N
            while(q&&tag[tmp]!=0)& ]4 }  V" o0 w) R* D
            {4 U, f7 e! R# L5 O
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);" l. W6 P8 h% Y9 ^# q
                  //cout<<" 2nd    tmp="<<tmp<<endl;  K- @; y8 b4 I( S; A
                  q=NextArc(t,q);
0 r% @/ u, X, ~: i( R9 _  L             }1 O1 S6 H7 o, R7 ]
            if(tag[tmp]==0)
; T: x/ c, ?. N- y7 c6 C                   s.push(t);" @7 F9 Z9 M1 F% N$ E
            ///1、对应上面连通分支只有1个点的情况
5 r4 L9 b6 q" F* h             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈, {6 B: s; M8 g: ~% h+ ^
            ///tmp要么等于找到的第一个未访问节点，
- \+ T- O0 U" Y: D/ U  z             ///要么等于与t相连最后一个点（已被访问过）
- e! h3 U9 M) @2 V" W. z; Z             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点3 Q# A. M+ I  ?$ l7 c3 ]
         }! l9 g( ]* z  P. S) D  m7 W
      }5 e0 N" b; j1 Y
}. Q& [! q: a/ C6 p9 b
}
( P* S. d. ^3 E, O+ E- X% X- F//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1) W( u. j. Z- {. ^7 G
template<class ElemType, class WeightType> int
9 q/ O: N* I5 {- RMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
$ K' A  L" r' \; T* \. w{
0 z5 d; T- k2 O3 p3 ? if(head==pre)
5 Y7 T3 M& U  U/ c       return -1;
$ ]! W" Z, V) W7 \5 {- S. F. I
2 ]% Z: t+ H- B MultiAdjListNetworkArc<WeightType> *p;
, z% {5 T( O8 _" Q  e' x% \; i p=vexTable[head].firstarc;
- p2 q% o. U/ ?8 t. Z* Q& v if(pre==-1&&p!=NULL)
8 x. l% \% c/ d3 s: Y8 v( D       return p->adjVex1==head?p->adjVex2:p->adjVex1;
7 X8 H; a. J; E1 ~/ C( S7 @ //pre!=-1&&p!=NULL
; ]) K: f4 A& z- y3 s! H while(p!=NULL)/ u; J5 I" h$ ?/ k
{
+ p# w6 e% h+ ]& H5 H2 W5 n       if(p->adjVex1==head && p->adjVex2!=pre), d2 X  o# Q# W- Z- I
         p=p->nextarc1;
# i+ ^- x/ Y; {' r       else if(p->adjVex2==head && p->adjVex1!=pre)
$ `9 y# M8 H: b) \; B  G  j& l7 N          p=p->nextarc2;
; j! h3 z! U# D0 N- B       else if(p->adjVex1==head && p->adjVex2==pre)
) Z6 D$ P4 J- [, b: [4 Z       {
, y0 {+ {5 p; p% U  O( {) @          p=p->nextarc1;- b  [* R! i4 R& U7 F9 S6 ]
         break;5 n7 g' r3 ]3 c1 d0 O- h) e
      }
; t: Y# N- O- e6 O  ^       else if(p->adjVex2==head && p->adjVex1==pre)
0 s3 h+ P# i- [0 C) Z  H# u       {
$ s5 }# Q2 i# Q& Y          p=p->nextarc2;8 d5 j# i+ K! N+ V
         break;* I6 z/ l  b( M: R: k" @9 |6 v
      }
' M$ v/ s1 U* v# V  A0 C }
2 I( r7 P7 E# c' v! M& a* H' t if(p!=NULL)
; ]. {8 @5 Z( T3 O {9 j/ v3 x; G3 F) _# O9 @: D
      return p->adjVex1==head?p->adjVex2:p->adjVex1;* J$ S6 [7 i3 M% `: P) C1 e
}
& e" n  {: }  {9 z. M, o else
5 u4 y- T% H% G( W$ c# Q' c; w       return -1;3 ^3 a1 ^# F3 u. ]! B' F" q5 Y& F9 o
}7 C2 a& N/ Z* C6 T7 [3 ]

5 G* f2 j% c1 \& V5 s; Q! e4 m
) N) @; u7 }- \- ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
" ~& \7 p8 y! I2 s, U5 p' T0 _+ k{6 g! n& |* D% I6 o3 }$ n+ _; [
stack<int> s;: ^+ Q/ o1 g4 d# }) W
int p,cur,pre;
9 E! j) _" s& a0 Y4 ?' ?1 \7 ?1 P9 l9 F //MultiAdjListNetworkArc<WeightType> *p,*q;5 C% z% {( ]4 J3 ^# a' Z5 h
for(int i=0; i<vexNum; i++) tag=0;//初始化& j$ ^6 L6 g6 j0 k% L

* c- `3 o- n- H8 z5 k  R6 y for(int i=0; i<vexNum; i++)3 R7 R- l4 ~0 J3 x$ h
{
& M5 T  J* @. m1 H       cur=i;pre=-1;
2 ?6 c6 o% Y7 g       while(tag[cur]==0||!s.empty())
- l1 Y( b) L' }: ^0 P4 E% C       {
; S0 Z( t) O# D- h. M) S4 O          while(tag[cur]==0)8 o- Y* |, a# ^( E
         {
& ~( i& ]& T& p& f" {             cout<<vexTable[cur].data<<"  ";
( _6 p! R3 Y- `5 G% \             s.push(cur);
9 X% R) s" w- P5 C! ^             tag[cur]=1;* F: a' N3 b0 g6 e
            //初次访问，标记入栈; T) R$ K1 g/ {! m3 O' i) Y

$ `$ O& b3 J7 ?6 d             p=GetAdjVex(cur,pre);//p是cur的连通顶点
; a7 O, d8 k: h& h8 U) f6 A/ R             if(p==-1)/ T; R/ r) R: O2 ]( \) o! c
            {
% s$ h7 h; |9 N( w                pre=cur;s.pop();
" u8 X( V  |; @2 e                break;. m! m. N8 S4 m* V# n- S
            }
% t  b4 Y2 Z% t8 a2 }             else
6 }# r( _0 ^' p" [             {0 h0 [' }* u1 _) [1 r; O
               pre=cur;
; ^  l3 X2 j) U. o: v! v                cur=p;
' b3 `. S# z2 n5 w) h# r             }
' V. f  e& Q; C1 b2 b2 u. Q0 z& t! D- e. J5 n
         }
8 {* X9 z- Z/ A  O          while(!s.empty())
4 F. _1 L  {0 `- b; R- k          {
& F$ m9 {$ N: t; Z/ W             cur=s.top();
: ~) h% u/ |6 T- \6 U             p=GetAdjVex(cur,pre);
9 Q( L" v7 g- L# C             if(tag[p]==0)
+ A) A4 N8 l/ D' `/ U4 u  W             {9 ?: ~+ W% g$ T
                  pre=cur;7 ^) U8 s0 m. T- v% v" d
                  cur=p;2 C" |; ?1 s0 Z) m
                  break;
" Y' W% |) ~( B2 w* x! G             }
; f& Z" U& v4 J             else
$ ]! u) r) X. e4 w             {$ p6 G! O, g0 p8 F7 [* ^
                  pre=s.top();) {5 j/ f! W' v' z) w3 [4 {
                  s.pop();& C3 d7 t! g5 f" }4 I$ a
            }" G% r0 `1 G& }; V! m) A
& w3 E9 N) J6 i* ?! q  b2 E4 U: l
         }% \% p% o" w) ?; Y
7 h' ~. r6 s. m' v9 u5 _; _
      }
+ ~* G. i3 c! I5 o2 {; p }: i  h9 w, G: C. B7 ^
}/ X& [) i- L; m% B6 {; M1 @3 n" C
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
, K5 f# }+ H, F# N/ Z& W9 y) x{  o) q9 E! `/ c! k  X8 C9 r6 X
for(int i=0; i<vexNum; i++), g$ m7 X2 Q  X
      tag=0;( Z5 H3 q* h% m) {' H  h
queue<int> q;2 d8 j9 f2 u; s) @( d( a
int tmp,t;
: J; }9 z* |0 e0 C MultiAdjListNetworkArc<WeightType> *p;
# _' u; n$ s- L; J+ u for(int i=0; i<vexNum; i++)" f! f: h$ R& g* Z) l
{
$ V& v5 n) u/ N' D: A       if(tag==0)% j) A& j+ i% y# r8 ]4 E
      {
& o& {9 ~/ |3 U2 p$ S          tag=1;
$ L' i. F9 |3 }5 n          q.push(i);6 f$ |( y1 Q0 ?1 U/ n
         cout<<setw(3)<<vexTable.data;
% z' f$ S0 r% V& H       }
. i$ ~3 u+ w: e+ V# }       while(!q.empty())/ p. |9 j2 d+ r" {& x
      {
$ I4 X  L: E% A. r4 f0 N; {          tmp=q.front();; f* s, q# j+ ?- X
         q.pop();! _6 M: y7 E0 Y* P9 l
         p=vexTable[tmp].firstarc;
3 M* f7 K" z& A' P          while(p!=NULL)
# Y) j$ E; |3 ^1 S  `; o          {  s. o8 c% S" a# k( b! S  ~& T" U6 P
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);; ?7 C, a7 p" L2 f
            if(tag[t]==0)
2 X3 r+ v% i( n, X: k             {+ G& G1 C" l) f/ O- u9 v0 ]
                  cout<<setw(3)<<vexTable[t].data;% T# B2 w. q" B7 d) |1 l& x
                  tag[t]=1;
  @, a9 m1 c& C3 R6 W+ I8 r6 o                   q.push(t);0 m+ f7 X7 {9 s$ h; P
            }
. j' I8 E2 ]1 f$ F             p=NextArc(tmp,p);
3 L* w$ Q% i; q* t. l- w          }
& h# |  W+ P: D+ a4 E& |5 z# L       }
" K" X9 e( m. t8 [* [2 V1 L- G' s }0 ^2 B5 V" ^0 g8 _# O
}
2 p  N: ~# c, {# W2 h% Ftemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
% H, F1 b7 s9 G. O: G; l{) M/ \7 f3 ^! {  T
MultiAdjListNetworkArc<WeightType> *p;
$ F3 T: R. y* s( ~ cout << "无向图有" << vexNum << "个点，分别为:";
8 H0 m7 y  B9 p& K for (int i = 0; i < vexNum; i++)& K% n/ L; }  @  |$ C6 |
      cout << vexTable.data << " ";9 L# R1 M# }9 k0 z
cout << endl;
. T7 k" U. ]) K cout << "无向图有" << arcNum << "条边"<<endl;7 f9 q  b- w! J8 e& T! K, v: G
for (int i = 0; i < vexNum; i++)
5 r! L+ ]; r* L) }7 V {
+ _) J& Z6 U( l/ ]" @4 U       cout<<"和" << vexTable.data << "有关的边:";
: B1 ?$ `7 K) W       p = vexTable.firstarc;/ }4 T0 z* ~* z: P# d0 M
      while (p != NULL); u# t: i) O; l. S* p& @* v
      {
; J$ o3 C4 p8 k/ e9 g          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
. y3 `# Q% J( R" Y8 N6 k' _4 l2 _          p=NextArc(i,p);$ t" c( f! j/ k" }
      }
) `! h3 l. |+ N/ @# b       cout << endl;
& G4 J" S  S. _0 S }+ h" n' Y0 Z( b9 N/ ]7 v& Q
}
( A5 [% o) Q& l+ t9 Y: Y
. q8 `9 r; p& q( F$ T! {9 A, X, }
0 O# \( A- A- ^* }$ b+ P, u邻接多重表与邻接表的对比
6 V- }* B; u4 T% \
9 i# s2 b& o3 v: O) l" u邻接表链接2 M% d% P3 L8 W
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。  k7 P" B8 ~& {4 p( T
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
6 O" c; K: s4 B  ]. A为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。5 |3 T9 v8 ~$ _* Y* D/ o: J" R
————————————————
% y1 k4 |9 S7 Y版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 p/ D# [* J* y原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669586 B6 v4 J0 Y8 C7 Q  @
0 y8 v" E, ]8 X

4 v0 W9 w& g5 X9 W' h0 M* R
9 Y2 }$ q; h8 `$ l8 n% w4 K7 u" X1 P
————————————————
& C. D2 H, c! r" W版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( w% }2 `% w9 U2 K6 x原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958: q. J" e2 a/ q4 n' G" x5 a9 q

, L5 h1 w/ ^- r3 G) H* g% C* o# O1 _0 d8 J% L6 y7 A; _