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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：' P: s F, L7 Z9 B% k7 F
data域存储有关顶点的信息；
: N. T# U: L0 q) tfirstarc域是链接指针，指向第一条依附于该顶点的边。
7 O3 U% |$ ~( [, w所有的顶点结点组成一个顺序表。

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;1 F+ |/ P7 t, {' Z$ @3 `& H
for(int v=0; v<vexNum; v++)
8 g7 M0 L- U) z3 Y& M& m {
( k' L& f, i4 c) m( Y0 c       if(tag[v]==0)
0 `) C, |6 t8 D/ c          DFS1(v);5 n& q! |7 V& b# Q
}/ h+ {5 o# d: H& G" D$ c5 Z# l. K
}( m# W8 A, |( c5 x. ^) S
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
' G/ G, w: b5 L( i/ G& z! b& k{2 v/ U" @. c! p3 c6 x, Q
stack<int> s;3 L4 ^! ?& L7 A+ e  p8 T* X
int tmp;3 ^5 @1 q5 [9 I: F! w" l/ y3 p
MultiAdjListNetworkArc<WeightType> *p,*q;
! v$ G$ a. P5 k4 {. s for(int i=0; i<vexNum; i++)/ m( ~  C6 k0 V( M7 a9 h+ G7 w
      tag=0;, {) k; ]1 C5 r$ H; y+ F
for(int i=0; i<vexNum; i++)/ h, J/ g$ \7 F& \( l) m
{5 x/ M+ s5 V9 `
      tmp=i;
! ?% w5 E) s; G* j1 G2 j( h       while(tag[tmp]==0||!s.empty())
2 q7 S) d% a" `* P, ]. s' K& L       {- x1 I  Q+ t$ j/ }' F
         p=vexTable[tmp].firstarc;( ^' W7 @' c) f5 _) E
         while(tag[tmp]==0)
6 I* n& g4 x6 ~% [$ G          {
8 r! R. P" F5 G, H             s.push(tmp);- f6 y* U/ H/ o7 h: k% w' R! v: x
            cout<<setw(3)<<vexTable[tmp].data;
% e7 ?: x4 M$ ^8 L- s             tag[tmp]=1;$ }5 V3 H' v% Y! f( \, t: D! ]
            p=vexTable[tmp].firstarc;8 o# r- y: u/ E) |& H
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
# f* t8 W9 J3 D             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
( h6 a* T! C- F  E: g             //cout<<" 1st    tmp="<<tmp<<endl;! e; a/ i: S0 l$ }4 M
         }
" x( G, {, T1 _          if(!s.empty())) c8 l( L. C, P  B
         {6 ]3 e  r+ y8 R( z9 N8 d, [
            tmp=s.top();. k5 a4 H- u$ a" j3 \7 h; Z
            s.pop();- D+ p8 b2 R. f9 ]. C# e
            q=vexTable[tmp].firstarc;$ V  x8 G1 s" s0 N
            int t=tmp;
6 `& G! e: d0 d  b. K$ f8 W0 _             while(q&&tag[tmp]!=0)
) l8 u; q+ ^1 H: Z$ B! o             {* }5 h+ V2 \( X& i2 |9 P; Q
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
, P' k; y5 ?! E# F) n                   //cout<<" 2nd    tmp="<<tmp<<endl;
6 j) f6 W$ o" R; i. N                   q=NextArc(t,q);
  T2 _+ e6 f9 p             }; Z3 ?" b1 L- _* Y6 l
            if(tag[tmp]==0)
4 j  a( O7 v0 |- h2 V                   s.push(t);
( d* A# O% B( E  _2 B3 Q# s8 O1 o             ///1、对应上面连通分支只有1个点的情况) @) J  B, l9 V5 ?3 H/ u+ u. e
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
# |& J. F0 F/ V; C; l# Q- _8 ]2 R0 j, W             ///tmp要么等于找到的第一个未访问节点，# A- ^8 y. E: e
            ///要么等于与t相连最后一个点（已被访问过）
% t. P, W% E& |, b6 G! @             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点' ^+ [$ E( [0 l) s  M) {* V
         }+ }7 h& z, {' P5 q: T6 O
      }
7 }  ]2 [% x5 @  F }
9 t" _) u/ `0 a0 x}9 e2 G2 \7 v& d, v1 l. o% \
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
$ m+ v# G7 \0 w& q! _9 Jtemplate<class ElemType, class WeightType> int
. d( j4 t" u- kMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)+ W5 ~. b  N% @2 `  o7 [; ^4 s
{& _6 i  Q  u: |/ W
if(head==pre)
3 b, R9 k1 a4 d9 g$ H3 ^       return -1;: q8 v4 o7 q9 `* Y5 U
: z' K# Z9 E. g; ^7 `$ y* I- `
MultiAdjListNetworkArc<WeightType> *p;' z( G) [/ R$ O- [1 ]9 |
p=vexTable[head].firstarc;
0 r1 t) d3 C% k! i" | if(pre==-1&&p!=NULL)
. |5 C" n. r0 n7 b! s- n       return p->adjVex1==head?p->adjVex2:p->adjVex1;+ T  H6 Q6 R+ G8 c6 E  ]
//pre!=-1&&p!=NULL, f; T, k/ m) Z2 ~
while(p!=NULL)
, x# n1 K; u$ S7 E {2 G% `/ g4 S, L9 j1 i9 D+ x! e
      if(p->adjVex1==head && p->adjVex2!=pre): U# r; L, p! k6 j3 w/ L
         p=p->nextarc1;# X; {; C2 X7 Y3 I* G
      else if(p->adjVex2==head && p->adjVex1!=pre)
; ]( H1 D8 ~% }, q" C          p=p->nextarc2;
& |6 {4 ], \' E; V$ \       else if(p->adjVex1==head && p->adjVex2==pre)/ ^/ c4 S$ I  L; b: u
      {. M$ W5 w6 C" W6 x) o# Y3 W3 S
         p=p->nextarc1;) k0 W  p  J0 \' @: b" J
         break;: E. `/ Q% M- U9 X
      }$ L  j$ }8 ?) q- f. B: o) d( J2 S
      else if(p->adjVex2==head && p->adjVex1==pre)
6 A* {# }/ n% n       {; Q" ~6 K0 }1 j8 M, t4 Y+ r
         p=p->nextarc2;
. U4 i7 C0 ]. D7 w# j4 S          break;
. }1 m& V! _. H& N, t5 S       }
# n8 m# n" B5 J5 O }
# G9 b' W) g4 Y/ p1 D  `: p: } if(p!=NULL)7 {# L+ O8 C6 g% E
{# g8 L- O% t6 f6 Y( n- n3 P6 L
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
! p5 ^8 U3 c; g: q4 U+ c$ T( S }
# X. a& O- I/ b5 z7 D* d4 o# x else
1 A, s: ?! B% x! x9 b       return -1;6 ?: o) u! e4 _* k. s
}% d9 {* W1 B3 v2 V! x+ c; J
! r: d7 K) ~5 S: p& D: ]) u
) ]3 E+ Z6 }- H2 M# ?0 I9 K
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
! ^+ ?/ ^/ ?  v$ l$ H; w, W{
+ z0 f" v! X6 W$ G* {1 O% @ stack<int> s;
  O* I- E9 x# c/ O# `) x int p,cur,pre;# k, R* `- O' O
//MultiAdjListNetworkArc<WeightType> *p,*q;
0 w7 F8 t' ~9 L for(int i=0; i<vexNum; i++) tag=0;//初始化: s6 i+ h0 y; u9 P

4 N1 I) q- e- e for(int i=0; i<vexNum; i++)
3 J6 b4 b$ T. g& S3 f {
9 y* w- D3 n( z: p* K       cur=i;pre=-1;
* t9 D2 g% i! ~) ]9 n; J5 Q: K5 Z; W       while(tag[cur]==0||!s.empty())6 J) B, Z. F- i" M6 _
      {
1 d& o) L# n5 S- ~          while(tag[cur]==0)
) P% F$ g7 O3 Y- L4 p          {; G0 g! m8 V' }: c# B- S; H
            cout<<vexTable[cur].data<<"  ";
5 I" ]2 t; C% R) C, U* |             s.push(cur);
* R- V" U, P# Y* u' m3 o             tag[cur]=1;
+ F5 y% x1 j/ A" \! D             //初次访问，标记入栈" Z6 Q. E3 {) U% ~, m" f
; n* f  W) I8 t
            p=GetAdjVex(cur,pre);//p是cur的连通顶点& v9 c* q+ W3 |  n0 T
            if(p==-1)
