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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：! M$ v1 \: Z/ |% {
data域存储有关顶点的信息；
8 m# X2 Z& v% o' p0 Gfirstarc域是链接指针，指向第一条依附于该顶点的边。/ p& w, X4 j( N1 D& r
所有的顶点结点组成一个顺序表。

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;
9 o- X" \+ ~+ U3 C for(int v=0; v<vexNum; v++)
! N  B: I4 |# D5 F# A' g {
+ k2 m8 ^9 c  k, ]! q       if(tag[v]==0)5 O. f6 V' `$ A! S- P
         DFS1(v);
; }5 a, h$ }; G+ c }# r$ d; O# T! J- O7 H" q- ^
}
5 G: I8 l+ n0 b" G+ |8 E- dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()$ X; X. Y  Q3 l$ M
{
6 E1 F" N- y* l2 u2 l  X) s8 r stack<int> s;
7 v. _/ Y9 j; t4 } int tmp;
7 T0 s, `' k- W: s; [/ l2 ~0 s MultiAdjListNetworkArc<WeightType> *p,*q;
5 u6 ~7 m8 N6 `5 f0 c% H for(int i=0; i<vexNum; i++)" G2 `2 j( _4 f2 _* t9 n& C% [: S
      tag=0;# A* v9 g' n0 H+ ]* j( E4 o
for(int i=0; i<vexNum; i++)
: Y2 p* u/ f) B& ]0 k+ o {
0 w' }2 _5 h7 o: n& l6 j7 Z       tmp=i;' |% R8 t: N2 o! }+ b
      while(tag[tmp]==0||!s.empty())
- Q1 S; g, g3 U" ]       {
2 @$ }8 I; }" l0 T& B  ]( o3 ^          p=vexTable[tmp].firstarc;0 k2 q. }. A$ E4 r6 R
         while(tag[tmp]==0); W. H8 h. p1 P6 {$ H
         {/ ^1 D6 y! k/ e& R! ~  n) z1 _
            s.push(tmp);
( o2 L" ?! v, u$ n5 Q             cout<<setw(3)<<vexTable[tmp].data;% _5 C3 t. h3 @0 k# B
            tag[tmp]=1;
5 w- a# d- Z% z8 ^             p=vexTable[tmp].firstarc;
# L& }, [, Q: D! c; l, Q             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for6 K* `! a! K' J7 {5 |+ q. M" E
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);# a8 s0 p+ E: W7 S0 F" ^
            //cout<<" 1st    tmp="<<tmp<<endl;
6 z  K, H2 v7 N$ j; u4 X          }$ m. i7 c' }" {; V2 a
         if(!s.empty())
