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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
) n+ {: t7 s6 m. d3 C7 \: t, sdata域存储有关顶点的信息；( Y8 j) M o( ^7 U7 I
firstarc域是链接指针，指向第一条依附于该顶点的边。
. w* ]5 a* I4 O- N所有的顶点结点组成一个顺序表。

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 i# y- V9 |% _2 Z7 B
for(int v=0; v<vexNum; v++)6 H; t4 s9 B* w5 H
{; J' u1 @3 N# d  Q# Z  P# p' s- I
      if(tag[v]==0)
0 i7 v+ U$ i0 @( {# Z  k; |          DFS1(v);
6 o+ i) G# U) V }6 E. {' [* ~+ H( Y6 e3 p7 B: W
}
% d. t3 ~. A% {) l- N% ftemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
$ b" \& t0 g) T: @7 ?3 y{  O( Q# D6 c! b+ p$ D0 Z
stack<int> s;2 d; y+ A8 d( e" ^3 H4 g
int tmp;; ^# a8 t3 c' N  [8 n
MultiAdjListNetworkArc<WeightType> *p,*q;* u1 H4 T9 Z2 j$ ^# ?
for(int i=0; i<vexNum; i++)4 S1 e6 E# K0 g+ Z  R
      tag=0;2 Y0 K! f. k( q  O5 A3 t5 R2 A$ ^
for(int i=0; i<vexNum; i++)( A2 U& K) E2 \. J7 F5 U
{( H3 H% E! F# P6 B! g/ l
      tmp=i;1 [0 Z' E, l$ t5 M  Y5 G
      while(tag[tmp]==0||!s.empty())
: j+ i1 M* A" [3 S, {+ u% m       {# ?; H8 q3 x7 D$ \
         p=vexTable[tmp].firstarc;; ^8 w4 U: ^5 @! Z# U
         while(tag[tmp]==0); R) I) S1 m7 p; G0 r* ]% a0 O
         {
) i9 v/ ?; I: W- L             s.push(tmp);
# W" V( O3 |; T4 ^9 [# _) P             cout<<setw(3)<<vexTable[tmp].data;; N8 I6 Y- ~' C/ V9 I
            tag[tmp]=1;( ^% N$ Y9 P% w& \- F
            p=vexTable[tmp].firstarc;, ~4 h  V, ]8 m, [( F
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
0 m, y& s+ g9 r* x             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);& ]5 o0 }0 a- O
            //cout<<" 1st    tmp="<<tmp<<endl;# S3 @' ~$ ?' K3 C( b. n
         }
4 C: C) D* ?" [$ R$ }( s- W* s, d          if(!s.empty())
% N4 l' l( h8 V+ ~( U5 G' p* }          {  D8 j/ i8 W. Q1 G4 a! ]2 M
            tmp=s.top();/ ^7 x5 L8 U) L( F! W: y
            s.pop();/ r& s/ V, W  s( {0 U1 C8 P, a
            q=vexTable[tmp].firstarc;
9 y/ E' X7 ]! G5 [. n             int t=tmp;# \  z, @/ e/ J8 r0 ]) h
            while(q&&tag[tmp]!=0)# b) [' c: G, o$ p( X
            {
+ e. n: d) v2 T. \+ s! v" P. z                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
( M: j4 }3 e0 A. H; R                   //cout<<" 2nd    tmp="<<tmp<<endl;
: }  R4 z# Y& p8 ~# x; w' r                   q=NextArc(t,q);
2 [( `1 n) |! m0 F             }+ s) s' K0 D% i$ T) s2 {* l
            if(tag[tmp]==0)
' }6 r) \- W1 d1 A$ y  u                   s.push(t);; z! l1 C, W$ @" z* o) i$ N. C
            ///1、对应上面连通分支只有1个点的情况
! T5 N; f% t- q9 z% `             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
& c! t$ M/ l2 T. k             ///tmp要么等于找到的第一个未访问节点，
6 E0 U; U/ G- c! d2 M2 J) G             ///要么等于与t相连最后一个点（已被访问过）, Y8 ?# k& H" u/ Q, a
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
/ G! U' A, @5 w          }  b  ]6 S' ]. C
      }2 B1 U# \1 k, h1 b" h( f
}+ D- a: U/ S2 o' n
}* v/ V* p( p% g9 F+ x' N+ r
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1: n% M* E! q) M5 x
template<class ElemType, class WeightType> int
+ `. B8 p' N! g- OMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)1 T; t+ z+ M* W$ {5 N
{2 @8 Z' D. I3 d: w  I+ B# Z8 U! a
if(head==pre)
7 ]* ?, @: Q1 d4 H       return -1;( b9 z, e, L6 Y; t' n
4 n3 t, p6 Z! N/ q4 j- Z+ c
MultiAdjListNetworkArc<WeightType> *p;6 Q8 J3 c; O' A( n& y7 k
p=vexTable[head].firstarc;
6 l6 T+ o, u+ D! l8 i! s  | if(pre==-1&&p!=NULL): J& J3 k( \2 c6 ]$ U2 V- G
      return p->adjVex1==head?p->adjVex2:p->adjVex1;1 ~( V) e* S6 _# n7 O% [
//pre!=-1&&p!=NULL' ]/ @2 c) p, Q# I4 J( b
while(p!=NULL)
& F% H8 q0 n# J {7 u7 s% p8 j# W9 ]; F- I
      if(p->adjVex1==head && p->adjVex2!=pre)
9 F$ {1 j8 j/ ^- w/ g; p          p=p->nextarc1;+ w8 j9 M, t7 E2 I9 C$ y& k' c
      else if(p->adjVex2==head && p->adjVex1!=pre): X( a- g3 b$ V6 l& d9 D
         p=p->nextarc2;) a. S" b9 C- N  Z( S+ O
      else if(p->adjVex1==head && p->adjVex2==pre)1 h+ ^; ?) J6 K
      {
/ J# {& L, Z( K# N8 E4 c, a          p=p->nextarc1;
( F* R1 G8 w- A9 T) K; V' U          break;) {* n' m! ?4 m: A. J
      }8 C! A5 Y* I5 l! }& ]
      else if(p->adjVex2==head && p->adjVex1==pre)5 ]/ y! a) ]9 ~1 n- D( n
      {6 u6 u& }" n* W3 b5 X
         p=p->nextarc2;: V7 O# _( S2 }( t! B* `
         break;
