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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：0 O5 q4 j/ \3 [" u# O1 H2 ?
data域存储有关顶点的信息；# f: b7 i+ C! W# n2 p% Q
firstarc域是链接指针，指向第一条依附于该顶点的边。
' n* }& i; }! Y6 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;7 ?7 L  F4 U) A9 ^- q& M. Z. P: Y
for(int v=0; v<vexNum; v++)
7 J. Z  p% E3 G {
9 o7 C6 V6 M$ O/ d, P# L       if(tag[v]==0)
, Z- u/ z. C3 ~  c  F          DFS1(v);
9 G4 Y- E! s- l1 ]+ X+ @ }: I1 p/ c0 [! i. R0 I
}! R% m% i+ z; R
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
( h  _; l) F" B' O  l( p{
3 s' M1 m4 |/ C/ T stack<int> s;
5 H" Q  r  u& S; t. ~3 k3 D int tmp;
3 Y2 G" ~1 W, \; V( c2 r0 M  I MultiAdjListNetworkArc<WeightType> *p,*q;
4 U- d( l/ `+ j7 h; E4 a# P9 ? for(int i=0; i<vexNum; i++)
- R$ E$ `) J5 I       tag=0;
# R+ ~9 ?8 W  s1 h1 U for(int i=0; i<vexNum; i++)
* g  I6 w; ^! Z {+ n* \% Q: e' _# S$ z
      tmp=i;
* Z1 r3 @! D- H       while(tag[tmp]==0||!s.empty())
# k) d. k" ^  Y% W, K9 ?" K0 Y  u       {
% X6 Z( m3 W2 t7 Q# t          p=vexTable[tmp].firstarc;6 D6 M( e3 P3 S2 w' J7 q
         while(tag[tmp]==0)
* d" C4 p- e7 H: ?2 l, q          {8 K  v! T. m$ f3 |8 F; o! [; p8 c
            s.push(tmp);2 Q1 e, z; I) p% l3 y3 Y
            cout<<setw(3)<<vexTable[tmp].data;
5 o* K/ |, A4 ^  k" R1 \. S* @             tag[tmp]=1;. c+ r( A7 b0 z8 f0 t
            p=vexTable[tmp].firstarc;9 Y0 u- ?7 U. O1 F4 p% T/ B
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
$ E  g; z0 ^0 e3 J3 U) H             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
6 \3 {4 B& }& A9 V" S* J             //cout<<" 1st    tmp="<<tmp<<endl;; S  Q# [: t( N% ?" i
         }
1 i' E: s) c6 o0 F8 F0 G          if(!s.empty())
+ M0 h2 v' A0 F- }( F          {
9 _6 ^7 }5 e7 L7 @  X' S             tmp=s.top();
. x" Q/ ?. D7 l) D             s.pop();
' E3 m% s  L3 C             q=vexTable[tmp].firstarc;
- M8 n9 n6 l* ~$ S# D+ o( }3 E             int t=tmp;
( C0 M- c& K' X+ K( c             while(q&&tag[tmp]!=0), L/ d" J  e" o7 t! F" n7 o
            {
3 Q# L" E; ]  w% f* @                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
. g( }/ f5 y6 t6 Q2 C% v                   //cout<<" 2nd    tmp="<<tmp<<endl;1 M7 J, @3 ~) r
                  q=NextArc(t,q);/ v4 Z' a5 Q' r7 @; \' a, p0 N6 y
            }
# b6 e4 G, [% Y             if(tag[tmp]==0)
2 k& ?7 y6 L. z$ n  M2 }1 \- c                   s.push(t);
! i% ^& q/ C- V3 i* P7 {* |             ///1、对应上面连通分支只有1个点的情况8 M4 p2 b2 i! h
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈$ }6 W7 a  @2 X8 J) p9 `6 a/ s) o
            ///tmp要么等于找到的第一个未访问节点，) u  C* W) r1 z% a3 N  y: P1 b
            ///要么等于与t相连最后一个点（已被访问过）6 [8 [$ {! O# k9 x6 t
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点: h* h# [- H9 |: b% P
         }4 ^6 r" K& A" s: m! Y% H! `8 z
      }
