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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
) l/ L- }1 n& j0 U$ G7 gdata域存储有关顶点的信息；
2 s! r, Z% `! Q! E3 L6 kfirstarc域是链接指针，指向第一条依附于该顶点的边。3 ^1 b! \( H. X
所有的顶点结点组成一个顺序表。

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;
for(int v=0; v<vexNum; v++)
. l* s- Y9 F2 G/ X3 A {5 E% `5 Z+ q/ s9 W+ \( L
      if(tag[v]==0)0 k+ `4 Z9 z! ~- E
         DFS1(v);
) V/ l5 N( {1 w$ _. O) L6 o2 r }
% L+ t. P& ~9 P! E% n# b! {6 N4 j}
: V' N, h& r0 b3 M4 B9 _template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()& ^9 L5 r5 L! H! z8 [7 `
{/ N, c. Y3 k" O; x& ~6 i5 J
stack<int> s;
: a+ `' X6 J1 L+ U) u5 W int tmp;
4 O5 Y  v7 C* }/ l( h+ s, u MultiAdjListNetworkArc<WeightType> *p,*q;
( \# q/ B1 b$ r1 C( Z% Z- n) V! @ for(int i=0; i<vexNum; i++)4 [8 e! X% J) V* B3 U# n
      tag=0;" L6 m1 z2 K# e7 w6 O) U: T
for(int i=0; i<vexNum; i++)
2 K" o' W, `% \9 E6 ] {
! m4 Z( I1 Q) N: i% D/ [; P       tmp=i;0 p; x$ b# F* M5 Z  O! E
      while(tag[tmp]==0||!s.empty())" ]8 x1 V" p4 a3 j/ t, S4 f2 Q, X
      {4 l1 ^$ S4 z( u8 h5 ^" |5 K2 e
         p=vexTable[tmp].firstarc;
9 q" g9 J8 X9 |$ R# x          while(tag[tmp]==0)7 z$ d$ ?$ d; N8 b
         {1 e" k5 D$ `6 \/ o# O
            s.push(tmp);
" s" t3 [! r0 h3 e             cout<<setw(3)<<vexTable[tmp].data;
7 ~+ L7 f( n4 {             tag[tmp]=1;
, R+ e5 n' A, k' s, r1 D             p=vexTable[tmp].firstarc;3 ]4 I1 S* I% F1 C6 f+ o. C
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
1 V) w# k2 d* P7 d& w5 B$ Y             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);) i) X* d: ?/ x& J* U: K& R
            //cout<<" 1st    tmp="<<tmp<<endl;9 w% ~# q2 N2 R
         }
1 c( o1 V+ O$ y$ x/ e2 L' O          if(!s.empty()), R0 i4 x8 n( j
         {0 L0 e7 {7 t6 V6 u
            tmp=s.top();
% n5 @; B' u3 v  W( X, v             s.pop();8 f1 P' O$ }+ J3 Q5 m- {5 _
            q=vexTable[tmp].firstarc;
; M8 T( ^, C! U: l5 ^- u             int t=tmp;0 [" k0 v% t$ u6 F
            while(q&&tag[tmp]!=0)
/ E: U9 Q! C( _             {
4 A0 u2 g6 V  T# X                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
8 a: Y9 N( I# c7 j3 g; Z                   //cout<<" 2nd    tmp="<<tmp<<endl;8 }- B, u: {1 p
                  q=NextArc(t,q);# q" ^/ e' R9 \
            }# w' U) C6 g* W) X3 {
            if(tag[tmp]==0)
$ d  C3 n0 x  _) h) v. l                   s.push(t);
1 o2 f7 O& y* l6 T/ L  Z) I             ///1、对应上面连通分支只有1个点的情况9 Z) E# g. c1 f( a) S$ `
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈- K) ?; S, p* h  c% E3 H8 J8 p$ g
            ///tmp要么等于找到的第一个未访问节点，
# ]. q5 r( L1 m$ t* g$ \# y             ///要么等于与t相连最后一个点（已被访问过）" ~- W3 j+ \: F4 n. L
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
9 a' k  t2 P6 C: y, C3 _          }
$ v) E! P+ J# ]' J3 X" G6 z" y! h       }3 l  O6 b" e* y! ?
}
8 E0 G$ w4 p  y! s}! n2 v# v7 N" P
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-11 H# _3 J/ p0 L7 H1 x3 D
template<class ElemType, class WeightType> int
- A$ |& e5 f+ C, x5 |, Y( mMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
1 V. Y' \4 {- N9 G& y/ F2 E* a{- _( _+ A, W* ^1 T! ?) r+ l7 _3 S
if(head==pre)
1 ~! V1 X/ M' u/ |       return -1;( b, o8 u& L5 W( ]4 x

/ ~# i* A5 v- ^ MultiAdjListNetworkArc<WeightType> *p;
/ E7 L0 L6 M5 Y6 y+ { p=vexTable[head].firstarc;& `( }5 x  h2 M8 f# q
if(pre==-1&&p!=NULL)- E2 z" L* b! j8 L8 s3 P! S
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
2 s* B! b8 W' g, h/ j, ? //pre!=-1&&p!=NULL1 I! g8 T) x, j! V
while(p!=NULL): l" n/ c2 M' n
{
6 k% ^# ~. d7 p$ [       if(p->adjVex1==head && p->adjVex2!=pre)
. ^; G/ U* u7 X, A$ w1 I3 u          p=p->nextarc1;7 x1 s' m: ^! }1 L. r; n- Z
      else if(p->adjVex2==head && p->adjVex1!=pre)
) m/ W6 L, j. e3 Y& B          p=p->nextarc2;1 ^' n- A& G2 p8 Y9 @* ?# M  K; \
      else if(p->adjVex1==head && p->adjVex2==pre)) T' S) }5 M, y& V3 \7 x8 {7 x
      {& A0 M. H: u- j8 }2 T- X% _
         p=p->nextarc1;' Q  x  t' R% F# I9 q# B8 ?+ c
         break;4 i" `2 z/ ^. X1 j2 ^6 s
      }& T) M/ ]8 @; }, D; V3 C: X7 g
      else if(p->adjVex2==head && p->adjVex1==pre); h/ L* z# m' L3 k
      {
, v$ A4 {2 S3 P. O          p=p->nextarc2;0 _. p0 B5 z; D4 H
         break;% L) \4 F" G; g. R6 j( E
      }
5 j* B8 B3 K& e. J }
( Y- h# ~2 z  ^9 i  V if(p!=NULL)
7 J! c0 n  M) C/ @1 ?% ~ {
4 n* B5 C6 T2 K" t' h       return p->adjVex1==head?p->adjVex2:p->adjVex1;
* q2 I: R" F7 N! H4 \8 f+ q( \ }% }& f+ p7 }2 z/ v, K# \
else
" g* ~" U- T9 w- Z& d       return -1;9 S5 j  E2 }: b4 f9 O  I, [: T* J
}' i! M8 A* {2 r4 R6 L

# @. r1 ?: {7 O/ @( K/ O) H2 w, {3 c/ q" q6 h( i
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
2 ]8 w+ {' X% @1 C9 R8 G{
- D& _) M3 h$ {! I( L; t1 i/ k stack<int> s;
! p* X6 t+ Q7 \0 u% \' F) c; I int p,cur,pre;
& F7 f' r' j( x5 ~) j4 ?' K+ y //MultiAdjListNetworkArc<WeightType> *p,*q;
7 a+ A3 s3 o2 @; w for(int i=0; i<vexNum; i++) tag=0;//初始化2 s, \, `6 y8 D; Z7 i2 j0 V
" A9 b' h; A) F3 |1 h/ m* x
for(int i=0; i<vexNum; i++)
. a8 @" e) ^) b' \' J) B( V {5 B# r2 l4 i$ K; k( H6 E5 c
      cur=i;pre=-1;+ Z0 Z4 W& w+ p' Q& _! s* P' v
      while(tag[cur]==0||!s.empty())/ ]! U8 f: q5 K1 J3 M
      {. w+ {$ H& u$ A
         while(tag[cur]==0)
) L. m$ A) t7 {# m; L$ c2 e          {, O: K- P2 u- ^$ G
            cout<<vexTable[cur].data<<"  ";
) }) k  B# g9 f+ A# N" B             s.push(cur);1 ^3 C1 y, r; b  O
            tag[cur]=1;
" y, l" P# _* w) h( c             //初次访问，标记入栈
# B* k: l, n8 ^* I$ R+ ]; Y3 P! `/ q# `" s" Q
            p=GetAdjVex(cur,pre);//p是cur的连通顶点5 U' M5 V; q- R% Q
            if(p==-1)  l5 E  c( u& U& b/ t/ d$ `
            {, B7 V3 n: R' H! _: X/ f- ]5 S
               pre=cur;s.pop();! E; A1 y* _" D% j  ]9 I2 ]
               break;. J! u: @% o/ M* w+ l1 f  n- l8 s
            }* U# @, e# j* L
            else; M3 L9 z5 F8 H
            {
3 p  p. a: z( X# K" g                pre=cur;
) `5 n3 [. g5 M8 Q                cur=p;8 R; q* r' k2 d
            }. Y9 K' }6 u2 G; f2 A" |, T4 `
1 p4 r1 S  M5 T
         }
6 K. h0 y( ?" @! C" D9 d, N* x          while(!s.empty())% }% D' s" q' X' T+ g2 h  S  V
         {
. e; ]' G+ t% B: U$ V8 o, D             cur=s.top();. H. o# m' l: w4 e7 X' I5 X: A
            p=GetAdjVex(cur,pre);7 P& d& }) H3 `- t# A# e
            if(tag[p]==0)
3 F6 ^9 s- l, z6 d! V4 U             {
6 ~' R/ @' a& m% X, m                   pre=cur;
! r% p3 c4 n+ I5 d4 @5 |5 |                   cur=p;6 w4 y6 B- K/ y0 p: e" u% w
                  break;( J, T5 Y3 X. S& X0 p3 r3 C8 P
            }/ n0 [$ B( J. y  c. N2 w/ i
            else+ L" I: ?" Z. H6 L5 J2 B" t
            {
  ], F* w- n* |* f8 {+ p) M, i                   pre=s.top();
; A" R& s6 B0 i- A+ Q# Y                   s.pop();
# x5 y- I( d9 Z2 o  l( J             }
4 K' d: z, v& X6 Q5 n# N7 k$ B% c  o! k& p
         }8 Z9 f: X1 R8 M) X' E9 X

; ^+ P+ J) ^2 D$ R3 o       }
, Z! e: T' M* m: W0 ? }* q5 @( ^, V) P
}. l, y5 y3 f: A0 M% ^
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()* a) h' g# ~4 [4 o# ~; [! k8 u$ b3 i8 Q8 z
{
# Y: H4 X4 _! p0 q+ O' n6 p$ x for(int i=0; i<vexNum; i++)/ J! R$ G6 j+ A
      tag=0;' u# c- q% {" S2 u" P% s' k
queue<int> q;
$ E! r2 U6 r! ]' M int tmp,t;
+ ]1 _/ [" P7 r' i MultiAdjListNetworkArc<WeightType> *p;! @, a0 f1 V5 F% c$ W5 }+ H  F
for(int i=0; i<vexNum; i++)
% L! N8 P* \1 f! Z {1 x- ]( s6 n: k) \
      if(tag==0)
$ U5 |) b/ \6 \( U       {7 ]. E9 I9 f( d7 S
         tag=1;% J$ N) r6 x0 M/ l
         q.push(i);0 I0 x% t0 C0 D2 ?  a
         cout<<setw(3)<<vexTable.data;
, C& d) @& @5 s% @8 ]       }3 i8 a, `1 r/ Y+ y- S, G5 b
      while(!q.empty())