; a0 ]0 |8 m1 s: C+ [6 P6 \             {$ E: D" B: {, |0 ?* r
               pre=cur;s.pop();
1 M7 j* ?- ]8 U8 r: H; S, Q0 U2 J                break;$ \# H9 v0 P1 P# T$ h% j, L6 i
            }
) Z8 E% e/ }9 |( Z             else
9 _" f/ K/ o) o6 s7 u' [! A1 i+ N. u             {& p  f! v& N, F! Z6 a/ }. ?
               pre=cur;( S: [1 J4 f0 L( }' v* z/ q
               cur=p;
% M  U7 |4 n+ q  V& I             }
; ?, L$ k) D# O) x
$ A8 V" @5 N; L2 r! S/ }; X+ O/ n          }: x" Q; u7 }4 P2 ?+ b
         while(!s.empty())
+ @3 {& W# h0 @3 v          {
0 n4 y5 v! z( O: v" F4 y6 N; w/ l             cur=s.top();7 u! Q. X5 I% O4 R
            p=GetAdjVex(cur,pre);3 N* }0 z5 i% d' D& @( K- @
            if(tag[p]==0)
$ u( Y4 d. K0 u' G5 T/ g             {7 s  v$ B0 U! j& |8 ~
                  pre=cur;$ z6 N) I- P0 x5 S, v
                  cur=p;2 j. W( ~* M/ F+ Z! W0 k* o0 e
                  break;
2 a1 Y: x6 l: N  {: O             }; P. s/ N6 S% i- E. c. A9 J: V
            else
$ @4 ~/ E4 x+ Y! C! K# y             {
0 v7 S5 |# B; d! v% x  X% F% s                   pre=s.top();
  B4 J1 V4 s& w) C0 T                   s.pop();
5 R6 q( L. d$ h6 M6 v3 `$ ^             }
6 F) w0 u2 @% }2 H& r' v* c: @
6 i9 y' e3 ?; {          }
1 t1 [6 Q8 i  r0 L3 k$ z1 A. |# S8 f/ p2 ?" a& x) h
      }0 p5 E; N8 c. V* d8 ]( v
}+ }+ _, A, {4 A# z3 R  P
}
7 v3 P- E" H9 H  I/ |- j( Ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()# }+ g! `7 J9 ?1 }" ~% m! w6 R
{
3 m( n) P, I, m for(int i=0; i<vexNum; i++)
& ]) o$ O" K- c  x       tag=0;# y. z5 [3 B. g
queue<int> q;
- s+ t6 U+ ]! @( R% Z4 | int tmp,t;
- H! y$ G' T5 Z MultiAdjListNetworkArc<WeightType> *p;* U- f& g; z# y! p" B
for(int i=0; i<vexNum; i++)
4 w1 A# _8 \0 i) S2 M' I {
! e5 }: `9 `9 _% H* s& ~       if(tag==0)
: a! E+ J" Y! A$ R( ?       {
3 S* K8 h3 U. O& y7 F          tag=1;; F% M- a4 r8 _& e" y
         q.push(i);
