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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
: H \3 i( [7 q' W- K8 ndata域存储有关顶点的信息；) O3 Q' b5 N9 h5 o
firstarc域是链接指针，指向第一条依附于该顶点的边。( R! Y/ Y! \& g! F8 G
所有的顶点结点组成一个顺序表。

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;
" D/ {. ]( n0 m5 G; c& J0 x, G for(int v=0; v<vexNum; v++), f6 u" w% d" h" z
{
3 `3 G; Y9 \% `6 [- Q2 l       if(tag[v]==0)
( J, ?4 x& I# V- O, ]5 `( e; @' N6 V          DFS1(v);
: k3 ?( D" n$ o, Y! l4 }) o }
6 K4 f0 h7 _  q) Q4 i: p+ P! ^1 i) q}" d& l2 l1 }' b, V: B9 b
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()% F- ?+ {7 Q2 X$ o1 t8 I/ d9 O' j
{
$ Q3 w" w, _, j" a% p stack<int> s;
( F, j/ ]4 b3 C# G5 q1 C int tmp;  u/ U' \6 y1 J) P/ v* b4 O4 o# G1 \
MultiAdjListNetworkArc<WeightType> *p,*q;
, `; @9 U/ S$ i& E. O for(int i=0; i<vexNum; i++)! G# s: [4 z1 X- W5 \& x6 N
      tag=0;; e, S$ f7 P; U& m4 L+ Q$ F
for(int i=0; i<vexNum; i++)# {% B' ?5 B* j( V. S/ F
{7 h$ M7 Z3 S# t( l. n" m0 l  I
      tmp=i;
' ~' r; t; R. }  P$ o& ~, k8 j+ d9 n       while(tag[tmp]==0||!s.empty())
0 R$ N' u* A. d$ J( h4 u       {
  k, n+ q2 x" r) I          p=vexTable[tmp].firstarc;9 M' t4 @2 }% S$ v
         while(tag[tmp]==0)* x% v. w# y( T) j
         {9 r1 `7 R: e0 Y- D6 V
            s.push(tmp);
" c. [/ d" S& M' x& R0 |, G             cout<<setw(3)<<vexTable[tmp].data;* Y! }& B4 f0 w" G
            tag[tmp]=1;
' |$ V: L  n. R3 D' }             p=vexTable[tmp].firstarc;9 F5 {: R1 ?  J
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
3 F0 G( K3 @3 _4 ]2 N, l/ {             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);3 [5 R* f/ o- F/ h
            //cout<<" 1st    tmp="<<tmp<<endl;
) D) C1 H5 ]' t4 ]2 W% {( b! I  y          }9 l* d6 x8 O- l8 E. G' Q) Q
         if(!s.empty())
! o& S0 y: L8 |5 ~" |          {) ]* f! L2 c; I8 g
            tmp=s.top();+ c9 o' Q6 r* ?% ^) g! [
            s.pop();
2 H( `' A3 Q6 T9 y! a: b  \. Y% F             q=vexTable[tmp].firstarc;% w' r8 P4 U8 i
            int t=tmp;
- q$ X2 H( w, v4 L5 a1 k             while(q&&tag[tmp]!=0)
6 b$ N1 \* D8 I$ o             {
& U" Q/ ~! [& ?( C                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
8 p1 J% E+ v. Z/ K( l2 H: j                   //cout<<" 2nd    tmp="<<tmp<<endl;
) z" K' \$ ^) g                   q=NextArc(t,q);
, M# `- k' F+ \4 N8 Y3 Q             }( ?; ^' ?* V  I, V
            if(tag[tmp]==0)
0 R' r9 B/ s) \7 J+ l; ?- z                   s.push(t);0 n5 R& Z% j" ~1 K( k/ S7 `$ x
            ///1、对应上面连通分支只有1个点的情况
/ z) `6 o1 @+ S. X7 s6 S3 t( d+ |             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈1 R- @# a3 ]2 p7 p% c- ?" L
            ///tmp要么等于找到的第一个未访问节点，5 ]9 u9 W# ?: W7 b
            ///要么等于与t相连最后一个点（已被访问过）
! \( D; `* m! u" n) X& P! `% I             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点6 _" L( a, G+ d* W. c8 o1 v. U3 Z
         }
+ T6 U3 w& s& R+ h9 c% O: o& D# f  ~       }
& b$ p+ Z% A! M( E1 J4 Q. X }
" D$ r6 B' q" A5 u& k}
, B+ W) K! l2 \, U) |//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
% `5 z4 ~5 f8 P  i! D' Vtemplate<class ElemType, class WeightType> int
+ k  u9 r8 s! e$ Q" bMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
/ o( a. C3 ~) C. \9 o& ?{  f6 {- d: c- C8 v( v  O
if(head==pre): N+ G- e( ^0 F$ U! d
      return -1;1 Q% p( z5 q) u3 q( ?
* H1 N5 f, H: A  B* j
MultiAdjListNetworkArc<WeightType> *p;
& F* ^2 o3 y( v( B) a p=vexTable[head].firstarc;
( G% x  \# `7 _0 h# S4 j: j if(pre==-1&&p!=NULL)1 x, ^5 |: }; a: e
      return p->adjVex1==head?p->adjVex2:p->adjVex1;7 Z& D+ U2 {) k
