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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
2 J/ u; F8 l& E' I" ^: i) ^1 vdata域存储有关顶点的信息；
# I; x0 y8 V7 ]! `' g, vfirstarc域是链接指针，指向第一条依附于该顶点的边。! m! T3 Y% r8 z z5 t2 y: d& @# K
所有的顶点结点组成一个顺序表。

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;) f0 g! t) j/ M8 f" P/ q
for(int v=0; v<vexNum; v++)- G6 D) J# L' m, H8 K
{# R2 @5 w) E; v1 V/ M% u+ [
      if(tag[v]==0); O+ n3 t3 U1 W0 _& e2 c
         DFS1(v);
4 q/ x0 `" D! f2 X1 T5 U }. C6 G; |8 O" N/ ~4 A/ K
}7 @* }" y! S3 Q' X* w4 i
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()$ k) P& m8 ?8 O' f& S- D
{  d, S. ]3 v% x, [- y
stack<int> s;
  U& k( R& y, r3 U5 m! m% i int tmp;
- t0 u1 ~3 c0 t8 J MultiAdjListNetworkArc<WeightType> *p,*q;$ S4 ~- a% O1 [) d- I7 a# j1 Z
for(int i=0; i<vexNum; i++)$ n7 R. g& W( A  e. S/ I
      tag=0;$ I; B$ r* L: t) M, `/ `8 t! s. n' A
for(int i=0; i<vexNum; i++)3 B1 Q6 d) @( T) l
{$ J8 w! Z* m  _+ e  p) h( Q
      tmp=i;
7 {; v; e8 j- _( J3 S2 N       while(tag[tmp]==0||!s.empty())& r- S* ~6 ^- g, K) h% ?: |
      {
! M: j2 d6 _/ Q4 u  P( \* B! A& s          p=vexTable[tmp].firstarc;
" I" D7 G1 A$ O0 b# Z" _! X          while(tag[tmp]==0)
% \  i+ G/ j) J! \# P  y# i- M* y          {' O' B" v: L! `& [5 s
            s.push(tmp);
# f4 ^& Z: s$ Q1 W* P, T7 h             cout<<setw(3)<<vexTable[tmp].data;
9 {! F* I% a) b/ x* F6 z             tag[tmp]=1;/ V: b( q- h! E. s2 h& ^
            p=vexTable[tmp].firstarc;: [, f8 `& ?0 V3 i7 Z) a: g
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
7 u1 d* R5 V9 l, t& F             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 z1 A5 z: z2 G' u" [) M             //cout<<" 1st    tmp="<<tmp<<endl;
" V0 A- O& U2 O5 J          }
+ n' Z4 D; m: P! i& Q0 A          if(!s.empty())$ L' O! f4 F0 N& y7 U8 _
         {2 u' D# A# t) Q
            tmp=s.top();
! y7 [% f" W) q             s.pop();
$ k1 ?/ W) r' y             q=vexTable[tmp].firstarc;  A6 [+ k# q+ }% i/ s9 l
            int t=tmp;+ L! l8 D" _! r/ f5 d
            while(q&&tag[tmp]!=0). i! A: O$ L! d
            {
* @  j& Y% ^% |0 b; m4 K                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
7 [1 {! F! d$ R9 n% l# E" M6 h                   //cout<<" 2nd    tmp="<<tmp<<endl;# _; E) @! \3 m; w& }! E7 b7 |& p
                  q=NextArc(t,q);
; G4 j: N3 i6 D" @             }
6 |$ y, {" ]' x3 ?3 T4 t: h4 P/ H             if(tag[tmp]==0)) p$ w% |. x' b* d/ }0 h
                  s.push(t);! _* ^6 m3 w6 p+ |/ g# ?% X. @
            ///1、对应上面连通分支只有1个点的情况
7 y- B, `7 D: @% V9 ^9 t* _             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈/ m: k0 r( u" u
            ///tmp要么等于找到的第一个未访问节点，  M) U  J$ p  Y* e# G3 w7 \
            ///要么等于与t相连最后一个点（已被访问过）
- a' a9 Q8 b* |6 G; N$ d             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点9 R: ~! |6 ]( l/ ^
         }- S5 F9 P  _! o
      }
6 T6 F' {. ?: u2 G+ O; I/ F }
" t9 z# H- b: ?. M) m}. @7 ^2 h( K/ a+ |
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
6 l! k' g5 F- D0 ]. v3 s& Y: p# Itemplate<class ElemType, class WeightType> int
7 K# ~; |3 Q4 q% y; s3 S7 }MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
/ R# {) C: g2 g9 G5 }- Q) C, ~0 F{& _/ ?. @' |7 b. ^, h: \1 U6 Z
if(head==pre)
1 R* N- \! C  E       return -1;% X, {1 Z6 \, h& b$ N

. p: \7 b4 f9 q8 f  r4 {" K MultiAdjListNetworkArc<WeightType> *p;
  ~  n- p$ t0 t, v+ ] p=vexTable[head].firstarc;
- e) _) [. }  \5 l1 N if(pre==-1&&p!=NULL)
3 H3 T  U9 z5 ~, S3 S6 R( s       return p->adjVex1==head?p->adjVex2:p->adjVex1;
; s9 L0 U3 E6 Z% O- @5 O2 D( f //pre!=-1&&p!=NULL1 E% j( O+ l6 g0 ?$ B# J
while(p!=NULL)
, R3 c- h, _# B {
* P8 [4 V: L2 [5 D0 B+ V. G4 C       if(p->adjVex1==head && p->adjVex2!=pre)1 i) }+ G4 k2 E6 u
         p=p->nextarc1;
  e) u: x8 s% B1 |4 C1 l- k1 [       else if(p->adjVex2==head && p->adjVex1!=pre)
3 m8 H) ?- V1 B          p=p->nextarc2;
8 G! A" w$ h* y; J& y0 g& P       else if(p->adjVex1==head && p->adjVex2==pre)' y6 J8 ^; a7 c2 ?. ~& }+ C
      {
( c6 |4 d0 Z/ E7 h# i          p=p->nextarc1;
6 v. M, `; Q8 _- s          break;
) @5 V: k3 o( [1 t) R) `       }
( y. A0 F& r3 H1 f8 F1 s       else if(p->adjVex2==head && p->adjVex1==pre)5 W& I. y5 ~; X8 n& w2 r
      {
3 _1 ?  A2 G% H7 v0 r3 v. V          p=p->nextarc2;
) i0 S. ~3 ~) O- N) T) u2 O          break;
/ F- S8 P+ D7 e1 H7 a3 |; R       }" L2 C2 s) a0 Q0 B
}6 o' w, ]. J5 s' q( s7 N
if(p!=NULL)$ L- m3 {+ D% z0 S5 C2 O
{7 s/ K/ N9 N: V& x
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
2 A$ m+ t% r# a. w9 W7 P }" N" Z+ x  K$ ~8 H" W2 t
else3 }" f7 Y6 [7 _4 E1 l
      return -1;8 c* `6 D1 x# v' Q) {0 S
}- g7 F4 F- V& a7 y* A1 r
+ C6 i+ M  z+ D$ ?2 T/ o
- n# c5 d( T* {" k: W' ?
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()+ b) u2 e0 S- Q
{
* j4 k" X, ~$ M% D: U% J stack<int> s;
" z* v) @$ X1 M% a  U5 u, [ int p,cur,pre;
/ r( \, Z* V% C( M5 u //MultiAdjListNetworkArc<WeightType> *p,*q;
, A6 W6 H* {+ i) n+ ` for(int i=0; i<vexNum; i++) tag=0;//初始化  V$ M) n6 R; `/ R
& G- y/ ]7 l" ]) ?/ u" }
for(int i=0; i<vexNum; i++)
8 N5 Y4 ^8 j) I- I; I {
1 `( U8 R. @9 a4 Q4 t0 \' \       cur=i;pre=-1;; n/ E6 P$ {1 @( N/ D% T+ e% g7 k
      while(tag[cur]==0||!s.empty())
: D) {* l) K6 x- t, P: c       {2 `) v7 g+ ?3 K  U$ s$ R1 a
         while(tag[cur]==0)
