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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
5 p9 ?4 X: Z4 U" wdata域存储有关顶点的信息；( s, k1 }, q/ a# p$ r
firstarc域是链接指针，指向第一条依附于该顶点的边。# G8 f& i% y- J/ e
所有的顶点结点组成一个顺序表。

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;
! g, f! s  ~: k' G* ^5 j: r7 a for(int v=0; v<vexNum; v++)
3 u; Z4 H$ l2 K; w {
/ ]8 E  ?# E# g& `' Z3 o8 s       if(tag[v]==0)
, f) L6 E/ b& f/ G" r! u4 D          DFS1(v);
/ Y0 I3 h" b  t4 t1 I }: s9 w9 V3 R9 U! `) E6 f
}% s. O* o' ]& t
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
9 x! k2 J8 x2 Q4 }+ |: e{
" }  J5 V  s( \: n: B' V3 Z0 J stack<int> s;) E) z* O* {* g" J% H
int tmp;
. m' Q0 {$ q: F5 i MultiAdjListNetworkArc<WeightType> *p,*q;
5 \' A# z6 A5 b3 |7 t for(int i=0; i<vexNum; i++)
3 ?& v* @' d0 ~" U: }( a& _4 z2 s       tag=0;7 ?9 X* Q1 {4 d7 d! d: Y2 }
for(int i=0; i<vexNum; i++)
7 Q5 E; V. y% {5 B {, t0 w7 e- G  J% o: B; U( {
      tmp=i;
. J, ^1 p# w! E0 d: k9 b       while(tag[tmp]==0||!s.empty())  g3 W! V0 K: I7 w
      {) o8 n. G3 B3 Y8 P4 `4 l5 x# r
         p=vexTable[tmp].firstarc;1 I1 y/ j9 }6 O6 s7 k# A" d: d
         while(tag[tmp]==0)! _( A: ?2 n  N4 z( |
         {- b& A  Q1 s2 i8 x0 e
            s.push(tmp);
! @2 B, N5 ^2 @, l% [6 x3 }2 b             cout<<setw(3)<<vexTable[tmp].data;
  E: y" ]1 _* T4 G( z, M             tag[tmp]=1;
' {- o$ C3 F$ ?$ s" ?             p=vexTable[tmp].firstarc;
6 f3 F. ]1 w6 c" v1 P2 q0 M/ }             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
5 H( {/ H. r* ]/ N! H5 l1 x3 c             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
) Z4 B* k7 }7 j+ [             //cout<<" 1st    tmp="<<tmp<<endl;3 s# n- l$ l% E5 x; y$ `& p  t
         }
9 ~/ H6 G% ?9 b7 Y# D8 U) j          if(!s.empty())
7 u; g  [5 w' U7 B$ Y          {4 n& e' G6 [4 w- W' y2 o
            tmp=s.top();: B4 t& a; Z) m% R# R0 q
            s.pop();
8 Y% q' d2 Q6 Y& E( Q5 o* S1 u             q=vexTable[tmp].firstarc;% p/ l# [3 O9 U6 n3 a1 i
            int t=tmp;
) l% r: G) O# m. I             while(q&&tag[tmp]!=0)
+ q3 m5 O3 E8 y1 U             {
+ h9 Q" `- l+ i                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);3 ?1 @, e& l) W0 X
                  //cout<<" 2nd    tmp="<<tmp<<endl;
+ t1 Y+ |  o! h) c                   q=NextArc(t,q);% n: [3 W$ s, J. H! |8 l6 l
            }
6 D, S6 R! f. m( l             if(tag[tmp]==0)) D$ Y2 z+ K9 ?" _6 o
                  s.push(t);
" W7 e4 P  y8 q; `             ///1、对应上面连通分支只有1个点的情况# k6 ?5 F7 ]! f- Z: h8 s# V8 W
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
, o6 q& x" r1 D- G0 S! g             ///tmp要么等于找到的第一个未访问节点，
8 m5 |1 H# \* {- t" X5 m             ///要么等于与t相连最后一个点（已被访问过）
( {5 N6 v: H0 y, K$ u) \7 \7 \             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
5 ^5 x6 [: j; u- s# b, m          }
. _" ]( A, W1 W4 d& o       }. v* Z4 E, S$ B
}( v0 P$ v- G% X& \' `
}
+ Y+ Q2 ~3 t0 x//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1/ L' h5 u- l) M/ C! h! t
template<class ElemType, class WeightType> int3 K4 @6 |* k( ?$ W- W2 t
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
) R; C: C3 Z# m$ v4 s. L{1 \- S: N6 y7 [# c# H
if(head==pre)
# N4 K; T  e& ?7 J: C       return -1;
3 g9 E# K1 A9 O7 l& |# ~1 J, B0 B8 Y, M! q" j, O' V- K1 U5 F. r* Y
MultiAdjListNetworkArc<WeightType> *p;
6 j7 [7 ?5 ~: z/ x' i" C0 F5 c p=vexTable[head].firstarc;
: [6 t! K; ~1 O/ l% I if(pre==-1&&p!=NULL)7 Z8 A" h# I/ {/ {
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
  k$ y0 c0 k2 Y& r, d6 v( v) ^ //pre!=-1&&p!=NULL% E+ K+ Y- M0 x" b
while(p!=NULL)
/ R* h, k' o) w( C1 a" U, a+ f {
; z6 L* I" Q: o" V2 h% u! o       if(p->adjVex1==head && p->adjVex2!=pre)
. g4 Y' V; s: K4 |/ w, ~          p=p->nextarc1;
5 {+ w0 K5 ~9 Y  `2 G; L7 j       else if(p->adjVex2==head && p->adjVex1!=pre)
% C  E* T- y- m# {9 G          p=p->nextarc2;
; `$ ]1 s5 `- |; i3 \* C0 J8 i" s       else if(p->adjVex1==head && p->adjVex2==pre)
. y8 u8 D+ [% e5 G, u! R7 W       {. G- w" G5 a" |
         p=p->nextarc1;
& |8 n% i0 d! [          break;- C* w/ F. L5 ~: @: F
      }
, Q1 T( k0 T* i; X* f  _       else if(p->adjVex2==head && p->adjVex1==pre)6 e% E/ @6 M. }& [! ~
      {
6 K# o  K+ U5 s4 V! {" {4 o          p=p->nextarc2;
: a) z; O" C7 m6 I* w+ G4 e+ s          break;- G3 A1 G+ ]7 a3 h6 U# s
      }
# p0 r6 [: ?& _ }' |, ^5 H6 \2 Q4 R- {2 `# v
if(p!=NULL)+ ?9 G4 _5 U0 B3 P- F1 X6 G
{
1 Y9 i2 y8 K! W$ M* o3 I       return p->adjVex1==head?p->adjVex2:p->adjVex1;4 D: C5 {* S. |, T* u' \0 O) `
}; {+ u5 w, F) w6 j/ q+ Z3 j. G+ h8 P
else0 o$ ~4 V  w5 G, n% g2 U. x$ S
      return -1;4 ]' u  |; ^& w5 `
}' G9 F9 P% u+ z" U  R* C# x

" Y% j* d# q2 a/ \
0 w* [- d2 A9 e+ u5 xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
2 m& V* I) M6 v6 |) F( _{
# P: z, q7 A( Q% a stack<int> s;
/ w$ f+ k( Z7 \4 F7 ~( |* a6 k int p,cur,pre;
) l+ ^% Y2 l' ~ //MultiAdjListNetworkArc<WeightType> *p,*q;2 Q* j/ ~9 A9 y3 S; r1 @; `: U
for(int i=0; i<vexNum; i++) tag=0;//初始化: \" [- V6 O- p- T2 s6 Q
2 g( h0 l# I0 ]2 Y$ Z: j8 Z% x
for(int i=0; i<vexNum; i++)
9 {- l/ j8 k; D& s' D {" D; w. w8 r6 g
      cur=i;pre=-1;% o. L7 S( a1 n1 `# d6 h
      while(tag[cur]==0||!s.empty())4 M) y4 p3 K1 j  w8 y8 X
      {% @0 w; y! Q. C- o  I% p7 s
         while(tag[cur]==0)% @+ k- f% i+ e7 p  ]6 f
         {6 ^9 {' n5 ]* C6 }0 B  G# |- h; h
            cout<<vexTable[cur].data<<"  ";0 J7 X6 d5 h; z! f
            s.push(cur);
3 r+ {3 l% N' s( K) D# l3 o             tag[cur]=1;
  a8 y$ k* b0 O2 x. b! u             //初次访问，标记入栈" z. `8 \& v4 X& V  p( {, |
, r: F4 j8 K/ k5 @2 y/ C
            p=GetAdjVex(cur,pre);//p是cur的连通顶点+ l8 l: m% r- }+ a5 D& |
            if(p==-1). N7 G( s; D. Y
            {
. D; f6 m: }5 B4 v3 O" k                pre=cur;s.pop();
3 ?$ [( G0 }3 B                break;+ k: M) G3 C9 A2 y" f
            }. ]$ g  X" g3 G6 u2 @+ F1 R1 p
            else
- N2 V9 ~) [9 r! J. z2 Z# N4 P             {1 Y% t- N4 u5 ]9 {! W- A
               pre=cur;
5 }, C9 l1 W; ^: K0 X                cur=p;+ H0 j, A) `9 Z% a, r6 _# S
            }
, v, p0 |' v( C" r. C# V
" b. {' Q! `( ^5 Y          }6 g5 o; C7 I" u% d* r
         while(!s.empty())( H# m& \7 a, k. Y
         {
; s7 }4 S2 C& d6 Q0 ^3 _4 l             cur=s.top();3 s. @- i) c' s: T% L$ u6 w
            p=GetAdjVex(cur,pre);% j. ]* A4 p" _, X/ s. P9 y
            if(tag[p]==0)
( Z' F% M3 w  y             {/ T# {, }. ?) P3 k: J  d1 g) H
                  pre=cur;
; y  w1 Z$ G$ [4 `, R                   cur=p;# s9 w7 v% X% ]% N
                  break;+ D3 e; w& s* `% G* p  `- d+ f
            }
3 P7 j: x( p2 i$ W" [" E: u# M             else" n; q: A" w8 @  @# d3 {
            {
2 P4 ]' F4 `* S5 Y                   pre=s.top();
" L+ D3 Z# u' e- _# j( }0 A                   s.pop();
( N0 t% @9 B' Q+ {1 }- @( t; Z             }7 q5 C; b* c% @: H- e

% \# b, k" t. T: G( }( ]          }" }$ X" T5 a+ @* Y% w$ O* _! G8 s

4 H% y! [. a) o4 i# J( b       }
( R: J/ @+ D7 m/ h8 e" g3 F9 z2 R8 A }3 G3 t+ m7 C- G& g, ?4 O
}- U0 [) V; g4 K- m2 C
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
5 P4 I! ^& E) `( v. g# u{
7 c9 B4 H2 E+ Z1 a! }: T7 \  V for(int i=0; i<vexNum; i++)2 a. E3 O/ L3 }/ f! }
      tag=0;' [8 W9 T  L' h$ r: `0 S1 w+ \! R
queue<int> q;
. G# j/ K0 M. V6 U* v int tmp,t;
, b+ }1 U* M3 i. ?5 k3 U: u MultiAdjListNetworkArc<WeightType> *p;8 l$ u% Z" k. B
for(int i=0; i<vexNum; i++)& B- O& g. J+ k2 w5 u8 f' r
{
2 d) ?0 M8 {: \% [! [/ W+ i       if(tag==0)
5 b% f! Y! R  J7 ?' M! G4 x       {% b$ z( T. E! i
         tag=1;
; `" c& }( [6 w# M1 m7 a, e: z          q.push(i);! k3 e2 r8 z7 K3 s: _
         cout<<setw(3)<<vexTable.data;; E  `( Z1 E. W/ ^! N2 I3 {# c
      }
/ j$ Z( a. n& B& t0 ?       while(!q.empty())
6 A4 C  n8 _, {- \# M; @       {
  D0 ~3 O6 A6 r8 S9 w! z          tmp=q.front();
. S' s2 a5 O, n) B- O1 ]$ l3 V          q.pop();7 b: h- v$ c4 S8 D2 u3 l$ S, W
         p=vexTable[tmp].firstarc;
5 r4 @$ v, N! S$ \: Z8 x0 W; W          while(p!=NULL)- {& N% K. I6 f
         {
" R2 h) y! @" z$ P5 m4 v: _             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);5 h& X8 u! R, {/ H9 H
            if(tag[t]==0)  H2 B9 P4 y( I. v3 R6 i* e( c
            {
9 y5 r3 o7 U' n* S                   cout<<setw(3)<<vexTable[t].data;
8 ?" e2 }, o, t" Z                   tag[t]=1;. M2 J1 o8 j* J) F# q
                  q.push(t);5 L0 B" U2 o. T" Z$ H
            }
* x. U' H) ]2 u             p=NextArc(tmp,p);
7 w8 {; c2 |2 R7 b2 V+ X7 s          }. |- k- ^* d& t+ g9 U
      }5 e1 v: |; S4 t1 S  N5 Y5 x
}
& k/ S3 B3 N( @, F! t8 V}  N6 Y) `7 \* f+ c  x+ i
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show(): o, w8 @4 D+ E5 u% q* s
{
, Y, {9 [; D/ V; d9 _ MultiAdjListNetworkArc<WeightType> *p;
6 B+ y) U; w3 d; Q+ w cout << "无向图有" << vexNum << "个点，分别为:";
- @; @" ?  k5 t. b% S0 Y' y for (int i = 0; i < vexNum; i++)! V  |. x0 G. u7 Z
      cout << vexTable.data << " ";" g6 o9 J2 Y/ F' @$ [
cout << endl;
; x8 H- A5 Y  V! o cout << "无向图有" << arcNum << "条边"<<endl;7 F2 L0 K6 k" C
for (int i = 0; i < vexNum; i++)9 ]- L2 V$ ?; i% d: E
{
7 \9 M4 m4 S" a       cout<<"和" << vexTable.data << "有关的边:";& U% P1 A3 b- f# Q# u' T$ f
      p = vexTable.firstarc;
3 C: _, v! `9 X4 P$ g       while (p != NULL)1 \5 m2 ~) u3 l# ^5 T
      {$ _" {- U2 [4 ]
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
; \+ y( q1 K$ |7 I9 z2 J2 X          p=NextArc(i,p);
# a4 O  s- C2 i, ~9 }       }
! P. N/ z6 E. j  B* J: W       cout << endl;
! l5 I8 X% g/ W0 n1 Z }  t! D8 ~( @# }) T* o4 L( v8 c% B+ h
}& ^* i+ R7 J3 U( w1 `: c

9 V, a7 B5 A+ m/ S& @3 b1 K3 @0 a! h- K( u8 N
邻接多重表与邻接表的对比
4 f+ T: a$ c; V% O5 ]( r7 A
3 @+ j* e, d. ?  S% p邻接表链接
# K1 B: E+ `) `4 C4 V5 y/ I8 U在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。! z( j' Y6 G% t- K* P+ n. o( H; |9 H
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。1 I* v7 C3 j1 v  S4 e% U' b2 J* Z
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。" l3 B4 k* H$ Y$ U
————————————————
4 @: G2 b4 g# C版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。: L# Y2 u8 [8 ~9 X) ?
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
; O, H( e& s7 r. C$ h$ Y2 ?3 p1 @# B! b/ I; i! s) c6 m3 N6 m! Y# |
- Q5 }% b7 x5 W2 B+ ^
( g/ w* T4 r. g/ u& `
+ p) V0 ~# b9 g
————————————————
- W) m, j* M! ?  a+ H. ^2 i版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, w6 ~5 \" ^% x( n/ ~& R) c: Q原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669587 u) q' s$ e0 {! [# H7 O

5 M' R+ Y/ c) R7 N6 |, W' t
/ V# ?% F* j5 I+ T2 F