/ G+ P( J9 Q+ q       }
$ O; j8 |5 N9 V4 C4 d }
* f& ]  Q; _; Y  l/ k0 F( j if(p!=NULL)
* b' ]# s! Q% }; y, w" D& o {
6 E' r$ B. z5 r; l, F       return p->adjVex1==head?p->adjVex2:p->adjVex1;
$ l, E& }2 q! n }" H/ `$ K8 G* u' N0 {5 O
else
' ]2 w4 H; u% s- I3 I       return -1;# ~) ?2 ^; _1 H. h( P
}% ~3 ]: W; \2 Q! g/ t: o! |
) A; l6 Z2 {( K1 N- b# x' e

! T0 D3 X$ G6 A6 Q7 K2 l1 q# L/ Y  ]template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()! A" L- [$ A( S* W
{6 T* Y; J( {: L+ ?
stack<int> s;
0 t* Q( N  f% T3 I7 q int p,cur,pre;+ a- K* c  `& F  D3 A' ]7 [4 b" U
//MultiAdjListNetworkArc<WeightType> *p,*q;
% U" w! u6 z  ^+ R, F( ]  U1 a for(int i=0; i<vexNum; i++) tag=0;//初始化
2 j5 K% F3 j' r% g0 D7 n7 T! P
for(int i=0; i<vexNum; i++)4 v/ n: A, s! }, ]6 d; W0 A
{
- m  Q+ t/ c" z6 ^9 J) j       cur=i;pre=-1;
5 z9 `+ x6 g, E% P7 m" M, J       while(tag[cur]==0||!s.empty())
1 \4 ~3 v6 F$ Z: `9 K2 a       {
3 Y4 \8 l: @1 [9 X          while(tag[cur]==0)& Z8 W! T5 o$ q/ x( l
         {7 f5 S; W; M* V$ V
            cout<<vexTable[cur].data<<"  ";! @1 M# A) M. s- ^
            s.push(cur);
0 K" g2 a5 ~. {  \9 Y5 L             tag[cur]=1;+ L; i3 Y  o2 U2 U( {5 W
            //初次访问，标记入栈
; e5 j8 X1 e/ Z# p- S; ~! s5 l' h, o! R( s1 u( }/ _% y5 n9 ?% G4 F
            p=GetAdjVex(cur,pre);//p是cur的连通顶点" {- A. H$ F! `: i/ v4 v
            if(p==-1)
0 ~9 x3 j2 L! E             {
5 o" _, m& |! O+ x4 @! r                pre=cur;s.pop();
+ K1 J7 a! `! L# q0 v8 [                break;' j8 s6 w& _$ Y* _
            }
" w3 ]3 S# e5 ?1 `( g- J$ O             else
! Z1 d0 Y8 ?+ s2 ?! v             {  i% U, d# I! i0 V9 _; O- ~1 X* W
               pre=cur;
8 y7 p$ L+ y/ ?7 s2 D                cur=p;
4 u% T0 w( B# Z! V% @/ B) ]             }  H. b7 ?8 k9 l& ~. P9 l: @
5 F+ v! W0 p# H6 [. E+ a
         }
4 @1 J2 H. _4 F7 b. b) r0 H          while(!s.empty())) F# ^; L& v" u& k) z
         {2 T5 h8 s3 B0 W7 |7 b
            cur=s.top();. v# d, p$ l" i0 O  m+ Z
            p=GetAdjVex(cur,pre);/ f" |# d5 J' Z# ]1 w
            if(tag[p]==0)
$ z# P+ [3 O/ y             {, X6 L; D& Z; ^# x2 P
                  pre=cur;1 N& C* S3 I" a
                  cur=p;* S9 O) V0 Y- r! r+ Z3 }
                  break;
! A8 B& f4 x( {+ C! p3 J+ o# t. Y% ]             }7 E' A4 `9 C  s
            else3 v2 k! t, l" ?* K5 O; \3 G/ ^# t
            {  c- k/ `' E, w1 d. j1 z
                  pre=s.top();& |* @. r2 }4 U( x% O
                  s.pop();
1 b' u  E! D) L             }% t. D" o9 W! r

; n- M; E8 o! `/ b. k+ R  ~          }
" m3 @2 I# d" i) j( S
% b- D/ R+ {1 f! b; L* \" h& o       }
! |8 |, r) v+ G9 G% d- H }
. ]/ Z+ m* P1 L8 F$ S1 N" `7 e}
9 g$ A6 u0 S  [- Q1 s! V6 g+ a7 Ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()4 U+ O% o' I& Q2 T
{) [& P7 n- w6 Z/ \, I1 F. ]5 a
for(int i=0; i<vexNum; i++)
5 Q0 W! x" m. p8 y: j4 B8 N) V       tag=0;# c% s! f; K) l& P
queue<int> q;
( r9 x2 E' L3 K$ O int tmp,t;' b  U6 t  Z7 n# U! r0 ]8 f4 b
MultiAdjListNetworkArc<WeightType> *p;
* ~* d5 c7 p  C8 G# K6 z for(int i=0; i<vexNum; i++)
3 v! ]- G) [4 A {6 {; V1 W" x/ N. N# ^
      if(tag==0)  K: t* r6 @4 c2 o
      {3 W3 X2 m+ c; b8 o9 o
         tag=1;& I, V: }8 I- U. r) E2 ~! Y
         q.push(i);7 D3 J& X* x  b3 Z5 _5 q' f
         cout<<setw(3)<<vexTable.data;' U7 t, j# ?. W; U
      }) M; f0 v3 e; Q1 e4 ?" p
      while(!q.empty())7 N3 }1 u! Z. z* c" h- ^( O
      {
3 a; F1 H+ g+ P; I" z          tmp=q.front();3 J8 v4 G- k- p
         q.pop();
5 ^$ o# V4 R9 y% M% N          p=vexTable[tmp].firstarc;
$ f3 X+ a9 d2 T1 {: i( V- u          while(p!=NULL)
- ]+ S6 w. a) R4 N( Z. ~% y          {
2 ]5 F3 [  |* H( M             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
& t8 _) H* }8 Y" C; T7 g+ G             if(tag[t]==0)
$ }# B9 q) W6 [1 W8 _5 [+ ~             {) }0 c0 h( z8 S6 s
                  cout<<setw(3)<<vexTable[t].data;
$ u0 ~' G) v. i/ S1 _0 h6 m3 J                   tag[t]=1;+ [. R9 h# R$ g8 ^
                  q.push(t);
) X2 S& l* \: {/ v8 Y, t" f* T             }; {5 C! f0 F% v
            p=NextArc(tmp,p);- ]  U# k. o1 [' D% g  J
         }
7 X$ |- V! v& H' X; W. z$ c& x       }' g0 _1 b4 k* V6 x3 o, ~
}
4 v3 p0 F4 Y* n: U: [4 ]6 o% U: S}" x- E. V, h+ U/ o9 ^$ ^
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
$ ?5 C  Y. p/ ~$ l% i( N5 l& x& E{
! a1 u6 P+ W, e7 ?$ d1 [- N+ i$ W! u MultiAdjListNetworkArc<WeightType> *p;  d, q! a6 A1 b8 S# b3 K, d% ?
cout << "无向图有" << vexNum << "个点，分别为:";* C1 ?& r7 r- W: S+ s
for (int i = 0; i < vexNum; i++)9 c/ a- \1 A9 N+ D' M" [
      cout << vexTable.data << " ";
9 |' d5 O1 s& i) \! I- c cout << endl;
$ j/ `( R# ?, ^" x5 Q: h) O  l cout << "无向图有" << arcNum << "条边"<<endl;
* j$ L$ f* K, k8 @, s for (int i = 0; i < vexNum; i++)/ a' o1 ]. u- l& S5 M
{
( w% R  R9 V) ~- m$ ]7 Y       cout<<"和" << vexTable.data << "有关的边:";* t- M0 j5 M+ Y- y
      p = vexTable.firstarc;' l  L) X* T! {( O) ?
      while (p != NULL)
) x1 P3 `/ u  y: Z- r9 b       {
& z# K" a* w3 |/ i          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
1 f3 h, E6 Q! x7 s8 Q          p=NextArc(i,p);/ C) k& i5 X) Q/ A4 b6 `
      }
! t' W# E2 W$ e( Z! r  Z# j4 `. F# z       cout << endl;
* l/ \- [/ E% ^: ]  G6 A }9 ]8 x3 P  g- j7 t  g  K
}% r* [: d4 S0 }5 p' w/ d' i( j
- h3 y. y5 |8 O8 V
3 G' e; O: W7 @
邻接多重表与邻接表的对比! @4 Q, h0 k: o) ?' W

" F/ @8 Y7 ?) P0 p# w4 Z, L5 ^邻接表链接' h/ y, @# |' r/ v1 G5 h
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。, D( E9 ~, H( u" H8 ^- T
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
$ Q0 t9 I' D0 b为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。( o; E9 [) R  y1 I
————————————————
0 Z2 \6 V% v" V7 s! J版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。' D: _' ]: [& ~# v) B! V( R
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958' m+ G+ `  X$ F6 r4 [9 M0 h
& `# F/ E; a8 c7 c

/ ^' v  L4 t9 c( S5 D0 ?: m* R. L8 g6 h& v* Q4 x
3 f' @/ E! m: A) @- \
————————————————1 o! I4 z9 k  M4 W' M: n+ {
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。: y% S: S6 o) [4 A' h: C
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669588 F, w* [/ b2 O1 [6 u  m! S
- a9 b. \' K# V/ @( X* J  _

2 m; A/ L) O2 r$ |$ _: l/ v