//pre!=-1&&p!=NULL
5 O5 X" R/ i/ M1 M9 k: S, ?0 y+ c while(p!=NULL)' {: W: T  y, h* C7 p, J8 z
{
3 V6 ~: c1 n# d' r( c       if(p->adjVex1==head && p->adjVex2!=pre)1 ]) T2 _, `" Q1 f3 r2 t2 f
         p=p->nextarc1;
8 Z& R( X. o1 m- }) M       else if(p->adjVex2==head && p->adjVex1!=pre)
$ v% x- ?4 ~- ^2 F4 q! Z/ n          p=p->nextarc2;, c5 ~8 `0 ~& J# ]7 t7 @! S2 u0 |) P
      else if(p->adjVex1==head && p->adjVex2==pre)
" ^  q/ H- e1 ?/ D# ?       {
& E+ e9 Z! C7 J, z( x          p=p->nextarc1;
8 u7 J& V9 s# k- m  C          break;4 ~. S5 j6 Q5 x% b9 ^% N
      }
  A; ?8 w7 q! f: W3 |) V7 t       else if(p->adjVex2==head && p->adjVex1==pre)( N# N7 V. z! {% J2 C
      {" B1 C: ^$ ^& H( H8 {
         p=p->nextarc2;, I, O2 V0 _" N$ j9 H
         break;
3 C- g5 ~/ ^) g0 N' x' `. N/ g: t       }
  L1 I: @' N9 z }
  m1 m# K/ b4 a1 [1 D3 @6 v/ ?  Y if(p!=NULL)
