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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
6 V* o0 \' \0 i1 Ydata域存储有关顶点的信息；; ]6 |( I1 T0 T% c" c5 }+ q) k. l
firstarc域是链接指针，指向第一条依附于该顶点的边。- E5 _/ K& y1 ]; m! Q2 m
所有的顶点结点组成一个顺序表。

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;! @8 {$ d# O4 }" n7 l% u2 H) E* ^
for(int v=0; v<vexNum; v++). c7 V& q6 B2 L( _- D
{+ l. u4 x& w" u3 f; M" ]9 [
      if(tag[v]==0)( u1 D: G$ ^0 z6 E- G4 \" N4 N
         DFS1(v);: \' B1 L1 Z3 K, {8 B
}5 i, Q) W7 w3 f/ Z+ a
}
& _9 K6 W4 A) Q+ c& Utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
, O: S3 |' D4 o" {{8 h/ \3 i# k0 @6 C* L5 y
stack<int> s;
+ i5 {  M; ^8 Y0 T/ U/ W. Y int tmp;- ^5 V4 Q: ?) p1 ^
MultiAdjListNetworkArc<WeightType> *p,*q;* _/ P5 b/ \! U- n8 @" y
for(int i=0; i<vexNum; i++)! V+ Z: B8 p2 T3 @0 f. c
      tag=0;" `2 w7 P( ~) r0 }6 t* w, O+ x
for(int i=0; i<vexNum; i++)
* O) \$ o( O$ H- C. d1 ~# e: K {
9 m  E. x: u" J4 k" ^, y% k       tmp=i;: {6 R4 z6 D0 M! F! u* V' {
      while(tag[tmp]==0||!s.empty())+ e7 E6 C& ]# Y& M; n+ \# w
      {
# d" D$ v7 H0 z/ U          p=vexTable[tmp].firstarc;0 P' P8 K* b  N6 t- L
         while(tag[tmp]==0): [3 O; ?8 Y8 |- j' Y* |9 t$ b4 ?6 r
         {
2 W2 Z3 m- V" z% z  j+ z             s.push(tmp);
! v) H# p& |; `9 y# ?: A             cout<<setw(3)<<vexTable[tmp].data;2 Y5 s1 Q0 s0 c. X
            tag[tmp]=1;7 B8 X7 W  y* K6 s! b
            p=vexTable[tmp].firstarc;2 m' j- A& F" Z; |2 X6 Y6 g( M
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
, S6 T0 k8 C4 ~; a$ A             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);9 d: o/ o7 N2 a; k& B
            //cout<<" 1st    tmp="<<tmp<<endl;! w: t8 R' l& Q
         }; g3 Z  X" {1 i* C
         if(!s.empty())
$ E* d/ y. r/ L# P* L. J          {/ Q/ p1 \  f9 D8 t" _' x) i4 M" }
            tmp=s.top();" m8 n1 ~7 c; n0 X/ X
            s.pop();
3 n& G5 C- ]( R8 M; \) w! ~4 y             q=vexTable[tmp].firstarc;5 `& @9 u* p: T) f
            int t=tmp;/ p  F; @+ W7 e+ y+ l5 P0 r! n
            while(q&&tag[tmp]!=0)' O0 g6 q- ]- o3 t) U' u
            {
4 h/ x& Y! I/ Q* b                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);  b( K, S! Y  r
                  //cout<<" 2nd    tmp="<<tmp<<endl;" p6 p$ ~* T, p4 J7 p3 v( c" u
                  q=NextArc(t,q);" i  s' y+ W6 W4 u! H7 u+ X
            }' B5 d% X$ H) r$ n
            if(tag[tmp]==0)
+ `  [. W0 F0 \9 m' ~) W                   s.push(t);7 _, K: X; ]$ v- G1 K% @* J
            ///1、对应上面连通分支只有1个点的情况
; _9 k$ m9 o& P) Q& x) f% b             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈& q/ h% r- L" D" ~6 F# \
            ///tmp要么等于找到的第一个未访问节点，
