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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：! `' l. s7 i, ]0 I
data域存储有关顶点的信息；
! R' D( A0 z* F, A7 bfirstarc域是链接指针，指向第一条依附于该顶点的边。/ ~) T( I$ A9 l
所有的顶点结点组成一个顺序表。

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;
+ j5 l( I6 `5 d1 d8 a1 \/ n for(int v=0; v<vexNum; v++)" E# |' \; W: ?6 c# }
{8 K; U% I& Y  o, U$ c: C9 ~9 p7 Q
      if(tag[v]==0)( I# H/ D( |. E. @+ o
         DFS1(v);
3 q; n: \& E# w( J }
+ q% o. G  X! l- w  |) b}; t0 R% j! [6 {5 |
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2(): U9 c  @# C" n* j$ B
{+ q+ M/ m% D* x4 X6 h# ^
stack<int> s;* C, x1 V4 S& @
int tmp;* H4 [. ?) `. Q: c: f
MultiAdjListNetworkArc<WeightType> *p,*q;$ W* B+ o, x! T7 Y# n1 f  y6 Z
for(int i=0; i<vexNum; i++)) c5 D0 E1 {; @3 i
      tag=0;
* r# U+ G) t% K  r8 e$ l for(int i=0; i<vexNum; i++)
3 p+ [3 L9 ^8 z6 @2 j- U, g {
- L2 E% {( f) s6 y) H. f# S       tmp=i;( Q* N* d6 M0 y& u) H& Y3 \
      while(tag[tmp]==0||!s.empty())
% E) V* l0 o  Z5 @9 y" l       {
! W; }4 ]' e% M! n. K1 M          p=vexTable[tmp].firstarc;
5 n, ?$ m) c1 \& ?5 ^          while(tag[tmp]==0)
2 n2 i% U6 f( l) s3 J2 @* T          {8 j1 a) x) G) j" Y' _7 I
            s.push(tmp);4 |" _- Q" Y* O; v4 a5 A: L
            cout<<setw(3)<<vexTable[tmp].data;# v& z$ {0 q2 O1 d9 w
            tag[tmp]=1;! x" m! C* O0 o# z* Z1 L
            p=vexTable[tmp].firstarc;0 W2 D" f9 j( }# _4 @
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
) f# H$ I. ]8 G0 G6 q' r) D" T             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
" N- F8 ]2 z0 W- H/ l             //cout<<" 1st    tmp="<<tmp<<endl;! w. W) }! \. l5 D- k( g, M
         }- m* c" q5 q- y0 X
         if(!s.empty())1 q: w1 x, N& L- h# L3 N
         {
" J$ r$ d  X, s3 O6 D6 w- T0 |             tmp=s.top();
7 ~, x& Q3 O6 f8 R! X% z' @7 [% C             s.pop();
% [. r$ Z. i/ W, m4 U( e             q=vexTable[tmp].firstarc;
  D; U7 M! d6 I- f6 g7 r4 M             int t=tmp;0 [" l) g7 ?3 X. X' p3 g5 q- a
            while(q&&tag[tmp]!=0)/ b5 C2 Y+ A9 k" z0 \3 p
            {
1 \" H; e6 _7 T. N& |' q                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
+ ]/ n) I6 Q3 B9 F, f' W                   //cout<<" 2nd    tmp="<<tmp<<endl;# t- W; c6 @8 F* A
                  q=NextArc(t,q);
$ P; t" u( V& W6 j             }
. B2 D! p+ r. C# s" o" H0 s             if(tag[tmp]==0)) N: N% W+ B) y& r. w: q8 ]
                  s.push(t);
5 Z+ A* k3 p& a$ |- v! x             ///1、对应上面连通分支只有1个点的情况- a/ [; D) u) i8 c$ V' P: b; a# V
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
0 s  u; F9 f' d% P4 _9 u             ///tmp要么等于找到的第一个未访问节点，
: n  p" K" _, h5 ]9 z             ///要么等于与t相连最后一个点（已被访问过）6 N9 Z1 q  d& [
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点2 S2 Y. I) F0 p' S; Y+ e' ]
         }
5 p6 t9 i( l9 L/ d7 t. \       }4 B1 ?1 l9 }( [! ~% f1 `3 q
}: ?0 B8 K4 F/ g! A
}" `' R6 M% w7 E+ S9 Q
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
& a6 m( W& p1 ~4 otemplate<class ElemType, class WeightType> int, @5 @6 A% a" E& c/ P
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)( j: x9 B! m$ y. p
{4 ~+ }- q- n+ E* {& r8 a6 z
if(head==pre)
: g$ y2 n7 R! f' z       return -1;/ s! o( {: R3 S7 s
& D9 J. Y4 [8 k3 `% W- B
MultiAdjListNetworkArc<WeightType> *p;3 H7 f9 m1 i0 a8 K2 E) i
p=vexTable[head].firstarc;) A- H' e. n0 y9 _' O8 ^
if(pre==-1&&p!=NULL)
- S( T( U1 G6 m, |       return p->adjVex1==head?p->adjVex2:p->adjVex1;
% r* g: d- O% D, o! X //pre!=-1&&p!=NULL* I  L- w; A1 f5 A0 s
while(p!=NULL)- V+ |5 |. q4 j; F% Z
{; ~3 M! G0 I; @- H- U' H
      if(p->adjVex1==head && p->adjVex2!=pre)
; d! h2 O8 x% w2 O1 n  `* g          p=p->nextarc1;
( Y' {4 L/ _3 M. e/ ^% U       else if(p->adjVex2==head && p->adjVex1!=pre)
# q! I! D0 c% u7 f; i% ~          p=p->nextarc2;
- a, x6 {2 d  l2 o9 h- t# j       else if(p->adjVex1==head && p->adjVex2==pre)
/ X  H" ~/ d3 u! |8 R0 p( _- h       {
2 X& P* S7 i+ V          p=p->nextarc1;' |( c! V, d, g
         break;
! d/ q& C" O% [7 \       }
- G; n& x' V+ K: p. W- S+ D       else if(p->adjVex2==head && p->adjVex1==pre)
% F4 v4 ]& S, h8 z: h" @       {$ W* N2 k0 X; d* [* l' C
         p=p->nextarc2;" q1 _8 P' e; R. g( m
         break;
4 e6 j) J) }! y( D( r7 {8 H! E       }
  @0 I$ p- a6 H7 v4 p4 H }
2 Q& ?4 |; N8 s1 B( N if(p!=NULL)' t  n% f2 h; F' }& V3 V+ O
{- j2 N. s! w: Y5 K
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
- w9 M; V9 e. a5 Y( P1 k }: {" f4 C( M0 J3 @4 G" Y* a5 t# q8 e
else# k5 \1 }& B! ^/ A
      return -1;
# J2 B  J- a1 P}
* Z7 Z$ }2 s, [, O: o; U3 h: N+ b) v: u7 X- H  w" ~' G; I3 g
& J8 |0 y% \5 X9 D+ v% f( ]
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
3 B$ l: B9 y. U% U6 W' n{2 e  d+ H" R  ?3 B" G: @
stack<int> s;5 l  u# o' e: j+ Z
int p,cur,pre;
3 [) I  U3 a4 z1 n7 |( K; B //MultiAdjListNetworkArc<WeightType> *p,*q;4 [* _4 l9 h  }8 D/ J8 X/ C+ T+ l
for(int i=0; i<vexNum; i++) tag=0;//初始化
4 e6 I, C7 q3 \" F! R# a; w9 p! A. m1 l
for(int i=0; i<vexNum; i++)
/ K) ]6 ^2 R, |& P, r. C# I {
5 m6 f* U0 Q4 W# ?  B       cur=i;pre=-1;$ d1 S- P9 J) L% o9 O
      while(tag[cur]==0||!s.empty())
5 h$ @7 @2 A. \1 Q4 p0 l5 @       {1 j1 Q1 R. m/ c; G$ k2 ]+ o- Y
         while(tag[cur]==0)% c0 `$ d/ g$ }6 n6 T# `: L
         {
0 Q1 |7 o, D$ X$ h0 T3 ^             cout<<vexTable[cur].data<<"  ";
0 x7 z* k' U% B. ]! b/ J' N* @             s.push(cur);
, z. R2 Y/ Y2 u             tag[cur]=1;
/ `& ]  m& u, k0 b0 b- v             //初次访问，标记入栈
0 W1 p" k8 f* o/ H& o9 K
$ ^" f/ z% x8 I+ u. H& q) T9 _% Q             p=GetAdjVex(cur,pre);//p是cur的连通顶点
& _- J9 o5 o$ P, L7 V9 t             if(p==-1)
            {
+ i2 ]$ m/ ?& f& F* t4 t                pre=cur;s.pop();, E: U+ W9 u" i* E
               break;
. F) }; T$ }7 [5 d  g; Q             }0 Z! R& [/ U+ @+ M
            else
' S" J1 n2 M8 ~! f             {
( f3 y" n* M6 q7 E+ e                pre=cur;
" D! p( j3 r, T% V. F9 ]1 g                cur=p;$ A0 ?( G' I: C
            }
3 \/ c- C) C) S4 `. D+ r  X8 m+ m% l# e8 `3 J% q  y" s# k. e) W
         }: z% @& v  d* r
         while(!s.empty())
/ u/ D5 U; ~& x! \          {
" [7 i( E! E% F5 g; s# c             cur=s.top();7 `. C' z. y4 t7 _) n6 r
            p=GetAdjVex(cur,pre);9 Q! L; [. {2 Z6 z( ^; A9 y* B
            if(tag[p]==0)
3 x  h, z4 q1 Y& b* R  I4 `; [             {
. b1 p- @' R  j+ Z2 R& g: a                   pre=cur;
                  cur=p;
5 e9 V; y- W3 f' T: h                   break;' Z6 E2 c1 g3 Q" F" f+ ^
            }3 Y% v! s  q* Q2 n. i
            else
7 R0 w! Y6 e4 o6 e             {5 m# n/ t( w" j& d5 X
                  pre=s.top();, i6 t# Q% B) B& e! q
                  s.pop();
: i' Q: w! I5 ?) s3 K* {. v3 i2 z5 d             }
6 [6 c) D& H9 O6 E. S9 T9 W  s  _5 a  y1 V
         }
  s+ |: H8 E$ L: U( B3 a% l! F3 c( Z. l- P# _5 a
      }2 S0 M  J; V+ [; _  h
}
) d) O1 Q1 h% c6 j}( Z8 A9 V8 E+ e/ r! S4 \4 p! X
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
5 y. @# _( e( f- ?& P{
5 Y$ c+ Q) f7 t# P' t: S for(int i=0; i<vexNum; i++)
& E% a8 }6 k" R! @( C$ O9 F/ J       tag=0;
: [! F: l% m* l7 u& G queue<int> q;
4 x$ \1 ~0 a- y( a! `1 s int tmp,t;
# S" S" R' X! F& I* l3 @) ?) g MultiAdjListNetworkArc<WeightType> *p;/ a' c6 ~( v5 k
for(int i=0; i<vexNum; i++)
9 P6 p! a0 G* ]% p1 u {: G8 E2 E  P& s$ U) j" n6 G
      if(tag==0)
, c" E' |1 Z# d& j6 R3 p       {
+ l; X% e, i9 Q0 d6 ]          tag=1;+ E! o$ k4 c( p
         q.push(i);) t. C1 O: j. I- |6 t) p& V# ]! L
         cout<<setw(3)<<vexTable.data;
- P# l3 B/ D% p+ g# b! m       }  s6 ^. T5 ]4 P: g  p2 J
      while(!q.empty())% D" F# I8 l/ `! \9 n& g
      {
$ S) r2 K: }* |* K4 X, B% Y          tmp=q.front();
7 J/ t! t  X: j% w          q.pop();3 C# w$ L) F9 R2 Z6 ~
         p=vexTable[tmp].firstarc;- s4 O  h% p3 ^- U4 X9 R
         while(p!=NULL)
! k- N$ N6 V2 l! V9 |          {6 d# N% x! \$ g- v0 L
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
* W( [$ k7 M5 ~. k& q             if(tag[t]==0)( m. K8 r& N( u3 n* e+ Z
            {
+ p/ J" @6 ]$ D; Q0 m$ T                   cout<<setw(3)<<vexTable[t].data;
+ V! m# _# P/ ~- [* x                   tag[t]=1;6 z2 P: v; ~9 ]6 E
                  q.push(t);
9 S) L* X1 k: C7 L! b0 G5 R5 k             }
' o) \  l2 D# N             p=NextArc(tmp,p);" D5 Q' ?1 g% v% K7 |/ E
         }" u$ ?3 Y! {+ a) O6 M1 x
      }
( F% h4 g6 A: x; I0 b5 c }
* q, b) q3 {1 a+ @  ~1 \6 m! K}
5 p2 l- x3 }% g8 a; y: q7 Y, ~5 jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()% X3 H) O% T$ u3 O
{# p1 i  G" ~6 Q  }- z% f- p0 @9 g% A1 A
MultiAdjListNetworkArc<WeightType> *p;
3 D: _/ J1 }" ^" g cout << "无向图有" << vexNum << "个点，分别为:";$ w. l1 F( Y' A
for (int i = 0; i < vexNum; i++)
/ ?1 t6 j  l2 X) \+ U  u- q       cout << vexTable.data << " ";
* t6 n2 G4 V3 Q+ y/ R0 y cout << endl;% E4 H; _0 m' }8 t. |3 w
cout << "无向图有" << arcNum << "条边"<<endl;
+ _# \8 H9 P( f1 p/ C for (int i = 0; i < vexNum; i++)/ J; V' z% i) r
{
1 }  q: i2 {; ]  \: O$ {8 Q$ R$ E       cout<<"和" << vexTable.data << "有关的边:";
. x% ~# Y+ V$ Q  a       p = vexTable.firstarc;
, g5 q5 p: v+ h       while (p != NULL)7 q& ?/ k% F+ i! Y+ D: F
      {
9 p2 ^6 C/ S$ o$ B8 b          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
1 i! h1 p0 N. S# _5 r, r7 @! x          p=NextArc(i,p);
0 p6 ~1 v3 f! l& w0 N5 G% A( H       }4 T* w# n+ R! m  R7 Y. ?3 S* `
      cout << endl;
1 R( b9 I6 h( e8 v6 K* y! f }
- H0 d; _. M1 T$ \}
/ U  I! b( v9 K' x/ H- {$ ^, y0 p  J

' t4 C+ H( s- O$ j# X) {9 ]: N& Q" B邻接多重表与邻接表的对比8 c' d$ o9 _2 F. U4 ^. P8 \
3 \. a6 H3 e1 O5 n: n: r5 W& v
邻接表链接; {- O6 K$ ]5 _% k: M; P/ H) D
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。4 m5 ]8 G/ e) ?- r* @! O5 q9 o( @) a
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。& ?& f: U+ r/ ~4 B: O! J1 f
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。* r2 w9 I1 L/ b( c6 W- n; l8 E$ ?
————————————————9 s( j3 ?, n. P8 r: ]# f3 D
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。1 G# _: E& i  Q1 r0 P
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
, H2 d  W' C% h6 o4 x5 F# z6 t' L0 `9 _6 H0 m, Z4 F' ^$ ?+ b4 M1 U
2 K6 B! \" n+ W  u
9 c( L" O% p4 H, \3 d3 B" K- ?

) z. {3 R% W# Y) V) I3 A2 q$ a————————————————+ m; [9 {) C7 k9 \
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ F' s# ^3 T4 w+ @# k0 b原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958& j1 r3 U' h5 ~! J. d! X9 A

7 N; M; F8 k; P3 q& e) y- Z- Q