& W! B4 p# E: B* a% h* V {
0 y5 [; s" F' r+ Y, @       return p->adjVex1==head?p->adjVex2:p->adjVex1;
% i/ Z! K0 O; F }0 p5 ?, B) G% f: `8 ^
else
* u5 q! t7 N% K) t  o5 V       return -1;
* Y& W! N; b$ N4 ]! V: r}0 ?9 _3 V; c% [9 U0 V
# b5 u" ^0 N" D9 n4 }5 v

/ C; r" _/ d# Z5 L8 r4 Btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
7 O5 g9 t9 [1 J, x9 S) V6 t$ p{+ P; V2 ~1 F8 P- ~' V4 L) l; P8 r) o- s
stack<int> s;$ W4 C# d/ ~; J% A: c* m* r/ K
int p,cur,pre;
$ x+ C" Z. k3 D //MultiAdjListNetworkArc<WeightType> *p,*q;. a, n8 b% D5 y% q6 Z: }5 N; T- C
for(int i=0; i<vexNum; i++) tag=0;//初始化
. z2 ]# s5 E7 o1 l) Q0 p& D- |  A' U7 Z
for(int i=0; i<vexNum; i++)
$ ^# K, Y6 L: v" b {
% r3 |0 o  @6 |; [/ m       cur=i;pre=-1;2 l& @& e3 K$ K" {( V
      while(tag[cur]==0||!s.empty())
2 T8 p/ r0 n/ m& J  {/ q       {
# S: H' \/ }$ X- D6 V7 O( P          while(tag[cur]==0)- v) c; Z4 ~  W  n7 J
         {5 _$ \# l) r* l. i- N
            cout<<vexTable[cur].data<<"  ";' n! U  `8 V' F, e$ x. X
            s.push(cur);9 _" b3 C. y; [) E0 e; G" d
            tag[cur]=1;; F* R& B, P% t& e
            //初次访问，标记入栈& Z6 ^- r3 i7 R: E* ?
  d8 c8 k0 |( a! B
            p=GetAdjVex(cur,pre);//p是cur的连通顶点2 N: v/ U2 s0 s( Q  g5 x
            if(p==-1)' h  O$ V* [3 ~" S0 Q6 i
            {# i6 d6 I! |. u( J! Q
               pre=cur;s.pop();
& h/ M( U- ~3 f7 ?- W                break;
" B4 j( Q3 H. q% |# }             }, m2 r1 }, D# a  ~; c% Z+ p/ O3 t# [/ p
            else
$ t( _/ k1 M0 @             {
! ~1 W% i- ]: @% p! d4 ^9 v' W                pre=cur;
9 w% w! _6 L& V+ S" x                cur=p;0 y8 Y  ]+ l. @5 @9 I9 o! A0 e
            }
" k0 ?" D! E! z! ^" [1 l3 f
6 s7 V* I/ o9 a! B' r+ e% l          }+ H( e1 y& c4 y* q: N
         while(!s.empty())) _2 \" ~+ u, E
         {( F3 j0 W: Z) [5 m2 M% r& b
            cur=s.top();
5 {' A, f% [+ `: B+ p8 _7 ?+ h             p=GetAdjVex(cur,pre);
! ]- ~1 p# p8 [2 D0 [             if(tag[p]==0)$ T( N, j& e: a! r) c
            {+ [' S, s1 c9 E9 k
                  pre=cur;
6 j1 l$ o& ?8 V9 A  ^                   cur=p;8 j2 I7 T+ Z$ b9 w
                  break;$ e  f1 U) q/ Z" S$ j
            }! [8 k" j5 ?# l* J" y6 i$ z; b
            else
# `# u9 \  E6 R7 ?# n' c             {
1 l, t. w: F& U: i' n                   pre=s.top();2 ?/ P) E7 [( I' {; K
                  s.pop();1 U6 D' q5 }. ?; W: X( m- z! B
            }# F6 u2 X+ y3 [3 a1 h

' V+ C7 Q1 I! X' U  ~          }" a. {" @- n0 A6 e) {
% W+ D- x6 ]& l. N, r
      }4 s+ p" G( m/ a: F
}
' W9 d4 A* U5 t}$ Y1 \' Z; `6 ^+ w9 j) B
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS(), v1 X; U5 N+ Q% B
{
4 M( g7 S8 i! e$ t for(int i=0; i<vexNum; i++)& j$ C' P9 h- G8 m5 F2 X- ]' f/ H6 J
      tag=0;9 |5 V* n8 f5 @( D+ `2 X4 \# g) A
queue<int> q;, [: i2 c7 U; s% O
int tmp,t;4 T5 D5 e4 I' O# P3 l+ E% r$ ]5 i
MultiAdjListNetworkArc<WeightType> *p;5 Y/ L3 i( A3 j; M8 k* m: y
for(int i=0; i<vexNum; i++)- O, r# Q( Z0 N3 T+ Z
{
; ?+ q7 N7 Q7 V) W3 k8 t       if(tag==0)4 C: s' w: a7 h& D( _
      {
+ V: V7 v' F3 ]          tag=1;
' m  j0 t1 t* C3 b3 s( U$ i          q.push(i);- p; j0 a0 X; n3 J: `/ j
         cout<<setw(3)<<vexTable.data;
4 x  ?! h2 z2 r/ v4 n6 _: M       }
. W1 }& \8 i) Y8 ?2 j: b2 f& p       while(!q.empty())5 B! H! Z" u; z/ S3 S
      {
' y. @) E5 L% w$ s          tmp=q.front();
1 l1 J. A% b' y: F% J* h          q.pop();$ X3 g  z$ _9 G8 O7 ?5 W6 K2 L9 W
         p=vexTable[tmp].firstarc;
- P- ?  m) z. m. J) ]3 H          while(p!=NULL). W9 V6 ~/ [8 |* B' M
         {
# L* y; }6 \& L% z             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
# `9 h7 R) }% s2 Y- E* X/ W0 ~$ S) d             if(tag[t]==0)4 a* G4 |4 R& s6 a9 Q9 K0 S
            {$ ?' g/ \8 L9 b6 R" {
                  cout<<setw(3)<<vexTable[t].data;- O) Z+ H8 h- a) }- A2 _$ ]
                  tag[t]=1;