3 {; y$ c( T. J7 s- }             ///要么等于与t相连最后一个点（已被访问过）) ]# h# G% l, U. o4 w
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点  _5 f8 b% Q- H. f6 f2 w
         }- G; G, I" z1 r1 X# ^( y1 s
      }
1 M6 v: o0 D# q3 _/ J0 e3 [ }
( z8 u, b6 V9 t/ {& ]# t/ O7 C$ X}0 N  \% s/ w- b8 ~1 L; |  ]
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-19 k* m# Q; l& x* i" D+ b) t
template<class ElemType, class WeightType> int8 u, [8 F; v: O# q7 V" K! @
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)8 h* p" d6 v' F! i9 Q
{  @5 ]) {; K, r3 S5 G" D( T% ?
if(head==pre)( a* s' t; D2 y! d$ `9 {1 X
      return -1;3 A1 @  K( G$ _" L

5 Q6 K- z0 E7 Y' ^6 S MultiAdjListNetworkArc<WeightType> *p;$ G# ?7 \& m0 K% Z! m) S8 z
p=vexTable[head].firstarc;. z4 P# ~% Z- w3 j5 ]' F. B
if(pre==-1&&p!=NULL)
7 B0 ~6 r/ z6 Y: S/ q  N       return p->adjVex1==head?p->adjVex2:p->adjVex1;( f  D: \- j1 I/ P* g, @
//pre!=-1&&p!=NULL
* B% z. T3 L8 L' V while(p!=NULL), ~! @  P: ?! t# \% L- y: T
{
' F$ ~8 ?* g. p% s7 \       if(p->adjVex1==head && p->adjVex2!=pre)( h: R; |) U8 P( j; D' |
         p=p->nextarc1;
4 Q6 O) V- z; E9 V! ~2 t       else if(p->adjVex2==head && p->adjVex1!=pre): D8 _2 p/ P, I2 |; ?
         p=p->nextarc2;
9 o# U) M: k7 |' x       else if(p->adjVex1==head && p->adjVex2==pre)3 u( W3 M5 {2 D% z4 c7 k) E" _
      {; w( [1 }, q8 u0 j" W) H
         p=p->nextarc1;/ X( F0 G' D1 J: }8 |
         break;; y" M- k2 O" {' N# R
      }
3 B! b) t! e* l. y( x1 o& }       else if(p->adjVex2==head && p->adjVex1==pre)
3 V) G& S2 _- f/ ~6 m       {
" N( r0 [% M  ?. Q9 ~4 D4 Z          p=p->nextarc2;8 f3 k6 ]4 g0 Z
         break;
# C6 B6 A$ I- d       }( T- y0 p3 d2 H. F" R
}
1 @4 ]& T5 p3 ?% r if(p!=NULL)
- E3 U; k* A* U: S* J- C7 L {
" J- ~! e3 d+ d3 N* p; E4 n/ y       return p->adjVex1==head?p->adjVex2:p->adjVex1;
. Z+ c2 Q( i; b2 D% U6 o }
6 k, ]% g" c, R+ k( N& x, e# C% { else
" w8 ~* u4 T, |" g       return -1;3 c+ S8 J9 |; G, K
}
# Z/ a2 f" s6 {. O) a; ]% |  T) g, E
+ C( j& l1 e2 a/ m% k/ a+ I. G/ ^# A5 l6 V- k
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
( m+ Y: @1 v& X{9 n+ x# @& ?  Z+ X1 m  `
stack<int> s;
4 _* V; D  b3 [: W5 [ int p,cur,pre;
) u4 O" r4 \8 F$ |6 P //MultiAdjListNetworkArc<WeightType> *p,*q;0 ?  Y& X2 a9 P$ Z$ X! T
for(int i=0; i<vexNum; i++) tag=0;//初始化  }2 E& D% X/ h

$ W; @) y% l8 f for(int i=0; i<vexNum; i++)
2 p# k5 z4 w( s2 i  t# n {
2 e. h: |8 Z3 W7 V8 z6 R       cur=i;pre=-1;
% [* E+ P5 \2 K0 W% s  f/ q" ?       while(tag[cur]==0||!s.empty()). T! A- o$ d5 A4 r; `8 h
      {! ?+ q+ e0 e7 q
         while(tag[cur]==0)  h6 b8 a+ ?8 x; \; |9 @7 C/ \
         {
. ^9 A. ]- v8 H( F# L             cout<<vexTable[cur].data<<"  ";
$ k' {3 p1 `7 X) f+ G" }  ^. ^- K; g             s.push(cur);) z  {* k- p  }0 f
            tag[cur]=1;
% ^9 Q( R- H- J) T3 h1 p             //初次访问，标记入栈
0 s  O/ \, b, n+ G. b
( M: C$ D9 i+ J' l             p=GetAdjVex(cur,pre);//p是cur的连通顶点
$ k" n1 G5 q" E1 D- O3 i             if(p==-1)
" K- [3 T' s8 S" T* d" Y             {
0 n& u8 r7 B; @4 x' r; X                pre=cur;s.pop();
9 u6 R! |" I% j4 z. C& t                break;
  l& F, |$ h% S2 ]; m& ]             }
. y# U% ?* @$ H' @0 \& R9 }             else
; S- y8 i' M9 q5 ~  s) n0 D             {' e6 c) O" ^- i7 w
               pre=cur;
  }. o. M: [  L" x4 O6 k                cur=p;  W& \5 j% F' C# P6 C
            }
, A7 D2 ~: a0 y/ C. N6 t
( ^6 a9 w, p4 b6 R7 h          }  m( g: @# U' d) U' U2 @
         while(!s.empty())& K# ~& @  _3 E- q# y1 T) O& M
         {
* S* X- W2 J" G1 g             cur=s.top();
  ^, d  R6 e8 @0 `! Z             p=GetAdjVex(cur,pre);# ?, T2 t" F( m
            if(tag[p]==0)
: z# h$ h( ]" u, G& b! k) H& R             {+ F( v1 E7 h4 ]; Z  o9 T
                  pre=cur;1 M8 h8 a8 {$ H7 }
                  cur=p;. u/ N. X1 b" X- I* q, q+ ]% X
                  break;
0 j1 t/ X+ ^- d, L* F4 W( R             }
' J1 q& V) K9 Z5 q! K6 o             else
1 k: e+ U% N3 H5 ]1 f' K- B+ j  p             {8 A  H! i1 Z4 r6 s/ z2 ~
                  pre=s.top();9 p# e' Z4 D6 Y
                  s.pop();% S% L/ q3 k' {2 {% ~6 n1 q
            }7 i2 R. k, R2 E) z2 l% e+ S! h/ H, h
& y* \' i: L& U' j( |3 y
         }, ?2 Z/ I5 F& F1 _5 Y

* {; }& W1 I0 l" x, p       }
$ L- T2 ?' q4 D9 [  ? }% a+ C0 r3 m2 A' w$ A% g& x: X
}
& Q2 p% o/ {0 L8 Btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()  T7 e# l' A2 \3 `$ J' Z2 o
{) U! w( O7 x( B! ?: I
for(int i=0; i<vexNum; i++)
/ f" H3 e$ ^0 m6 c       tag=0;
8 e* W9 ~8 e" x. b( Z. X queue<int> q;
  d' T# q; }# {3 p5 {5 S) F int tmp,t;
$ `3 _3 F: C4 k2 U3 N) C MultiAdjListNetworkArc<WeightType> *p;9 m9 D* C* ?6 G, D/ I0 O1 w3 m8 s9 z
for(int i=0; i<vexNum; i++)0 e0 O- N7 x# X( [2 h
{: q; u4 j# H4 M3 \
      if(tag==0)
6 K7 N9 \$ f$ y       {- T$ t1 |! I5 E/ l2 h6 N5 Y% T
         tag=1;$ K7 ~" R* \6 f& L
         q.push(i);
- d: [8 N. L* c; b3 D; y: l/ M          cout<<setw(3)<<vexTable.data;
6 h+ _4 w, v+ }& f1 x* ^' r       }
: p  [" ]0 d: G       while(!q.empty())  h0 @; H! a$ h; ?1 r9 F2 W. S; x
      {
9 V! g$ Q$ R4 n" w- {          tmp=q.front();2 H/ [( r$ t/ l3 l7 q5 b
         q.pop();
( f/ {+ ^8 C/ s6 F; @  \5 S          p=vexTable[tmp].firstarc;
9 t- R8 W0 F9 g5 |0 K* E          while(p!=NULL)
- S8 |, C% |( _# q          {
2 Z0 y! {; J) O8 Y             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);& C- M$ a9 f) {" v* C( o: {5 m
            if(tag[t]==0)
5 L8 W, n& W- d" \: H8 E             {# z: N1 ^- T4 h  m' Q
                  cout<<setw(3)<<vexTable[t].data;1 J; }, k. n4 R$ |- P  ~
                  tag[t]=1;
3 Y+ Y- z% n: Z                   q.push(t);6 U1 A) I) _. H  Y! p
            }) q7 [2 k. |3 B- z
            p=NextArc(tmp,p);- J8 H0 f% N9 w
         }5 B  r3 I' }! L
      }
! w) f3 Z' `5 [5 h }2 I; q5 K; y: L5 w- x
}6 y/ y4 q0 h5 i) E- w) F* q
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
! v7 u% _) R! p  W6 ~# ?{
& d- F" R1 p, j* y" |4 F! t MultiAdjListNetworkArc<WeightType> *p;. n& f2 P1 M: x4 x
cout << "无向图有" << vexNum << "个点，分别为:";
% f- H" I9 c- p# F+ D5 \& N5 E for (int i = 0; i < vexNum; i++)4 @! g: G3 V$ \+ |( C, Y
      cout << vexTable.data << " ";
" u$ ]% V# R7 F, y& m" \ cout << endl;# @: m% b+ b  g- s
cout << "无向图有" << arcNum << "条边"<<endl;: n! X9 I* N; _6 z% ~* ^5 a: d
for (int i = 0; i < vexNum; i++)
6 m" ?* p. y  i9 H2 U {
. v" y" m! Z8 s# \' n4 {0 s       cout<<"和" << vexTable.data << "有关的边:";
- @9 |# o, a4 j       p = vexTable.firstarc;; n+ ?+ R( P& t+ j; o1 ^
      while (p != NULL)
. L1 S  d: P# x5 J$ ^       {
% r/ Q* M* p5 U  B8 B          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";- Y& i+ o* X8 u" W7 z- J
         p=NextArc(i,p);: d, ?6 b6 M* f  \/ V" C. i6 |
      }
* a, V5 b9 n- h% u6 S" W       cout << endl;6 d2 X2 o3 o2 s! J- p6 X, M
}
* Q/ _7 n( n% r$ Z7 Z3 O) C}' _5 Q  H& w2 d5 z9 I6 ]2 C' W

0 p( p! i! d7 @& m( t7 D9 Z8 q# ?- O1 T1 \/ l, @
邻接多重表与邻接表的对比* o/ f8 H1 B  x0 S4 C
# ]1 X6 p9 D" [/ k0 Q+ j& H% F9 ^! g  O
邻接表链接
  i1 X% Z1 E& o( ^" U在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。5 B  ], \! N! [% E2 `
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
  o* f% y3 e% J. V为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。7 l# E' d0 M6 K  m+ m' x
————————————————
4 h. T4 S/ D) s# O4 x: |版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; I: i  |+ U( t/ E% h
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
" K! B* k# M* z7 o( m! T$ c0 I" {$ D. \4 s
- H$ p  U/ O( ]3 n
, o5 c" ]5 }. p, I
7 n* C0 X3 A: ^. u7 p# |
————————————————
, F: [: o* x+ L+ m% X2 L- ~* E) w版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! ], W4 [( j+ [. V原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669585 X+ f, O! p# a
" y1 D' w  J" s: Y
" m; Q# K. T. u$ h5 J1 B2 z1 h