- X! m/ R# ^1 ?# f2 p       {; u* o1 r) m& T) W0 @; w* y. H
         tmp=q.front();/ N$ Q& n8 r$ @
         q.pop();7 S+ h3 M4 h: h% t
         p=vexTable[tmp].firstarc;
0 `9 Y* m5 y# v          while(p!=NULL): L/ C9 f, ]7 T. n/ c
         {' K8 t2 f* Z& m2 s1 _6 {& U- }7 V
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);( U- P6 }& J8 x2 U
            if(tag[t]==0)
$ y. W( t. Z& R( e             {
. v5 a! ~: N- N                   cout<<setw(3)<<vexTable[t].data;
; I; X- g, \4 D" l5 E                   tag[t]=1;+ S8 k0 n6 f9 t
                  q.push(t);; B) M3 z  [' n$ j: H+ M
            }! M1 Z* J9 t8 Z7 \0 N
            p=NextArc(tmp,p);
: M& f5 U+ q: ^0 k          }3 ?; h" {2 Z- v' l6 J8 o- n( h0 i
      }
5 H0 m/ ?' M& p6 z2 ~ }
0 ?) A+ G2 c- Z}: v* T, Q" b3 k7 [
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()( K) r* c* E, M9 w5 G3 n7 _
{
! w- i. V# ?, W! t9 g2 I. k MultiAdjListNetworkArc<WeightType> *p;
5 x* C  e6 S2 H cout << "无向图有" << vexNum << "个点，分别为:";& t7 t4 ^2 ?, v: G' P
for (int i = 0; i < vexNum; i++)
/ w8 E/ T4 X4 P4 k  f% w' v& J       cout << vexTable.data << " ";
  N8 D  I* H( `& d/ |" y# U cout << endl;