5 j2 q- \3 f. S; s }0 w6 B$ X" \. z( G
}, m7 v7 S0 {. _9 E& q* y# ^: s
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
5 A: J) O5 }0 I4 Z. k) }template<class ElemType, class WeightType> int
0 Y5 c7 F9 m. C' l9 R& JMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)6 u5 `' i: s3 x8 j$ b! Q. `
{6 h  Q3 {- q# T( `
if(head==pre)
3 [! }& c) {4 N       return -1;8 c" S% T, M" E
8 @5 x) ]# c+ k( a6 j
MultiAdjListNetworkArc<WeightType> *p;- }" `# ]) v* ~" l. u
p=vexTable[head].firstarc;
$ A9 e  F5 a) P9 }7 L if(pre==-1&&p!=NULL)4 b6 \6 Y- h0 A
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
& N9 q, b' Z% l8 F  S, W //pre!=-1&&p!=NULL$ d( r4 m& \7 [7 S2 `5 X
while(p!=NULL)
3 r9 F- a( g8 X! t# \ {
  q% O7 k  d2 O- g       if(p->adjVex1==head && p->adjVex2!=pre)$ l1 o1 a& G* C8 _/ X) _
         p=p->nextarc1;2 {7 \' @/ w$ b+ `4 t& S" M9 \
      else if(p->adjVex2==head && p->adjVex1!=pre)
, @) \6 T. F0 i  j2 A6 Q  i          p=p->nextarc2;$ y$ b; V  K9 }3 h9 i$ J2 T
      else if(p->adjVex1==head && p->adjVex2==pre)! h* A# S4 H9 R/ r$ T+ j
      {
. g. M' J9 t: S6 z9 d5 ]8 f$ l* Z          p=p->nextarc1;
4 B* D4 {$ O0 s          break;0 E( l, d; N5 |8 ]* ?6 [" r3 a$ m+ f
      }( p* g  D6 Z# y* i
      else if(p->adjVex2==head && p->adjVex1==pre); n% q/ R% g5 q! Y8 V7 p- j
      {4 A" x$ Y! Y# B& `2 ]
         p=p->nextarc2;/ a/ U% i. z6 c7 U' K& z
         break;$ Y$ R4 \6 k% i$ F
      }' f5 g% y8 o3 e2 a% z0 R
}# U3 {. Z" f! `, x
if(p!=NULL)
% q# v7 o: ?0 E" B( g {
' l. e* U1 A7 `" E: I3 P       return p->adjVex1==head?p->adjVex2:p->adjVex1;, H) K6 L" q) j5 E( J5 u
}
! K, n* c+ P) z# L. a3 P' n. z5 ^ else
) S* c( I3 B: M5 H       return -1;
5 Q! L7 c. _5 j9 R+ M6 P4 [}
  q9 a  ~; Z9 M# ^' J
0 j% \' t! p, D3 V2 o+ g# L; h4 ~/ U7 D# S) B2 c( z
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()# w4 `& a8 Q8 o, p
{
% o! ~0 R7 |! T3 a4 S# B stack<int> s;
& P, V# s- x0 g* M+ i% G  P" r9 B int p,cur,pre;
9 a( S2 c; G/ _) C4 h //MultiAdjListNetworkArc<WeightType> *p,*q;
# n* A+ ]1 k1 H# P- |. q for(int i=0; i<vexNum; i++) tag=0;//初始化
2 \9 ]' N& y* Y+ m# s' ^" H: Y  y0 }
for(int i=0; i<vexNum; i++)# ]" S2 ~) `- m/ i( g/ }! {1 ~
{, K+ u+ Z# @8 [- c6 m5 p2 S. L
      cur=i;pre=-1;2 y* D7 M' o; s  k
      while(tag[cur]==0||!s.empty())
0 o$ m8 W2 ^* i2 `0 ~       {4 K$ d5 p) i% G7 |/ O) y& y3 }) b
         while(tag[cur]==0)
) p( B1 \" _" z3 A4 R9 X          {
. D) y0 j0 `, Y- o3 n6 p             cout<<vexTable[cur].data<<"  ";& d2 X2 w0 w( ~' u4 q  L6 U
            s.push(cur);
# h4 P3 l. [  }9 v             tag[cur]=1;
% w$ k5 I$ h# `             //初次访问，标记入栈6 g6 e" l. s* f  h+ T
+ M( [. k' w2 {7 b0 a
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
* ~2 u- G. k5 W             if(p==-1)
/ e8 f+ a  L9 T- K& _5 p+ s             {/ @9 `# P" _' I# `5 O
               pre=cur;s.pop();3 O+ L4 ]& |7 }5 V
               break;
3 `2 \) {$ `- X; M6 x             }
* s" R* h' S3 T& h! f" p             else
; E# C: r6 N; k8 m; j             {
) h1 b6 j3 I. O! {6 L                pre=cur;
1 O- ~+ Z4 s% ]- k1 Y% G, n                cur=p;" ~& h# B2 K$ v. L
            }
  B5 a5 u1 ]! X" O
