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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
, Q- |- _, z/ m2 ^6 F, f0 w3 n6 udata域存储有关顶点的信息；
0 A$ B l# J' }! s" Dfirstarc域是链接指针，指向第一条依附于该顶点的边。$ J3 z+ L7 p" n; G; d: O
所有的顶点结点组成一个顺序表。

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;
" S: k+ ~% F5 n5 ? for(int v=0; v<vexNum; v++)- {- ?7 u6 p) s, _# H- p& P
{
* n& V. u  x! Z4 _2 v       if(tag[v]==0)
- M- c' l! J% y- b          DFS1(v);8 T0 i. u: w0 X4 @! A8 n
}3 W) e9 Y, z; |3 @9 ~. P5 M
}
: f3 n0 s% G6 ^- |# ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()/ S( c$ f/ [% `
{1 m! h) S$ u! d# m
stack<int> s;2 n9 m  m) B2 q; C& W6 b* K6 \
int tmp;1 Q5 K- T& U8 y' F' R" \! m$ T
MultiAdjListNetworkArc<WeightType> *p,*q;  C/ ]* i2 \7 q! n
for(int i=0; i<vexNum; i++)  L4 B2 ~  f* E: z5 V2 ?
      tag=0;
" E) c/ k: g4 r) G, D/ ^: a for(int i=0; i<vexNum; i++)0 Y8 y/ \, m5 h8 s9 I" \
{
3 o8 X# h2 m% @" j: g1 i2 L       tmp=i;
* \# ?# o( k) c       while(tag[tmp]==0||!s.empty())+ P* G% R9 h* n* G) q/ k- E
      {: |" y& S" X( c3 k' p
         p=vexTable[tmp].firstarc;
! j* M: O$ s& C, V4 V# H8 q          while(tag[tmp]==0)
4 k" U* o0 j: H$ ?          {' q7 L7 M9 [: ^2 ?
            s.push(tmp);& v" ^* @# |0 ?3 i
            cout<<setw(3)<<vexTable[tmp].data;8 a0 ~, d/ l0 G8 G: S" L3 n
            tag[tmp]=1;3 v6 u4 c! Y+ q; s. \
            p=vexTable[tmp].firstarc;' ^; E! C$ p. H
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for$ Q/ o, J0 V/ L- p. V0 ]
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);0 T- p' y% A( t+ A
            //cout<<" 1st    tmp="<<tmp<<endl;* j0 f# w0 f+ q# B
         }
: f( M* p( Q( }( N, ~4 T          if(!s.empty())) `% J2 B; b6 g# P' N3 R4 x7 }8 `+ W
         {) W* Z% I9 o( `6 ?9 @, i5 E, B
            tmp=s.top();
+ x5 v( l1 m, m" }' J, K             s.pop();' j6 B, X  K) X- `4 E$ `
            q=vexTable[tmp].firstarc;, p8 d& U* _! X! \! R+ D
            int t=tmp;' Y7 ~+ ~1 n7 E: P9 x' c8 c
            while(q&&tag[tmp]!=0)
' H2 Q0 t7 n. z0 M, D; ]" E             {. U- ^0 O! `" Z( y4 s
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);& Q4 q' S0 G" P/ P9 N/ b
                  //cout<<" 2nd    tmp="<<tmp<<endl;
5 y, a9 R8 ~. O$ A  i# w1 e$ K                   q=NextArc(t,q);' w5 X& ]( a! l' W/ V5 `
            }% }$ @( [% }$ V0 V- ^- \/ z3 V
            if(tag[tmp]==0)5 T/ O# O9 ~2 K; S7 P
                  s.push(t);& d( e4 P1 u; E* u' W
            ///1、对应上面连通分支只有1个点的情况* G6 _# u; H0 O1 R- `
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
$ D9 c6 V$ g8 t, R             ///tmp要么等于找到的第一个未访问节点，
4 E% x% h6 }# Q6 S4 `" _' Z( v+ y             ///要么等于与t相连最后一个点（已被访问过）; U. q/ ^: ^; B
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
% C: {5 ~+ ?. s) k; v          }" `' j7 B6 s9 q0 @" {9 V
      }