/ b3 i0 N; M+ r! e- T          cout<<setw(3)<<vexTable.data;3 Q3 X5 @! w; Y0 e
      }
/ W; ?3 X) O# O8 }& v9 o1 F* a2 ]       while(!q.empty())0 P, |+ ^3 }: ?: U4 ~- a4 `( ~
      {  L6 r: d; l) t3 G- x
         tmp=q.front();3 w5 j  }7 k$ r$ R1 D6 o
         q.pop();
! x& \8 M- D* V- w          p=vexTable[tmp].firstarc;
6 u7 I2 q/ l1 a          while(p!=NULL)9 ~& |* |- m, g) N0 N* E7 ]
         {
- I" W% E2 {- N. z0 \             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);: _' x  n) }. r0 X2 y7 E& C* S  M
            if(tag[t]==0)2 Q! B5 v4 T' ^) c9 l
            {5 \& ?9 @" {( k  Y# ~1 N( s7 X
                  cout<<setw(3)<<vexTable[t].data;* V2 d# A; P' @% G! F7 c5 k) ]
                  tag[t]=1;  q$ {- {+ D: c
                  q.push(t);9 I) s3 U& s5 E, ^
            }7 W6 f. w& y+ d5 Z
            p=NextArc(tmp,p);3 z" i2 l& _1 F
         }  n0 H! y  ]- M0 G: |
      }2 E. X9 y( T* r) y
}
' F; r7 Q( y3 n" c}
; [/ \+ p* H9 f2 }template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
7 c% P% b5 M( }3 p+ ^8 G7 O6 K{# j8 T; Y5 k1 I7 f* l. ]/ I& c
MultiAdjListNetworkArc<WeightType> *p;7 r0 O  w- b5 N- d- b" [
cout << "无向图有" << vexNum << "个点，分别为:";5 I; J; r/ @- N3 n+ p5 ?
for (int i = 0; i < vexNum; i++)1 Q& d, p" r* d# L! d+ s: e
      cout << vexTable.data << " ";
' t) l$ X+ u& \) }5 s2 ~, j3 ^ cout << endl;. k: J' h3 |* ]
cout << "无向图有" << arcNum << "条边"<<endl;' h; v+ \& F* `& x# o* ~' f
for (int i = 0; i < vexNum; i++)
( n# I9 R6 L3 [/ |% H {4 [( [4 S& C5 u9 d
      cout<<"和" << vexTable.data << "有关的边:";
. M4 y, `  c4 c9 S+ m7 e0 o+ O" E       p = vexTable.firstarc;
5 R  S, ?+ O- w# u/ o" H. d8 _0 }       while (p != NULL). b; Z6 j: O& O& N# E; ~- e3 c" y
      {+ A- u+ ?9 h# B
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";" c9 A8 Q$ p: g/ H4 Q
         p=NextArc(i,p);! l! ~6 K8 \# Y/ F! o
      }
9 _- Q+ ]' z4 N# \0 S- U       cout << endl;# x* B6 e! d8 I$ c$ }" q4 |
}3 W7 V$ G$ @3 h8 w; G# l, Z6 I5 S
}' z* j4 Z" P* H% K# f+ B6 V" s" n

: `" |6 o  A! W( }) B" K& g6 J( k9 A6 c# }4 h/ n9 ~8 Q9 j5 j1 K9 W
邻接多重表与邻接表的对比/ ], F; s, I& S' H
' U0 G# o; f5 c7 I) i) D
邻接表链接; t! N+ l6 t( K! r+ _. x! p
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。  T! J3 x% _) L+ I* x9 a( C3 o" Y0 j# d
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
1 q# K2 T7 p& w" U为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
. k9 A! B2 R2 b5 r————————————————
2 ^! Y  r; S0 V4 [$ R版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 g) h* L. h9 r4 u  z原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
! U) c/ q  y3 t2 G2 D/ R/ j
1 B5 g( Z9 n+ S+ m) r; j" L3 p9 b9 C/ [& q6 _. \; M2 f
+ a% v: O( G4 l& C! {! P
/ g. s  m  R' F4 z. m
————————————————
( z5 S0 f- Z& w# b# Q版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。9 j. m) K, R* a8 Z& Q' y
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
) C/ Z" E$ B7 k) m6 q; f) k8 U' B8 U8 W7 K& @/ R
" L/ c0 U. r; i# `' [7 G, ^: R% w