7 H8 n1 I! x% j; L; y          {
! x: e( T, J0 f             tmp=s.top();
7 f9 g6 V" e3 d! t$ m, i% B             s.pop();4 Q6 u8 Y0 W9 J5 Z2 T- P8 a
            q=vexTable[tmp].firstarc;
" S8 k  n. O0 a3 R* W4 h             int t=tmp;- o7 Y! _" e" \9 W7 k% z5 d
            while(q&&tag[tmp]!=0)
* ?5 D& u3 r$ F5 x  |             {
2 F6 m! v2 T9 H                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
) M- z0 D3 f, m" z8 g& \" Z                   //cout<<" 2nd    tmp="<<tmp<<endl;
9 x& v2 K9 ~& z! v! y# L                   q=NextArc(t,q);
4 i! e2 T- X& X8 G$ ^3 b, m8 F             }* j) ~8 m/ ?5 j# q
            if(tag[tmp]==0)
  t- d0 i4 d% }* l! C7 V                   s.push(t);  K  m2 {. _# w$ ^% N1 T
            ///1、对应上面连通分支只有1个点的情况5 j% w' Q- D2 T1 Y
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈+ f( x( L! w* Y, r8 c- |* g
            ///tmp要么等于找到的第一个未访问节点，) H' Y# e, v- _
            ///要么等于与t相连最后一个点（已被访问过）8 o) d: `* a0 h+ c
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点4 j' e/ h2 {. x; j! k& N3 U# W
         }" E. ?; R- C. H. ^8 p) T( g# F/ }
      }
9 c4 Y9 \% |) @2 n7 B4 v  b& n8 A }, ^/ q& Q9 m0 W3 V- w  @
}
. o5 ]/ V, z' R. p5 R& u- O0 b//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
, p4 l' R' B, M8 ntemplate<class ElemType, class WeightType> int7 W- J. E' r4 j# o! x
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
" g: K7 K, w1 c! u# |. v" Y1 u{
! Q1 ]5 ~/ ~/ d/ |( ~6 | if(head==pre)
* i! Z3 Z1 N+ T, h9 R% T( r       return -1;
0 @0 \3 G) s3 H% I1 M+ q* }, v  l2 T2 k. g  _, }6 i
MultiAdjListNetworkArc<WeightType> *p;) u  o9 p' o( P; U9 M
p=vexTable[head].firstarc;% N3 w/ ?  K9 i0 F4 {- Z
if(pre==-1&&p!=NULL)8 d2 ^# L# a) j" ~6 L* f
      return p->adjVex1==head?p->adjVex2:p->adjVex1;& ?( p- E* K% w% S2 v: j
//pre!=-1&&p!=NULL
1 c6 \' t8 r; d7 k% m. F; L* y6 D while(p!=NULL)
2 C* ~8 P6 |  P {
  A  M5 `* l. h! N5 m3 H3 L! h       if(p->adjVex1==head && p->adjVex2!=pre)
. G: ^* O: u/ J          p=p->nextarc1;
$ j& T: u# @$ S9 R       else if(p->adjVex2==head && p->adjVex1!=pre)
6 q9 g( i( x& C6 |+ m3 K$ P9 ^          p=p->nextarc2;: x2 W, M& e# c0 d7 h2 {
      else if(p->adjVex1==head && p->adjVex2==pre)0 [5 z# U8 o( k( g
      {
  g7 {; C! q6 A          p=p->nextarc1;
1 N+ a9 Q9 V5 @3 ]+ a          break;
* S8 ^3 T' |5 {$ L9 f: y3 y! L$ s       }+ t8 R5 y5 l  g1 A
      else if(p->adjVex2==head && p->adjVex1==pre)
; K) e, `/ a8 H! ~6 K9 ^+ d       {
% H. `9 F9 S4 f: M8 n: q' V          p=p->nextarc2;
: [! J+ \7 e; n9 H          break;; E% j6 y' I% p2 m9 F; g
      }5 r: j; H& \" O$ J; X0 Q
}
5 g( A$ D# o, O" h8 J% n) s+ p) G9 c if(p!=NULL)
/ r6 ~& d2 m  A3 \% M- ? {: J8 k$ ^# u! A
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
6 l' D7 L6 _) X }
4 D3 M* Y1 i( [0 y, r3 M else  q, [0 z5 f8 I* W( G& B1 X: B; [
      return -1;
! [- `; n7 @5 \, M, s/ d; b. l}1 f! A& J. V" {+ t/ G2 c7 I
0 Q4 j/ Z: h3 ?2 e* U4 @
) g0 [3 o' w1 s/ V
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()' }, m& r9 l# L$ o- F9 S6 u2 E
{6 H" e: S5 I/ a8 b- f. P
stack<int> s;
+ M5 p* _0 A& K6 f9 s6 H int p,cur,pre;, r2 b" Y! c# w" s, A& C; T
//MultiAdjListNetworkArc<WeightType> *p,*q;
- |/ _4 M0 s& h3 w) z3 O) s( {# v% ? for(int i=0; i<vexNum; i++) tag=0;//初始化
& M  }( h( P4 D9 |8 {4 Y( D" C' L- V4 ^0 s' F, F, p& y$ v
for(int i=0; i<vexNum; i++)" K" Q: n- v8 T$ C6 |& b: K
{
! W+ R" b7 a. d& [       cur=i;pre=-1;8 R! \; c2 k! I/ }  A
      while(tag[cur]==0||!s.empty())! Q& U5 G# ?; R
      {% P$ A6 g( e1 Y* O0 C  Q& N
         while(tag[cur]==0)
& F! O9 j( n3 a" i* Z- a          {6 C8 R4 L8 s) T1 a7 O
            cout<<vexTable[cur].data<<"  ";$ ]: }% z8 f+ y# H, o1 H' o) J
            s.push(cur);1 o) m$ k! \2 H/ b4 j6 x+ d3 T6 Q
            tag[cur]=1;: k9 d: I: d7 `/ S
            //初次访问，标记入栈! w; N6 [2 j3 q0 m3 m6 v4 S
$ _# V3 I+ B9 X
            p=GetAdjVex(cur,pre);//p是cur的连通顶点- @) L1 a( k2 @- e9 D
            if(p==-1)/ |4 w  x- u& G" `- w/ @+ u
            {3 {" H$ x: h  d
               pre=cur;s.pop();; {- C+ c0 H# Y  t/ S
               break;# [. o! J. T8 t) l2 N9 G+ m
            }
& r! ]' V6 @( [1 @0 V! Z* a             else
2 M, a5 g% s; m6 w: h             {
0 f5 K  \" k" }9 r9 i' c% H' D                pre=cur;3 L1 f) t" ^- C: P3 r. ~
               cur=p;- G/ W% N! p) J8 p* V
            }2 I9 o( ?: y8 ]6 M8 N

) W) L: W2 s7 p6 l& s8 i" _          }
" Y+ I) G/ S2 k& t$ k" _9 B6 W          while(!s.empty())
1 ]# S, J! B( f' }0 D) a7 h# z0 R          {
7 j+ B/ ~$ l! O3 R0 x  I/ e. x$ Q             cur=s.top();
. u: A% m6 b% W8 l. H/ C6 e, O             p=GetAdjVex(cur,pre);% `# u2 L1 |- Y5 C2 R$ l+ @" X
            if(tag[p]==0)
9 z- S- l( H& A, A             {4 `/ X9 w2 B) F! M/ J& P, V
                  pre=cur;  G, w% F! z- R% p
                  cur=p;
6 w0 d- ~  w0 ~4 `9 d' ]                   break;
* e; o- Q  Y+ s3 N             }. b! ]" W- [( p! l9 a" c
            else
/ x6 T8 L$ }1 L             {
+ E# A* [9 o) _! Y7 ?! t3 G8 m                   pre=s.top();9 \: X" t3 x; T3 U- k( `) A
                  s.pop();
& f* o. _- Z. i* y: W0 S             }7 w/ w7 D5 r3 x