1 x0 A7 l" y( Z( m+ x cout << "无向图有" << arcNum << "条边"<<endl;
: x3 R1 @$ W. W+ ?' c for (int i = 0; i < vexNum; i++)0 F. r! {, {# v; o( F- R8 e7 g
{
  z2 j1 n3 [& I7 B- X/ P       cout<<"和" << vexTable.data << "有关的边:";
1 N" ]6 f1 d4 |+ h: N& g2 Q; f       p = vexTable.firstarc;
0 T' l' s# Q% \2 V/ \3 _       while (p != NULL)6 ]. b; W+ ?2 j/ T+ o% C8 g
      {
; }% e) M5 A9 F1 B' g6 X          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
8 u: r1 M" g' W6 _' d" ?          p=NextArc(i,p);
' `" y, P1 D5 a  b! r       }$ i) s0 b/ \% N: |
      cout << endl;7 @8 g) M& w" U& l, ?
}. a: G6 c8 n. U
}
9 H3 y% O% R! b- U: I- ?( }$ z  P. S8 ^
4 l9 h8 [4 f' f/ b3 M' w9 q
邻接多重表与邻接表的对比
9 w) x4 O  t$ x" ]5 H6 C4 H& [# R/ ]0 n% y( f
邻接表链接. {( d- I4 Z8 m4 W. k( f) I8 V
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
; o* L5 i% Y1 ^" f( O) g$ I在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。( N& M3 U* H7 l+ }" {! F! o, d
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。- E$ V8 c" H8 y9 s# ^
————————————————2 n! I% H9 F' Y- K
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 Q) E% [! z" E8 }原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
7 l* b- Z8 R* I) y# |* }: w" ?2 K$ s( c- F. l( z
  {* X9 O0 @2 ?$ O" ?/ x, C3 d
3 }; B# f# w1 \; G+ d; q9 |. E
2 }+ Z, \' `% @4 w
————————————————
. v- ^  e* ~7 m" \版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ T' z2 l( q/ p原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958! {, [* ?' A2 n: T* O0 [

) C9 ^9 `. D7 K3 e! W5 u0 q' p4 Z5 Y9 U