0 b7 W- ?; m' F; \+ g1 q1 Y          {9 U" c. z  W1 I- r, o# z& x
            cout<<vexTable[cur].data<<"  ";
+ t( h4 b6 ^/ f5 u6 ^             s.push(cur);! d0 J/ b# L& |# O2 j
            tag[cur]=1;7 X5 G( S. w& A( y# c) J! _
            //初次访问，标记入栈: F+ v' K1 z7 G

: p2 _; e/ `8 ]7 E5 T' P             p=GetAdjVex(cur,pre);//p是cur的连通顶点
, U- M# H  }* @9 S4 r9 P2 w             if(p==-1)
! ]3 [1 ~1 d8 d& Q( _1 L+ Z             {' i) R) g0 [( D6 g2 \1 b! r" H+ i
               pre=cur;s.pop();% ?1 J- Y0 k! W
               break;- I9 b) H8 J* h% t) n0 o
            }
6 g, F- @5 q4 Y1 l             else# P5 h8 t7 ]; }$ C9 U4 v6 L& L
            {
2 N( r. ]2 U0 a6 C                pre=cur;* G6 M* s! t5 M# X9 D4 ]
               cur=p;
6 ^, K+ E2 i8 ]3 V! f! E( R! n  n             }
- d! X" v3 H6 ]
+ W6 L) f( M; W2 j          }
- J& p! J7 V1 \% ?: X/ v; A          while(!s.empty())
1 u# F5 a6 S" I          {
2 _6 d& q5 t3 ~2 ]             cur=s.top();
: _' w/ [7 t& k             p=GetAdjVex(cur,pre);: l% {+ f/ D5 f7 R- k6 B
            if(tag[p]==0)" o3 Q0 C" B. l
            {
                  pre=cur;) j4 g$ u7 D0 I
                  cur=p;
- v3 `6 N+ P7 h9 N7 g3 o8 b2 N' W' K                   break;! ~4 V4 p* w3 e* ?! M2 C$ z% |
            }3 E- y# L- k' q5 v' S- B
            else
0 W$ ?7 [4 R6 W, A2 d" \/ L* z/ U" L             {
1 ]( f# C: ~- z+ _                   pre=s.top();' c, b  `0 R; l: L7 J* p+ w% E2 N7 J) J7 a
                  s.pop();
& g1 m8 y& U4 O5 \6 h$ N             }
0 E6 M1 Q& q7 i9 `2 S2 r; e( m# ]( l3 |$ [- W, U6 G
         }
) t" W+ O: U( g! T
! Y; c" Z9 o- P1 Y4 e) N       }; h8 q9 L# \7 u# B/ r* p
}
7 p7 t& x( r; P}. t9 F/ b2 H9 c! M+ M" g8 Y
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
; {* s. i# i( y* n  l2 T' A{
6 y. I: Q( E7 z4 K0 x for(int i=0; i<vexNum; i++)
/ Q3 ^" y0 \( ]# b: H       tag=0;
! i# m' y* Z2 J0 m. ? queue<int> q;5 t+ ]8 ]( ]% s) v. o
int tmp,t;  [/ W- j9 Y8 b2 |( W$ c, E/ Z
MultiAdjListNetworkArc<WeightType> *p;
& z! E! i# Q7 {7 }3 Z/ u for(int i=0; i<vexNum; i++)
2 e2 a& C' g( q  ` {
* D4 U+ a0 N4 y$ t* }4 Y8 s. Z! {$ j       if(tag==0)4 c3 b! x6 T, S0 y/ ]+ t. U% z
      {
; }5 x% S# m# f; D$ ^$ R          tag=1;
' L; e! i8 d, |& s          q.push(i);
: i# x1 C8 N- s' F& l  q1 O: }          cout<<setw(3)<<vexTable.data;. ?$ s' P0 V9 d$ ]5 j
      }. u5 g0 v4 r: b; H8 D, i
      while(!q.empty())( {  [' t- w6 _3 ?% b+ S4 @! _' ?
      {
0 T/ u' V2 R* I9 h& n. {- t+ }          tmp=q.front();; P. K) K' g2 j2 m: H! [% G
         q.pop();  M, ^: _4 L( k5 W+ m  ~
         p=vexTable[tmp].firstarc;$ ]' H$ D( ?8 ~
         while(p!=NULL)
7 X- h" T' T* h  j! s  i4 Z          {: c' q+ e) o/ c
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);' Q; p; v( b; _; T! A
            if(tag[t]==0)4 ]7 @! B/ Q5 S6 N$ R
            {
* T7 m: G9 |% d7 o! J$ J                   cout<<setw(3)<<vexTable[t].data;, v' l/ o: ~& Y3 O4 \
                  tag[t]=1;/ I# `7 J; O+ `5 A2 Y. y
                  q.push(t);
9 K" B7 G  e* x9 t             }) L- ^, V3 j6 d
            p=NextArc(tmp,p);
' C  K) c, k$ C( j          }  Y  ^  x0 e: T7 R% U% G  J
      }
+ G6 N3 s0 P- G) g }
$ I1 I4 P8 x( o- `% |5 T- E}
4 K/ w6 f0 t; Z2 L6 ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
9 R7 d7 @* d  @1 H5 L- y{2 i7 j' h9 z: x
MultiAdjListNetworkArc<WeightType> *p;4 Q- r) b( S- m+ P! h# [* C; o
cout << "无向图有" << vexNum << "个点，分别为:";
' ^0 b. E. S& t for (int i = 0; i < vexNum; i++)
2 [3 n5 @6 S& T0 l       cout << vexTable.data << " ";
/ `5 Q2 v# X* u; A- S cout << endl;
1 L$ _" F, [% u cout << "无向图有" << arcNum << "条边"<<endl;
/ j0 t7 P# N- A; B" }6 q/ w for (int i = 0; i < vexNum; i++)5 s4 Z5 O' p1 c
{9 t3 |+ s9 F4 A1 g4 H  z+ L, q
      cout<<"和" << vexTable.data << "有关的边:";
, z. P, M3 W1 M# B       p = vexTable.firstarc;
% P1 n: q8 @0 x. x6 g2 S9 L       while (p != NULL)
! I4 }/ O5 [6 o0 C0 Z3 U       {
% \6 j5 M/ G) q1 U: n5 u          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
# L- n2 e2 Y  s1 |$ X          p=NextArc(i,p);
" l9 U5 b7 o+ [" F: z. ?( M       }
' c+ }8 w9 S8 T  B& b' d( w4 Y       cout << endl;) \, X/ X. R+ r$ p* o; d/ K( J
}' Q; _( w7 N7 n
}
' I8 f: G) E8 v! _: T' l" i3 O9 _# ~6 r, m- q
' a* d! L) x) E* c
邻接多重表与邻接表的对比, v& e  \: F6 W) s  W# q2 S1 {/ t6 N

( \- ^& ^3 q5 Q9 I" N邻接表链接
  p! \* G0 }  M  Q在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。1 Z( K: P0 B4 W: i) M" b
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。; K8 O& k1 U5 d
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。0 _: B7 J/ _) K6 j
————————————————& i# i% X/ Y# F1 q3 A( G2 a/ l$ ^
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ o/ j/ _( D8 u) T+ z原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958- b* K/ P/ _2 L! w# ^( u( F$ C  w

1 j9 [* ^+ D. X* E5 g2 B2 f5 R/ n4 l* A( d& S& t
. U* G" Q' b; K4 T6 Z5 F! o3 a

& n, p( o( O4 @& M. U————————————————' s2 P* \9 q! w% ?( m3 Z
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。- W- A8 A  G* C+ H- L' Q
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
. J; w5 r0 W9 V& w( |( e
' h: t' D7 d, J% C+ F4 J
+ X. C" r& @, y8 k5 D- [- s% K