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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
# D( [7 G) o7 H: N0 x8 g, adata域存储有关顶点的信息； K W" ]9 T& Q% Q) R9 l) F
firstarc域是链接指针，指向第一条依附于该顶点的边。
0 \: l+ y4 P, X7 v! U! R s; c" Z2 J所有的顶点结点组成一个顺序表。

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;' K! K2 q( f+ G2 O, x; X* R
for(int v=0; v<vexNum; v++)2 {7 _/ b  A. `* \. F
{
' n9 F. H0 }' E" K$ X       if(tag[v]==0)
1 X: ^; C/ `, [1 Y          DFS1(v);
: y) E  }5 _* E2 l9 ^) ^ }
5 d$ V; t1 `8 F7 S4 c8 w}
5 {( r  V* f" x" L8 Ptemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()$ U- j/ c0 L7 n8 N$ {
{
% L+ |9 R# ?# V( l* Q' s' t stack<int> s;
. f6 j* \# T5 U, t int tmp;
. Y: H3 l# N% C+ ^7 b' e3 |/ N MultiAdjListNetworkArc<WeightType> *p,*q;
) n# m9 K( Y" y% o7 L" S) s for(int i=0; i<vexNum; i++), O2 v. v$ v/ e4 K% N6 ^
      tag=0;0 e  t( ?. H2 N5 o# Y7 m$ T( t+ D
for(int i=0; i<vexNum; i++)% c. N8 K" i0 g4 z" g/ p
{
. G3 Z3 a5 q5 n, m& r       tmp=i;, `3 n( `8 q4 s/ D$ c5 }7 p9 e
      while(tag[tmp]==0||!s.empty())& C5 T4 v/ ~2 N" H) v( p
      {
' _% w6 ?2 C& M+ P9 `  N1 g          p=vexTable[tmp].firstarc;. C5 ^8 G( O5 p. f
         while(tag[tmp]==0)
' r6 [4 u. d3 c* l& [4 c# l( A          {* t7 c0 W* T+ B4 g2 I
            s.push(tmp);
8 w, u: k* V1 F) p' {7 f) p7 b0 O             cout<<setw(3)<<vexTable[tmp].data;8 r( }7 u( _2 T, p# v( T( W
            tag[tmp]=1;& z  J8 X1 c( G: g6 ^2 o/ L: ?% Q
            p=vexTable[tmp].firstarc;& j. |" ]- O; Z
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
: _: H: S4 N3 W: A# x# M             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);' _" I. O3 \, \0 o/ {! K; M. j
            //cout<<" 1st    tmp="<<tmp<<endl;
9 W+ Q& B% @! a1 {          }/ a+ S6 X  S; S9 z' q8 h
         if(!s.empty())
% f2 K  r4 N5 o1 ]          {0 t4 j4 \4 ]5 T9 \* _3 D
            tmp=s.top();2 B/ i/ A& \6 O. a. p) J  N- O
            s.pop();
' N; U( D3 _* b) d6 h3 b             q=vexTable[tmp].firstarc;
6 d: D8 z- }) G, ^! ]             int t=tmp;
1 h: L+ n# S. k* s7 b             while(q&&tag[tmp]!=0)* y! V! w0 H7 E$ a+ i2 \
            {2 q2 }& I& q  @2 u0 S
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
# J% A" t0 U, X9 Z$ R9 B                   //cout<<" 2nd    tmp="<<tmp<<endl;
( ?- f$ l8 r' ~6 C$ n+ B( L                   q=NextArc(t,q);
3 z/ m! l1 f' T5 \+ X: i             }
) E1 b" B( l9 Y             if(tag[tmp]==0)7 I, S, T/ D: q- |% f7 X4 H
                  s.push(t);
* |' @  z8 v1 s9 W* Z7 r. `             ///1、对应上面连通分支只有1个点的情况  \9 k- i. E) n5 k( R$ o: ~
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈9 J& u6 c0 T9 G$ @0 w: Q6 u% ~* ^
            ///tmp要么等于找到的第一个未访问节点，# B8 Q% ^; `4 {7 x) p) z/ B
            ///要么等于与t相连最后一个点（已被访问过）
