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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
?4 Q0 b j, E2 H9 odata域存储有关顶点的信息；2 I; `% f: \! w3 S% M8 b6 Z
firstarc域是链接指针，指向第一条依附于该顶点的边。
+ y" Z" \4 h. ]0 I所有的顶点结点组成一个顺序表。

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;' T9 O# _7 r, G: [& A
for(int v=0; v<vexNum; v++)1 G0 }6 r0 p/ n* |
{: @7 B5 G- ^% S9 r2 D
      if(tag[v]==0)0 q% J) Q1 \' `  Q2 t- n1 Q$ ]8 i
         DFS1(v);3 R/ K- q( i) t& H2 v; X; m
}9 M2 J) b. C5 A5 I8 y% C9 E7 S
}
, q3 Y4 `7 ?+ t* I! o2 }: r! otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
  G  c, A9 r; I' u- e{: m; L/ S# |3 B
stack<int> s;
: E5 h) u- b% Z+ c4 J( F int tmp;
& M8 S3 W: `# x MultiAdjListNetworkArc<WeightType> *p,*q;
8 ~1 Z8 m4 [* g% h* w7 Y for(int i=0; i<vexNum; i++): s# J: l$ z' j8 b
      tag=0;7 P# Z% g/ Y! I
for(int i=0; i<vexNum; i++)- ^8 J  x6 u! _: [- M. H# C7 Y$ ^
{; {+ d4 F, `4 ?) x8 e( T6 F/ u
      tmp=i;
( _; Z! E* R; ~( e' b       while(tag[tmp]==0||!s.empty())9 Z- ^1 `$ V% ?- R, K5 |
      {
" E) _" x7 C7 @) G3 I, Z3 E' N          p=vexTable[tmp].firstarc;
: O" j; B5 I3 k+ |7 C& Y2 E' i5 x          while(tag[tmp]==0)
+ L) `9 C$ v9 }0 W0 l" t, |: r          {) G3 E9 s4 V  M, U
            s.push(tmp);) q; t: K0 c3 U8 N" Y
            cout<<setw(3)<<vexTable[tmp].data;
/ i* J% F% \! C: u# Z0 T* _             tag[tmp]=1;! O) G4 K( r% o6 S! t
            p=vexTable[tmp].firstarc;
- X( M9 Q8 `0 w             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
- ^3 d! w9 ~, e4 j6 [* F7 C             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
: m( ^" x4 x& I& B' x5 r! N             //cout<<" 1st    tmp="<<tmp<<endl;4 L: ~5 X6 f1 n
         }. u; G- G' c9 j5 x, B. T6 T9 S
         if(!s.empty())1 e- O# H/ F! x  T% b6 N1 W5 _" E! `
         {% Y( M* q- W! I
            tmp=s.top();
% g- Z0 Y+ i9 L  H! X$ j! G             s.pop();
4 x8 j+ l6 f- u; `1 l/ L; i5 \. r             q=vexTable[tmp].firstarc;
0 U0 j+ K  f0 o             int t=tmp;2 l1 L3 l1 N. P! J
            while(q&&tag[tmp]!=0)# }- \2 Y) L' N. s2 u
            {
, j7 e2 d+ |2 {( _! g                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);; [& L9 p" n# E# ^# @. k4 \
                  //cout<<" 2nd    tmp="<<tmp<<endl;2 [% ]  S% z# O
                  q=NextArc(t,q);! K' L# x3 j. \0 d3 h4 U! F
            }
4 O7 j3 x" C, g; l+ r8 {' W             if(tag[tmp]==0)/ R2 m5 X: r3 L0 M# h& l2 E9 g2 e
                  s.push(t);
0 x& p6 A% U* I  z! l9 A8 ?2 s             ///1、对应上面连通分支只有1个点的情况: e; G/ }2 ^# k, a% B( i3 N5 W
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
' I0 a- `" C( {& i$ M" t             ///tmp要么等于找到的第一个未访问节点，6 k* m: j2 @* T1 I( F
            ///要么等于与t相连最后一个点（已被访问过）
# u; n1 s. u2 G5 Y: W" f$ [9 T8 V2 y             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
) P0 y- B6 i( c3 P* q) ]          }
& ~5 ^6 G1 U0 X& F       }' M9 G0 b4 w- ]+ o4 D  L
}5 r8 R( i* d! ]( z% u
}
+ b) V  j3 M- r! O//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
! b3 E& J+ [0 u7 ztemplate<class ElemType, class WeightType> int
6 w6 g1 [7 D) i8 T5 XMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
" t: u: s  G- g. r* p. c* O{2 ~: i( d  j" I0 a6 o- B
if(head==pre)
4 _9 ~! x" I5 y/ T% _3 x4 A       return -1;
" g# I: M- x/ L. \6 s4 g6 O8 r
6 X( q' W1 E. e MultiAdjListNetworkArc<WeightType> *p;8 S9 L, e: w. Q" {0 l7 s. b
p=vexTable[head].firstarc;
% l6 h! m3 z5 V- s+ |. P- N6 c+ } if(pre==-1&&p!=NULL), I9 B/ H- N. T  H4 v
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
& [# T+ k  g- ]% X5 r6 f4 I- O; \ //pre!=-1&&p!=NULL
: N) g/ S0 X2 _( q+ N( L while(p!=NULL)8 ]! w$ D. l" v+ T+ ~
{
$ `2 v) S8 z* `4 P: s0 [       if(p->adjVex1==head && p->adjVex2!=pre)
4 c6 e' T$ t/ `- y* U* A          p=p->nextarc1;: Y& K" q+ w( i, |7 h& B8 |
      else if(p->adjVex2==head && p->adjVex1!=pre)
/ \, P: m* g0 e2 D          p=p->nextarc2;! c( |* ^" o" n+ M
      else if(p->adjVex1==head && p->adjVex2==pre)* e7 W7 i% b: n0 N) \
      {1 x* t8 x! F3 B
         p=p->nextarc1;
" F  @/ o. ~: c/ H# p          break;3 e/ H" z" z1 c2 L  I- r1 Y
      }
! k3 M. _6 U$ w       else if(p->adjVex2==head && p->adjVex1==pre)- c" X) d' c- C% J
      {) Q" X3 K( c+ ^9 D5 |5 n8 v8 r8 @
         p=p->nextarc2;+ G  a+ P! Z& `' P) b9 S
         break;7 ]2 R4 h$ O) ?' \. y  r2 N  c; ]
      }
; @1 Y; x' [) e8 z/ c }
; d5 C( C$ R: i7 @, Z if(p!=NULL)
& N. C' `+ H& |4 ^ {
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
( I) k9 v' O0 U" n( t( j }
: G7 X% C; o- ?$ F! ? else
      return -1;
) F0 t' Q# ?+ Y# t: p2 R( E) s}0 c& ?% _1 L6 L& K
) \' o/ Y& y8 l  ]. k# v: _

' {0 G1 C" o1 q& h- ?6 Stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
+ v* ?9 k& Q" R0 m; H; ]0 Q) x% A4 m{
5 f9 Y  l: e7 o; `, W stack<int> s;
: `% B4 N( \# g% ? int p,cur,pre;
/ ]3 C* U" q: b5 K( e& d' x //MultiAdjListNetworkArc<WeightType> *p,*q;
5 P4 K0 ]' }& U) |5 v: N; d/ O9 S for(int i=0; i<vexNum; i++) tag=0;//初始化
% i9 M- k- W4 w: f( G  ?  }$ }
, o# g& m  j: f! N for(int i=0; i<vexNum; i++)
. I$ }. n9 H( E/ |" I( G' m8 n {
/ o& n% H- {- g' F  L       cur=i;pre=-1;& u6 @- z! C: X& B  Y
      while(tag[cur]==0||!s.empty())
! [$ W( d6 r, g3 t6 H3 v       {
! {: s( N1 W4 s0 N1 _          while(tag[cur]==0): z$ j" E, b* B! K! i; R8 k5 H/ O
         {
0 @9 j0 @1 E' |) K# m  t             cout<<vexTable[cur].data<<"  ";
; l) |* S+ U: U  e  R             s.push(cur);
4 s6 p& o8 x) V# N             tag[cur]=1;
/ w7 C9 D) a2 c1 c- Q! b& R             //初次访问，标记入栈6 \7 C# d" d% D! d5 \! T* i3 w. _
" m" N  z, e, i: }3 i
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
: \! A( a, l* S, @- v, v# h             if(p==-1)# V+ E1 p, X( [; T# \2 B
            {
% O; {* p! O  l  a- e* s9 c) O3 y                pre=cur;s.pop();( N, k2 R# z5 d8 Q* z$ U
               break;
( Y2 W; Y" P) ]2 I8 w4 V             }% J/ G7 ^/ q! ?% Z( K/ L
            else& J0 E/ M1 q( O* l( G' ?1 z8 ?
            {
. }( l& {; W. k                pre=cur;
3 ~- t' c1 g5 Z- ^( p2 g                cur=p;
% c3 I: C0 g" q8 A             }$ b0 y% w- Z- ~
$ Y' p6 S" a5 p2 u/ f5 s( T
         }5 k# q' @9 M' A4 L# {
         while(!s.empty())
9 _. F9 e0 {/ z. a# }$ q          {
/ ^1 x2 G" K! Y" h. y             cur=s.top();
8 L, q* Z1 A+ Y' O& t4 X" s             p=GetAdjVex(cur,pre);
, c0 m: \( S6 b  e. V             if(tag[p]==0)9 d2 h( P9 o- ?- k! g* ^
            {
/ c9 }/ u8 I) h* `6 ~                   pre=cur;8 M2 u* ~! _; f
                  cur=p;
1 M& F4 P0 O- W                   break;
7 q2 T' k) ^- `  R' w             }
* b1 }' _! S) Q, U             else
6 ?, d* D8 |( A7 k5 s( g             {3 d3 j3 D/ a: t- V2 L! R( }* z
                  pre=s.top();; s, a5 h, `+ m# q% B9 n; s
                  s.pop();3 W( v' r) p) e$ D
            }" {4 e! V# g; u' [& f; Q2 s

' Y3 V  m6 ^  _" d& T          }4 o/ c/ p* D7 V9 r( w! h/ Y0 U
6 [7 m  t" Z2 H; v, t! q# H5 C
      }8 }+ {! E1 f- f
}4 {3 q) b1 q& T) d  M& ~5 E
}
+ O% a: r  u$ F  O3 h3 K( Ktemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
; U( M2 o, k  H' K{- p4 |. p9 r& ]/ U3 r- B
for(int i=0; i<vexNum; i++)
' J# E$ j  R" I! @1 I       tag=0;9 C6 j- i( ]* s: P1 N
queue<int> q;
$ t$ q$ q$ o, P0 [' p int tmp,t;
8 |+ e  M3 Q+ f7 _- R2 {- `9 s. L3 ^ MultiAdjListNetworkArc<WeightType> *p;
9 W3 c  y2 v5 V! v0 ?  ?. D for(int i=0; i<vexNum; i++)& R: G- O4 U# k+ Q# z3 L
{
0 n) G& D2 V- ]" F       if(tag==0)
2 C$ `: P- {' h- I6 m8 ]       {
  p9 ]( T6 }/ [0 c, u$ g3 z, A( m          tag=1;
6 s" s% M9 ]- u* ~, S% X9 C! y          q.push(i);
2 S$ F3 [' K! _  `. B          cout<<setw(3)<<vexTable.data;
6 T; }$ N8 ?/ N. R       }
) T" M. x/ ^8 N% U       while(!q.empty())
" v7 I* r; m: v( L. C- X       {
" C( [" h( f7 o; }  S% l          tmp=q.front();
- z" N0 D' d! d$ X4 W0 L          q.pop();
6 k; ^! E$ O- r% [3 v; I0 K! D9 g          p=vexTable[tmp].firstarc;
1 |1 w6 R; ~  t' w' I. v1 |          while(p!=NULL)
0 j$ a! N( P5 s- M2 ?; ^. `          {
4 M2 E6 s% ~0 G% u, U5 t* ]+ d             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);5 l* {  `  b  t
            if(tag[t]==0)8 ?5 B6 x/ v) H1 ^: l9 s+ ]( p
            {
  k; Y0 A/ {$ L9 F) I                   cout<<setw(3)<<vexTable[t].data;
, V, Q, C6 T! ?6 s" a8 D7 l; u                   tag[t]=1;: V: r& Q3 A6 K; Y. J- S7 g
                  q.push(t);, j) |, [  c/ z. g+ z
            }8 M0 I! O: u  K0 Z9 }
            p=NextArc(tmp,p);
2 w' o* q6 e4 G5 ~          }* i: Q# J. S% k: b  K, w
      }
! K% R" |/ d( t4 u! h7 h# w* a }4 [6 M7 m5 G! e0 b
}# A# c/ h0 O, Q2 _
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
3 {7 M) g& F9 `& x1 i{) n1 Z0 u. \0 \& N
MultiAdjListNetworkArc<WeightType> *p;5 W  T$ M- O- G. s" ^: ]/ h' N
cout << "无向图有" << vexNum << "个点，分别为:";
, O: v+ \$ r$ Y' l9 p for (int i = 0; i < vexNum; i++)
1 O0 O3 m6 D1 a9 @: I) v8 _       cout << vexTable.data << " ";
) q) [$ F5 \$ p0 D- R8 B8 ^ cout << endl;
0 N* d( n7 ~$ X1 E8 ^& s( R, u3 B cout << "无向图有" << arcNum << "条边"<<endl;
5 t; O0 }5 ?& o" B for (int i = 0; i < vexNum; i++)* W) y7 a5 G. }( ]7 c% Q: R
{1 B3 ^5 f8 u+ R. d
      cout<<"和" << vexTable.data << "有关的边:";
: ~, Y2 l5 \9 T+ n, `/ ~3 r: u       p = vexTable.firstarc;: \. ^& M' K  R, w" z5 u& E
      while (p != NULL)
2 ?( e# g0 _' V( p" J3 L) D       {
6 e9 y" J& X( L; k/ Y          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
$ B; \. o0 h+ M" F; v9 e+ \$ O          p=NextArc(i,p);& ^1 ?, D7 m% s, v
      }* c# |7 X/ G7 f- w' R
      cout << endl;
, _3 C3 t0 U5 \) `% o, [ }
  Z# h4 L% h1 [8 ?}2 a  n, k( {4 D% S& I$ J5 g6 j

* V/ m! F8 Y& b  u# D
* y& `/ ~7 D8 r( v6 X邻接多重表与邻接表的对比2 n8 U' [+ K: o: Q6 q
) H% m8 J* o8 l2 V  \" b& a
邻接表链接. G' x. [/ W  N' w, k
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。" }  o- \+ b" }. m% i( u. g/ l
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。! U- r0 }& l3 V: o. ^, r
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。0 \1 h+ i+ ?. Y! O( h
————————————————
, `% K& K" [6 e% m7 Y; U6 S; g版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。) f- l& j' E( m9 s
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
, Z9 I) q* o" j. E: o. w$ b1 o' c
$ r  ?# U2 T: u* w8 W3 g' |7 m( I" a
/ B  c6 O- o  Q1 z6 T' `; d
$ S0 L$ {) r+ Z8 _4 b" @/ u3 B  z
————————————————
+ m8 R, _/ Q1 I0 Y) ~* U* x版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 {( ^/ N) H5 w% U! G原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
  b$ S! w/ a+ r5 h' G$ m
$ Y2 ]% H: R9 Z& P5 A! ~6 v# e. |: o  Q4 o$ h( Z+ x$ K! E