7 G; A9 Y# w- E) c }/ D( L# {% @. B  L6 x* M
}! @: `- t- T0 ?5 ?
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
. U* \& J" G- p( S9 Mtemplate<class ElemType, class WeightType> int2 m; n5 [- K  M# j6 K
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)- a! j1 b/ x) L5 s
{& U) o8 \$ N6 \# V
if(head==pre)( }& O) r' q6 Q8 ~# Z+ _
      return -1;
+ G& z5 ^  o& o' F, N$ y* t  m3 m; V4 x4 V6 k
MultiAdjListNetworkArc<WeightType> *p;' |9 K9 G. s- {8 a; T
p=vexTable[head].firstarc;/ @# z$ k1 H7 B  u* c# N  o1 c
if(pre==-1&&p!=NULL)
7 g! f: d0 \  A0 _' e       return p->adjVex1==head?p->adjVex2:p->adjVex1;( D# A6 ?# ]6 i" t* \8 x
//pre!=-1&&p!=NULL  Q; n2 R' g  g) L) k+ o( }' m; B
while(p!=NULL)) V9 W% z+ h+ Q: p) ^; N
{( M( U' t6 J! ?
      if(p->adjVex1==head && p->adjVex2!=pre)
4 a) B1 ~2 o8 n  G" F          p=p->nextarc1;
1 s; N( t. D4 ~- V4 O. u* V$ l       else if(p->adjVex2==head && p->adjVex1!=pre)
# f! c( g, `8 A+ X' ~9 i          p=p->nextarc2;
+ {7 }7 W+ E+ A' W0 R) {       else if(p->adjVex1==head && p->adjVex2==pre)) ~; c/ `! o/ J) a. c
      {$ p9 v" g4 x4 v3 M
         p=p->nextarc1;0 L" Z4 r* Z0 X, H: F6 w# r
         break;
2 ]' c5 a  A/ W2 \8 A       }# v. ^" p0 g, A; y6 K% ]
      else if(p->adjVex2==head && p->adjVex1==pre)5 D8 E  H, k( Y# d. ?2 o3 H* _# v
      {, h$ t; O" N* h# o
         p=p->nextarc2;8 t, p2 v7 d& `% j. l1 U5 H
         break;/ G3 h% i* g; J; n- P( b$ l& B
      }: K1 F. b1 _6 K2 }. r9 _; X
}
* n' Y1 u4 D2 Z% S6 K if(p!=NULL)
! y8 {2 l% U! V4 l1 t {
( n( `! g6 t. G1 @/ {7 t+ w+ ]& w+ N       return p->adjVex1==head?p->adjVex2:p->adjVex1;
. I9 c& u  p& R  `5 e& c }1 M+ I, k4 e/ S  `, G0 j: C8 `, ~
else# ^! ~6 B& y9 ~2 U0 z2 x! o
      return -1;& d. \$ w1 P  Y8 B( `
}5 d" V- N4 [5 I) R4 d8 Z; ?

9 Z2 B6 n  W, g3 U; ]* l
3 h6 {% x# S2 {# p* stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()3 s, m! T3 q* }" U6 o3 j- }; J
{
& M7 O# e4 I% P4 p1 h, S stack<int> s;
5 x2 }- T& c* C4 ]8 B int p,cur,pre;; [' M4 U; a6 W& B3 V! V* H3 o
//MultiAdjListNetworkArc<WeightType> *p,*q;/ Z* E/ ]5 p' W& X. H
for(int i=0; i<vexNum; i++) tag=0;//初始化
) ?5 ]: f9 x8 \2 e$ x. {" L8 f9 s7 O" j9 M- S- N0 Q" c
for(int i=0; i<vexNum; i++); b  Y* J+ [3 N$ S. ?
{
" ^" M6 i$ e3 c: z3 y/ I       cur=i;pre=-1;) ~& f5 @* l& `7 y+ o1 A: {$ H
      while(tag[cur]==0||!s.empty())8 x+ g* V) @' f4 T* v
      {& s  m9 V) M+ J; t1 `2 j
         while(tag[cur]==0)8 O( Z) G' ~) I3 P  J
         {
/ t% g+ V+ q( f1 x3 c6 k0 W             cout<<vexTable[cur].data<<"  ";2 i; Y# Y% f" I7 D- r5 N
            s.push(cur);
# U* |: C- w; y; e6 a1 ^/ k- P6 {             tag[cur]=1;
7 q* j; q$ |+ Z0 T! y/ u$ p             //初次访问，标记入栈; g! L/ b4 [/ F7 B. Z

; d  D8 [' M$ y- \             p=GetAdjVex(cur,pre);//p是cur的连通顶点8 ]. ]6 v# L, Q# Y' R
            if(p==-1)
$ i. w+ U/ ^  k: W5 z- W; \             {
1 R& Y, p9 U( D6 R* \$ a                pre=cur;s.pop();! e* I: n4 l1 C$ p
               break;
; X1 P5 Y) S/ y6 D             }$ ~& M, X$ |0 g6 o* D+ ?& e4 B: l
            else
  H( N# W  C) F  \             {
2 N. ~7 s. J! b3 Y4 V+ B& d                pre=cur;. o% P8 R  A, {: w
               cur=p;" e2 U0 y/ Z: }$ o  Y; ^
            }, l  K- _8 x2 q4 g  j5 |
* O" o8 w8 S" ?8 @7 E  T
         }
" Y' @; a# V" V' e2 f  a. i' F          while(!s.empty())% E! r+ v; e4 S9 x
         {3 w2 J1 m& ~; D- B
            cur=s.top();
7 t2 Z5 n) r6 n* U' B$ b& a/ c, w             p=GetAdjVex(cur,pre);
" G( h2 t7 A; R& D3 x3 G, P8 y             if(tag[p]==0)
- W7 D" F. j; C  @+ N             {2 }: H4 I9 ^4 d/ R! N
                  pre=cur;+ Q/ l- N- W8 X5 U, t
                  cur=p;
4 i/ l! E2 m3 c6 `                   break;( w$ }6 a9 B1 H2 n9 R: f+ p
            }
; U& G1 s4 {4 O: {3 Z" ^/ b7 h/ Q             else1 `- Q. Q- I0 K
            {- t3 k& o7 N. z* H
                  pre=s.top();
* I; $ z2 \2 f                   s.pop();7 T: O" q# X. \
            }
% W( W: J4 }- b. ?, W* G( n3 y6 F2 z6 ?  L& d  g
         }
! V& _+ U+ C& `5 E- Z8 D8 f: d3 [0 ~# z( I: ~: B- V- G
      }
. h- E* v; ^3 [ }7 ?) T$ o" {3 N, Z8 {. ^. H% Y
}3 w2 q+ a2 E7 @; p: Q, r' Y1 D
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
6 S. t3 H% F* k0 e{. ?' n8 Y9 L& V3 |3 m
for(int i=0; i<vexNum; i++)# H% ~$ ^1 n' u" ^: Z. I
      tag=0;
! i& e: X, u& S# a# ] queue<int> q;
" {2 B7 ^- h! `# M$ c5 W9 k int tmp,t;
) _. o. G; S& ~$ z4 K. B MultiAdjListNetworkArc<WeightType> *p;
& K9 u, X- Q- `; R6 T  V1 C for(int i=0; i<vexNum; i++)
* $ W$ Y+ N; p0 f- [# s {2 Y; i3 [0 g, m% U
      if(tag==0)& K5 ^7 I; Z, Q" Y
      {! O- o- _# j8 I9 N6 f$ T, P
         tag=1;7 x2 m5 F& z, P* A- H' z# g
         q.push(i);0 p5 A( K0 B  J9 c* n. q! f
         cout<<setw(3)<<vexTable.data;' X! `0 i, I2 A, c1 q! Y
      }
* e) r2 c! v1 u/ c6 p6 C0 {) `+ x0 s& h       while(!q.empty())
8 y) m" R; B! }       {/ T1 \( G6 E7 v0 C
         tmp=q.front();
- v" y. }& G" a& z, S  S5 a          q.pop();
2 }$ t8 s+ _5 i/ I4 R          p=vexTable[tmp].firstarc;. y/ W; ^: F. Y9 w' Q
         while(p!=NULL): k9 m% k# e) o! Y. Q8 N
         {
3 u' f! k* q4 t8 w             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);; C& m7 Z3 k4 j, d9 O5 M% a7 H# t
            if(tag[t]==0)1 B4 K/ p3 T2 X; x7 M$ ~
            {
. [2 r' {0 s+ c/ x! ?                   cout<<setw(3)<<vexTable[t].data;1 m4 ~. g( @! e& L& y
                  tag[t]=1;! A* S6 M  A( t. j. I
                  q.push(t);
, F$ d2 S5 a8 v, ~8 l6 b" l             }
, C$ T$ \! M) ]* W8 n3 q7 l             p=NextArc(tmp,p);
# Q9 g" T9 _  l          }
& W5 H5 D& i' e7 U       }
0 p# T7 @4 L! P5 ? }0 f8 O9 j! S/ q; T3 _3 d
}/ E, D; }3 g8 z. o
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()8 h/ E9 Q) O7 n: G
{
) x3 c" C. p; A MultiAdjListNetworkArc<WeightType> *p;
  i- {! b, X  ^& {, S1 M cout << "无向图有" << vexNum << "个点，分别为:";
& n7 c9 b  n; a  ~& ~* X3 K' j% b for (int i = 0; i < vexNum; i++)
- M5 \. d6 x7 o+ B% y" e4 j! I       cout << vexTable.data << " ";
4 q( M) M3 c/ h, e, O( h cout << endl;: F' L" i! [$ R, l% N
cout << "无向图有" << arcNum << "条边"<<endl;" ]6 y  N( t1 J; m* Z
for (int i = 0; i < vexNum; i++)
) s8 O' G9 O  H4 f( @8 o {
  B" y6 c# }( N9 d% F       cout<<"和" << vexTable.data << "有关的边:";& ]% C( s+ ]6 ]: S# U, a% A) i
      p = vexTable.firstarc;
  d( z5 t! O* g0 b7 m$ L. D! n       while (p != NULL)* a. q) H, l, c# ?: u0 v
      {
4 l- c( F6 B! d5 `4 V% ^& C2 D: m# e9 K          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";1 n( T6 Y4 \: @: C. L
         p=NextArc(i,p);
! H7 T6 v; B! ]  V7 s8 U% j: z       }
4 x+ @% {# _% J% t7 r9 Q1 r       cout << endl;
6 u  x3 }# Y. Q }
% Y( I- p$ c  o8 G}
6 {! ]; C+ `' [; u/ x4 \
) d" R: h2 I0 K1 ^1 v
9 p# `' O0 [) I: z! k1 w4 ^邻接多重表与邻接表的对比, F' x$ y6 a* K1 T- v* r* }
, w% _( W+ t# o4 h& i; Z
邻接表链接
6 f$ s) [$ T! E0 [) U0 G在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。, Y: ^; l& d5 r+ m4 @- J. I
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。* s7 q! j/ Y1 l) y/ \
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。$ A4 T5 @; C4 Q) w# a9 x
————————————————3 N% W+ a& _9 ^* k5 i5 P
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 g- A, x8 N+ K2 E& z7 }原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
3 L/ ]1 O3 [  H% J: h2 w, u
& p5 W, C. W9 k$ H" b1 l
/ `# o' L; G" A( O% M) h( w. S+ D& P  S

/ \6 l- X" q* N————————————————: |* b) g8 _8 X& S
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
3 E) D2 P' Z6 P, `* X) N2 @, M& H原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
8 e8 V/ G7 z; j3 i8 m# m  ?$ V* E  R" Z# e; |
5 o4 p8 [4 ~% U( e: T. \  M