$ u; r* t7 j% q; {$ E& \& z                   q.push(t);
& U. y& P$ c% ]5 w5 r& R             }
2 K8 b: t7 A0 @. A0 }             p=NextArc(tmp,p);/ B) ?, G/ q+ p
         }2 {0 L+ F1 J+ T4 `, u0 m
      }4 K* \) ?  v1 e6 j0 k
}
1 B3 [; E* D( G0 q2 b; m4 [}
% q- M2 }- y9 I/ O9 {# utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
1 C) _# E: }& |9 g, ]* u; b8 y{
+ h$ f  G' V6 z MultiAdjListNetworkArc<WeightType> *p;1 e6 v: T2 k4 p* }( b4 U
cout << "无向图有" << vexNum << "个点，分别为:";7 p" d0 l! l8 e0 Z( d
for (int i = 0; i < vexNum; i++)/ }. C( F0 C; k" i9 E
      cout << vexTable.data << " ";
7 [( s# {' j  f cout << endl;
+ o; b$ o1 H9 s/ \% `  R5 o- o- ^ cout << "无向图有" << arcNum << "条边"<<endl;
) J0 J& A: h: u5 Z! `' m for (int i = 0; i < vexNum; i++)
+ z& p. z+ F8 t/ p' o1 V( Z. h! J# ^ {) I7 ]; g: i2 A. T
      cout<<"和" << vexTable.data << "有关的边:";
* z0 [5 o, q4 m1 j. c       p = vexTable.firstarc;7 ?3 L% [9 C, J6 F( G1 w8 X
      while (p != NULL)+ W7 Q0 J: H3 b4 @! e+ E2 s
      {
% q( F3 x* f  z* u0 [2 W3 p2 g          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";( e! N5 f* y2 s3 y- }: w! {5 K
         p=NextArc(i,p);
' a  j+ S: \7 ]" B7 f       }. Z  {$ G" S* B3 u
      cout << endl;
9 w  J+ b5 B9 L+ o: h& `6 F }" G0 ~  g' r- I! H, R, b
}; W' j) x" Y6 B7 K- M. u5 i. Z- @

1 ^) e  T  u3 L2 V' U4 L  w7 ?( h) u" d( q! k
邻接多重表与邻接表的对比
* T: O! t! {4 o" e9 i( B9 u0 {- K2 `& ~/ N# l
邻接表链接
9 j8 v# V' \5 p- I/ @在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
# _5 Q8 Q* w" N7 V8 ?/ f: P在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
( _: u; W& J1 M) I( J  m7 }( U为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。6 O/ ?3 l) ~) \% F  [
————————————————
- ]* R" D/ }9 B版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! n% Y1 I7 l+ K0 l' q) H9 P原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
+ H& |; c4 y/ L& D4 o8 w, h, X, D5 E/ o& i

5 q/ X4 N- V& F  O# m2 t
2 Q8 y5 q7 E7 v/ D
1 F. z7 E' `+ `; F5 r; \. r————————————————) z/ P  z( `2 d1 Y. S
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。& j4 S& {: x; a, q# D
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
  z% f  C+ G3 I5 z( t
4 i, J9 L% z) ?  `& V# w: [
4 v- [' `' V0 M3 B