* N2 \0 m5 a# T) l; X          }7 A# E  W9 Z& {

2 m) s: |6 M- q6 N( F       }* d' Y6 T3 D3 h+ s- o  w. ?
}
. }& `# l  v6 ^. |: j/ H}
/ V( ]' Y5 Z2 n% i8 k  ]$ ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()/ ^5 P& ^' i" `# D% {6 \
{3 Q; i/ a3 R- \; ~3 [4 Q& ^
for(int i=0; i<vexNum; i++)
# L8 C* E9 m2 S; ^0 y; C1 A       tag=0;
7 ^, [5 ~! j% {8 n3 y+ U8 W, d queue<int> q;) }0 H! }# c: x; f
int tmp,t;$ o* l# U3 ^- I# F$ N# Z
MultiAdjListNetworkArc<WeightType> *p;! b1 o- G. o) m8 H
for(int i=0; i<vexNum; i++)
0 o6 s0 e; c5 \2 i, O {8 d# ]6 I9 F* o
      if(tag==0)
7 R# q4 g* W# [4 X, `! A4 ^9 t# O       {
# n# e; l4 s( u3 n% P- J" k; @+ G1 F( Q          tag=1;( S% |* _" V8 @% j: K. a% ]
         q.push(i);
8 ^7 D8 [3 f1 K          cout<<setw(3)<<vexTable.data;, m& t& X# J$ q
      }  `6 H- Z  u  O; _0 k# c
      while(!q.empty())
( X/ n* U5 }& l# [9 V       {
9 O6 H: O. a# d6 F* m          tmp=q.front();
' T- ]! T- p, a5 A          q.pop();- r8 F8 C/ ?8 a; O
         p=vexTable[tmp].firstarc;5 M# p0 v5 L6 {* r+ b
         while(p!=NULL)
) a6 s2 ^% L2 C' h: l          {8 f$ G6 |- ^/ Q
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);; j8 ~" Y% v4 f* r
            if(tag[t]==0)
( B+ K/ @" x+ D( A  ]             {6 X) K+ h5 k; p; |
                  cout<<setw(3)<<vexTable[t].data;9 x& V- Z" _+ T. m
                  tag[t]=1;' @9 P- z/ ?8 V- v* s& ~
                  q.push(t);' D( m: ?; G# g/ O+ W; J
            }0 O2 ^9 ?% i, ^  K6 r: h2 u
            p=NextArc(tmp,p);
5 _6 |0 U3 Z% `8 J# d4 B          }( g" y; Q% H9 ~# t3 A5 t( N
      }. u/ H! x% p; C/ k2 Q8 M
}/ |  G1 I, }5 }  D: w
}
, W5 Q: g* V1 B, Ltemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
. ?8 S$ W& ?/ H4 x{
) I% y6 o  ]! u4 s* N# z9 I MultiAdjListNetworkArc<WeightType> *p;8 Z+ y0 \3 H* ~* n0 j* l
cout << "无向图有" << vexNum << "个点，分别为:";% K) I$ `& B2 N( R8 L# v2 @( h
for (int i = 0; i < vexNum; i++). Z. X7 I2 K, C" Y: M% U/ w
      cout << vexTable.data << " ";
! C! u! h; K' C cout << endl;
/ h# O" o% |; Z( e: } cout << "无向图有" << arcNum << "条边"<<endl;
+ W9 O6 H1 R% G1 I/ h, F for (int i = 0; i < vexNum; i++)
5 z. i* A2 l* ^0 }+ ^& s% l& k* e {! d) w( b  \, C, f
      cout<<"和" << vexTable.data << "有关的边:";
! }' ]0 y" W) H( m8 J9 ^/ a       p = vexTable.firstarc;6 J; D# D) Q% d
      while (p != NULL)  k3 v9 y! ^1 F
      {
2 L& ^: T, T3 ^' u+ ^          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";4 C& {! ]) h( b% p- N# S
         p=NextArc(i,p);
, F1 u! x  C5 b% Q* |: v) J       }
* K6 b2 ~2 H' S) z2 n       cout << endl;
! W7 l- e5 N# q' E: M+ ^ }2 b; `: M, e# g2 g. y
}2 `+ V: F/ P8 A

2 m) u' K2 K8 b! d; D: S3 u8 i; t) x! `$ K# d: Y
邻接多重表与邻接表的对比9 N5 K$ k, ?6 w. }. f7 R; ^
* ]; A4 n: A( l! c% ?% U( U+ ~
邻接表链接
  v# p% I+ I% ~2 [8 H9 p( m5 A在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。0 y7 ^5 A( ]/ p" T
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。, ?3 q" G& W; R. e& H& i; |
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
8 d6 ^* H; P9 h7 v————————————————
5 d3 m& u% {$ y: t版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。" _7 }3 a; h1 N0 A3 l
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958  D9 D7 G9 Y$ y: L/ @0 @. J0 O
1 o9 A3 G8 ?) k8 j" S' E: N* Q

3 `. b1 u, k9 V* ~5 g9 O/ I( T3 u1 U+ L# V. C

* w6 u/ f  L( z; [+ M————————————————
8 y* Z+ H" M, T! J$ ^( k版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。, S+ N4 n& ]" D: w& c1 J
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958+ t3 i, W- G' G; m& }2 b

* ^- j/ W* c5 |! H5 p* z2 B& H& x! h  \# c$ J8 f