" I+ u5 W6 ~0 |6 }# }- n          }/ _1 |/ Q! M' ]4 r/ V! E. M& t
         while(!s.empty())
% h3 m9 U' |+ v  s# W. X* p          {
4 z3 k/ T! F7 y4 _; P2 b             cur=s.top();
/ ]$ L5 L: p6 Y( u             p=GetAdjVex(cur,pre);6 d# `1 Z1 J. h9 v0 a
            if(tag[p]==0)8 r$ \* ]5 A- U) N% W( S. w
            {& K' x" a' A3 o# a6 f
                  pre=cur;
1 n, z/ ~  C6 {& k8 |" R                   cur=p;* f0 Z0 x* J8 q- e: B
                  break;
  z' S3 G9 S! W, x* B  ^6 ~             }& U) {" N* P* t  [. A5 K4 z, P
            else
5 C0 ?! B0 T( T% K+ v6 T) [5 E* G             {8 D) X1 Q3 m$ y$ A. l) h( U
                  pre=s.top();# v5 p* n) O# a% d
                  s.pop();8 v( q- {0 ^! g, Z9 B; ~1 t
            }. O) `( B+ I/ a& r( q) }9 p8 H

  r1 R' `( W1 h          }
4 V: a7 N1 I" A) D, K: h* D; }$ B9 b( F8 m3 t# e( \
      }
- ?) n* S1 P" C6 F- i8 G2 D7 D* F }4 |/ a, O* l6 u6 I( s) z% m' o& |
}
# E- k7 z3 T0 v3 Z  S7 Ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
; Q& I$ B2 l$ Z- A) v{+ P3 h' h8 ]5 s3 f1 P* u
for(int i=0; i<vexNum; i++)
, M* ~! `4 j) i3 F; j/ r1 R       tag=0;0 f- ]  O, }* C! O% H; j6 U
queue<int> q;
0 i6 |- M. [1 k int tmp,t;* X8 n  k' W# ^/ j& n7 C( V; d
MultiAdjListNetworkArc<WeightType> *p;6 T6 P* w+ H$ q! Z0 H9 v! }
for(int i=0; i<vexNum; i++)
3 F7 l) n$ d3 ?8 V! U) c1 G {
      if(tag==0)
  ]& k0 X0 z9 t* B. ~5 e       {
9 C; Z' Z. A8 k2 n( K; x4 M          tag=1;
/ N/ p' ]$ @" a4 ]6 q1 c          q.push(i);$ R2 t! a, {$ `2 I/ {
         cout<<setw(3)<<vexTable.data;  q7 f, N  ~+ T8 w' H  c7 N
      }- U% z0 ]0 a! r2 h8 V' v& U& s3 Q7 d
      while(!q.empty())- R' j; ^" s9 n+ `
      {" h$ N9 F1 s7 v4 l
         tmp=q.front();
) ?5 N) l0 G/ ]( }          q.pop();# _0 G0 N- ^2 q- b# t
         p=vexTable[tmp].firstarc;