4 i4 L$ ?$ s. l1 E             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点/ N/ d  [, B# A  U
         }
  U1 m7 j7 t4 c, V  a       }
4 {* X- N& `" k; S+ n4 k" ]  @ }
0 ~1 ^( n0 `% ]8 h$ `8 R}
( t! s3 m4 ^. J6 q. X* Y9 }% X0 b//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
. D, g: K! r4 U# \7 L' |" X8 ]template<class ElemType, class WeightType> int$ X' [$ A& l. ~/ }; |% W0 S
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)9 {! t/ w, R3 \! t5 B
{9 I+ H2 h! ^+ C- T( S, X# m
if(head==pre)+ V* p# x# w6 s- a
      return -1;
: g9 L- H' @% a# M4 k9 u! n
# g+ Z+ w0 f* `1 y MultiAdjListNetworkArc<WeightType> *p;
( }4 I# n2 v' p3 N! P( [4 b; S3 f p=vexTable[head].firstarc;3 r8 Q3 f1 K* h& d
if(pre==-1&&p!=NULL)
/ T  Y" w: Y0 v3 a       return p->adjVex1==head?p->adjVex2:p->adjVex1;+ T) ]- I+ `4 E# X8 U
//pre!=-1&&p!=NULL7 C& W1 b4 {9 t1 w$ y; n* g& H/ B
while(p!=NULL)
1 O! B& n: M2 I- B+ {6 o& I1 { {
$ \  P" c/ v4 f3 v( ?       if(p->adjVex1==head && p->adjVex2!=pre)3 P/ m9 |* J& @: b& M, H' J
         p=p->nextarc1;
9 V. F$ R# @0 W1 O% b: @6 x       else if(p->adjVex2==head && p->adjVex1!=pre)
" q( ~" A2 E+ v          p=p->nextarc2;% v. N( {( q" W7 Y( p& I
      else if(p->adjVex1==head && p->adjVex2==pre)/ w# X. a: [$ G3 d
      {
1 g% d1 I. B0 T8 Q/ X% r% }# N* S- m% ^          p=p->nextarc1;0 k7 x) {9 ~$ G5 L
         break;
9 J; q2 g$ B. f0 L5 a* b. L' H3 E       }! n! i4 [! h7 d
      else if(p->adjVex2==head && p->adjVex1==pre)
5 q  ?! b; S) E! a9 B0 S4 ?0 i0 z       {4 J; |2 V* D% {, S8 ?( K
         p=p->nextarc2;
% k( l- [! g8 w( |/ z; y          break;. ]" I6 _% c6 Y# @, `" S% S) j+ W
      }7 M6 M+ v. [1 J  l3 q: i
}' {, p2 \% S" [5 h# N4 k
if(p!=NULL)5 Q& H, {- C4 ], {& v
{
  H" N4 W+ P3 a7 `: }5 Y       return p->adjVex1==head?p->adjVex2:p->adjVex1;( y3 b2 ~3 y3 ]. \
}
+ \; M% O1 s# r0 ^ else+ _2 _: ?# b1 ?3 {# h6 d
      return -1;, H( S+ S: p% X6 E$ t
}% m' E" K6 b$ k" q% Q8 p! N3 S) }3 L" a

: s2 @% p6 f1 i$ B" v% |2 x
* i# I) \) n& U" R3 d! f; t9 Ftemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()4 s  a: s4 E2 a  [2 W* w
{
8 R: T" x* \/ Z$ q# L6 l) e stack<int> s;$ Y6 g; W6 s! n4 y
int p,cur,pre;: p6 {1 _8 u$ u. t  ^- }, d
//MultiAdjListNetworkArc<WeightType> *p,*q;
& o, G# O6 k7 R# q; t! f+ K for(int i=0; i<vexNum; i++) tag=0;//初始化9 I* H7 D2 i- l, C' u8 F
  a; u7 k. h* j; I
for(int i=0; i<vexNum; i++)
; P  `! C4 _. y. T  y {
8 r! ^3 T) u' Q" b3 Z6 D$ e       cur=i;pre=-1;& r# d% s+ V. v' Y7 d' z
      while(tag[cur]==0||!s.empty())
% s( I) Q# }2 {: G       {
% e2 U  ?5 u# `; Q! l9 q; `* O          while(tag[cur]==0)
" S3 q# J$ U" n. r' E- y          {
# H& |+ @1 Q+ G1 g             cout<<vexTable[cur].data<<"  ";5 H! k5 s* U9 j% _$ m1 y( t" Y  v4 _
            s.push(cur);
; b. Y$ J9 S7 T( W: q. Z. K6 ?; D             tag[cur]=1;
7 B% l8 G9 S1 g% \4 ]             //初次访问，标记入栈
) g$ E: q; D3 @2 q* D: T4 g: c5 D: N6 e$ k' J
            p=GetAdjVex(cur,pre);//p是cur的连通顶点- M% E5 g6 v2 D8 ?9 Q
            if(p==-1)7 I; s8 R* c8 z0 p% E) j- Z- b$ T
            {7 y3 C4 j: J% x$ }  _( a" t
               pre=cur;s.pop();1 [* D# z  H$ x
               break;' V0 N8 o; k  x8 f4 ~
            }" Y/ O! q  f" T% @
            else
7 O0 b$ L+ V# r0 h' q+ y             {. v; K9 {( W2 S8 u+ L8 F; ^
               pre=cur;
/ m. H: q; Z+ u$ y% m                cur=p;! ^% _8 I# H, [
            }; \% s9 r% a4 q

" m7 {, o) q6 B# {( \( Y          }
& @6 T7 S1 v6 A8 a8 G          while(!s.empty())# g0 y; k& z$ ^9 _( h
         {7 a3 n% j: l4 o$ e
            cur=s.top();
5 F8 T- {( D0 q; U$ ^             p=GetAdjVex(cur,pre);' U& l) A: V6 N! }$ B
            if(tag[p]==0)1 n7 ?8 S/ D3 Y1 \
            {' ?, s, q3 R- P# M
                  pre=cur;
! g) ~$ `) Q+ c2 s$ g  y- b                   cur=p;$ v4 ?, d7 g1 ~: }2 [0 ?
                  break;
# I4 ?" k- {$ m, u% N( E+ z3 w             }% ]7 }4 f* T# O; ^1 z2 J
            else
  c3 y/ Y& `4 ^3 P             {. F4 ?! N5 _  J: H8 P2 a
                  pre=s.top();
4 C" W7 f; q! a  V5 P6 G: h                   s.pop();" P$ F; H% `$ b1 I- l
            }6 y8 H4 q% |0 e  u, _( w: i% g

6 s1 Q' [, R+ z4 _1 h          }
5 V' B* y- t. N! Y% z# I4 V; R& d6 X1 t% n+ t- o
      }" S4 [. g3 O" M4 K1 l6 D0 U  ]
}, Y& P; o* [0 S+ I* F
}. R7 F0 }, t! x& a8 @7 }
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
8 C2 t* O: {( u% \: z! C{
* j( U6 v' \. c: a9 @# f. d for(int i=0; i<vexNum; i++); T! y; D/ U4 T- V/ v: L$ k
      tag=0;0 d! i# P2 m# Q, q: U
queue<int> q;
, I# M& a3 H1 {4 J, I2 } int tmp,t;
% \$ [: ]! L( h* C6 l MultiAdjListNetworkArc<WeightType> *p;3 Q4 y( D9 n6 v- [' O
for(int i=0; i<vexNum; i++): [0 }# m- e2 K, }& A" \2 T
{3 {4 }3 w$ o* j; M/ ^. z  @" P8 P
      if(tag==0)4 s. M& W* m- ~; c, J  R
      {
' G* ~3 b- F$ e$ k          tag=1;
7 L- q% G5 I# _' D( M* Y          q.push(i);, e2 B& `9 v+ H$ S8 q6 y
         cout<<setw(3)<<vexTable.data;4 G1 ]( }3 l; r( B- q: |
      }# @, H5 \3 n% I. ^4 [' B3 w6 t+ x# p. W
      while(!q.empty())* P" c- x0 k( L+ e4 X" X8 E
      {
4 l; A% s- S1 i  e8 e6 I          tmp=q.front();
" f7 S: v/ ?2 r, F6 p+ Q          q.pop();! b6 O! r# Y) J9 T
         p=vexTable[tmp].firstarc;5 l; c% h0 C: |9 G
         while(p!=NULL); s  H7 _& ?; N: `  i
         {& K1 t/ d/ T$ j/ s2 u' l) Y
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);0 t7 e8 w8 l& \1 E3 B, y
            if(tag[t]==0)
( ~* @7 X4 r5 u$ x* D' A             {3 v6 \5 G( K( d( [+ M* b
                  cout<<setw(3)<<vexTable[t].data;7 T" G) }0 [, Y# L2 m6 ^/ s
                  tag[t]=1;
                  q.push(t);
) U% e) n4 E  G             }
: a+ i- t4 V) |9 ]2 ^8 t+ V; M# @$ k             p=NextArc(tmp,p);
# D' ?2 X, `. ~8 _; f          }
( O" t5 d  I! ^& x) ]6 z' m! G       }
- i1 a$ u$ G7 {" f- k }
% [' U9 z( d/ V, E; o; {( u}
9 [' q7 j$ r; F! K/ m+ P, |3 ktemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()1 M1 _* D( P* b7 s
{3 w2 R; i$ U* `6 @9 |
MultiAdjListNetworkArc<WeightType> *p;. {4 d' p& t$ f# z% c, w0 {4 Y
cout << "无向图有" << vexNum << "个点，分别为:";. w- o: }) h% X# J4 K' t
for (int i = 0; i < vexNum; i++)  M/ c: y) h) R/ h9 W8 }7 j6 _, {
      cout << vexTable.data << " ";8 A/ _/ u) h+ P7 s# M: `
cout << endl;: K) S9 M8 q0 c' P/ i
cout << "无向图有" << arcNum << "条边"<<endl;
3 u! y8 c$ a, t* y5 M  f' P for (int i = 0; i < vexNum; i++): o; W$ q* n2 h% }
{! [$ [$ T9 x' ]: _' ^2 I8 ~1 o
      cout<<"和" << vexTable.data << "有关的边:";
6 S% T+ i7 h& o       p = vexTable.firstarc;& }5 o! A9 f7 x! F/ a6 m' W3 ^
      while (p != NULL)
5 O2 X  N+ ~. q: E' G5 o$ J. f       {# \$ B4 }5 }6 S! o7 w2 ^3 V' d
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";. m/ @$ E3 w4 ]8 b3 c
         p=NextArc(i,p);
0 E3 ?6 K4 X& d& a       }
3 C4 m$ `' |9 B( O) r0 O) T9 ^1 h       cout << endl;
0 m6 [1 @" o. J* s4 r }6 Q3 W2 Z" A" `; _" {
}) w! R* ^! B, x0 ^; q" {8 s' |
1 x( X# r: X% H5 q

: l5 U+ V+ x2 _4 N0 M邻接多重表与邻接表的对比6 H" `" _9 F6 g+ r% x; a5 W# Y

" R: [! C% H$ `; }, E邻接表链接3 G. Y% j6 B* O# E5 H3 v
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
7 o. \, y0 ]8 o6 j6 a. r; z在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。5 o$ l% \# c8 `& e0 R4 g
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
  a2 n2 T! K; K6 y& f% q————————————————
' t" [/ C, ^8 Y& a- T# C0 f7 ^版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。% s) {# ?3 L. s1 B: T) w" R. X
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
$ Q7 z6 {* Q% r# B6 D  s( I
% {  p5 s6 ~2 o9 `6 A0 c! V$ R. ~$ g; D% X6 T0 q

" A) I$ T* L' F' U0 K- V+ G$ y* Y0 C+ c0 _  N9 |
————————————————# A8 m) c( C  a! n* `# O
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。+ p9 w2 o# u% |
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669584 P1 S7 E5 @: I% w- ]5 b& X, V

. A$ `" Q6 d! K5 @0 U3 y
1 p. ~  Y' D- U1 u! r