' G( M. t. G6 d, d1 I; U- a! T          while(p!=NULL)% B4 y& P- e8 J( w( t
         {
3 A( K+ L# b: T5 K, y, E             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
; M/ \0 r- K9 p             if(tag[t]==0)+ v/ h! y8 V- [* T/ _' m7 G
            {
8 Q8 t" n% L! d+ ]' D3 M% N                   cout<<setw(3)<<vexTable[t].data;
* v6 L5 {; t( z2 O( ^                   tag[t]=1;& Z& }: U1 j4 H; q) V5 H
                  q.push(t);
; g# H( i: F3 [9 _             }
* \( X* D# m7 L5 q9 o             p=NextArc(tmp,p);
; G* Q& V# ]$ {6 x$ l$ u! ?          }
2 P5 l- L6 d4 D  E, Z       }8 k) N6 P7 V4 f/ Y" R
}& t* J$ h* p8 f+ m; I: ^# A- s
}. b. w& ]0 x" i3 t/ [
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show(). H' o4 H8 [# t2 E; ^* \3 h0 H
{8 L: S( e1 J# W. j' N1 C* B
MultiAdjListNetworkArc<WeightType> *p;
1 K8 g7 L1 v# Y6 V2 o2 b' ^ cout << "无向图有" << vexNum << "个点，分别为:";
$ W4 y3 t+ s0 |. i8 X; I for (int i = 0; i < vexNum; i++)
8 u3 H$ w9 n: [       cout << vexTable.data << " ";7 ~) |# c+ s9 [( d
cout << endl;5 Q; |. a3 N$ }# `, V% `& m- `
cout << "无向图有" << arcNum << "条边"<<endl;
$ K  x# P* m/ q for (int i = 0; i < vexNum; i++)" V3 l1 S# b8 h* p: p8 a9 F
{
% y; j1 S! R9 }# t! [# ], H6 W/ Q       cout<<"和" << vexTable.data << "有关的边:";
$ A* d) X# Y* z6 d       p = vexTable.firstarc;
0 x# x/ g& v/ A6 A9 R! Q7 B       while (p != NULL)
+ v& o/ Z" @' }       {
( D' s- n' k. B, i! f* W! A          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";* L( i" N" H. F1 Z& U
         p=NextArc(i,p);
3 f8 m& g- W$ O& X0 @. E       }
2 i! F8 W" F7 a1 ?9 g0 I0 T4 T       cout << endl;
. y6 d" h8 n- ^* C6 a2 K }4 h" Y" |- e6 @% N
}6 v+ c1 j) r0 B% z/ S% U

) |0 I0 a5 w+ G( ~) b" P! ?% R" S$ _4 e( t7 K% P
邻接多重表与邻接表的对比
/ }0 @+ N0 o+ A& Z1 ]" B
) R0 i$ I- h" r邻接表链接
2 R6 k6 X  M: Y# P/ _4 f' V/ V9 P在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
' P$ w( V+ \# d  }) e在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。, l( t! X6 |  y; r3 U1 M  [5 J
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
: [+ z. l' N. K, f, o. {————————————————* [) k3 p! o6 V$ h, ~4 }
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ D; B8 p6 g8 v# o8 O原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
4 m3 F# q5 `  k. k7 O% Z: M6 h
+ O1 f! O; s& L* g. Z3 s- ]
: s4 B, N- W% l9 c$ f- m$ G! t" X" q3 Y* ^5 s# {6 w

& W& g, w' e( A' l: E————————————————
+ p) N9 R" p* c: ^) o5 K; ?' U5 v/ a版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 H- [5 t1 D/ j; M+ H原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669589 q. ^8 g% ?. t2 B

7 z- B# T9 O( G( @; |4 ^- l; P  M, t/ [  m2 c+ w0 }