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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
& I* A, T0 l/ a9 {; t$ L' Bdata域存储有关顶点的信息；
# x- T7 C3 s- Q/ Qfirstarc域是链接指针，指向第一条依附于该顶点的边。$ X5 q% e% Y2 C. P K; 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;3 _, J5 R, r" b# H: p
for(int v=0; v<vexNum; v++)% H9 {* l' k7 l/ g6 f' ?
{" ?0 U- f& K: Q5 R- s/ q0 c5 ]: v5 X
      if(tag[v]==0)
0 z) D. i8 h' ], Q) x9 L          DFS1(v);
* _7 D+ B  `# T- a9 y1 B/ S6 q }4 e( Z; q6 s$ ?9 B3 D" a$ Z( M0 q
}# w+ _) b' J- D7 B  V" J
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()' O4 p9 c* i, z  u7 d
{! x! ~; w! u! x2 j- @  T
stack<int> s;
5 ?* N" S/ X; F6 \  g int tmp;" x: a0 O9 v; B. |3 T
MultiAdjListNetworkArc<WeightType> *p,*q;
' B: w6 p0 _. W+ c8 s. T for(int i=0; i<vexNum; i++)
" f% H4 X9 a* z3 q6 i       tag=0;. S1 Y" N. j" _, a% x
for(int i=0; i<vexNum; i++)# v* u* b% h- y% j0 j
{+ W# S, |- d% P4 [) \% ^/ `+ {
      tmp=i;
& |7 ~) V2 Y# ^' K! V0 S       while(tag[tmp]==0||!s.empty())- U$ S6 S* n4 U9 ?
      {3 U7 w; o/ ]- _
         p=vexTable[tmp].firstarc;
& j$ v8 }9 x6 f# K          while(tag[tmp]==0)
$ `5 [' }) R" _          {
) N1 Y# K+ _- r% r% }9 r- V/ x# h7 n             s.push(tmp);# N6 {' H# z! i
            cout<<setw(3)<<vexTable[tmp].data;
* r  r2 R( i% p             tag[tmp]=1;
6 r& V! T+ K0 m5 u0 ]' z             p=vexTable[tmp].firstarc;; g) K; {# i6 n1 _6 D
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for- @" r& y% z1 H3 J' r$ L
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
5 B% L/ N; E) m) _: \, V             //cout<<" 1st    tmp="<<tmp<<endl;
* T: V9 q: }3 G0 J          }
+ m) j4 g0 ?- ]          if(!s.empty())6 X+ f9 D. Y. _
         {
# k' X1 L: p+ i* ~             tmp=s.top();
+ s8 g" h- {% Q0 f             s.pop();
' s; K* C* H8 v' W             q=vexTable[tmp].firstarc;
! K/ q3 x$ S& t& [9 d  a+ d+ n9 ]             int t=tmp;+ b$ X' x& J2 V. H
            while(q&&tag[tmp]!=0)
3 U" @4 n/ S0 d( r" A             {
. y5 M" B3 s0 l* g" n                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);0 v: `% t0 Q: ~$ ~1 H! i
                  //cout<<" 2nd    tmp="<<tmp<<endl;
" q4 |: i- O8 m. s1 e                   q=NextArc(t,q);
+ ~9 _, i& g' G  Y             }
7 v# X! O: Q  P1 W. w/ ]2 U             if(tag[tmp]==0)$ n" y0 H8 t4 v. g7 k% O1 n
                  s.push(t);
# z  }1 \) F7 y( C             ///1、对应上面连通分支只有1个点的情况
* B* [$ S. A7 i% j" H" b6 @$ f             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
% h' z8 R) ?6 J) D8 [             ///tmp要么等于找到的第一个未访问节点，/ V0 a9 Y0 L# o& P* `/ g
            ///要么等于与t相连最后一个点（已被访问过）% f- B" W- u  D
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点) k3 l) U7 \8 f( {# e4 q- o
         }
; Y* l& [4 Y2 M' D1 r) `8 y6 T       }
% f8 Y2 H: \2 ^/ x1 u" }& |* f( g }1 _( N# a' o, p: r  j4 T$ |! a
}
7 S& m' A4 j1 B6 ^2 i//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
: {* \$ z/ U1 p. r' w* Jtemplate<class ElemType, class WeightType> int  F8 d: [  K2 T8 e# c2 k0 Q
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre): G9 h2 m6 k! x3 _$ z. l$ n' {( O8 W
{$ e$ w& ]( ~$ s5 E
if(head==pre)
5 v- P1 t1 B, S1 H       return -1;
2 G9 }$ f& r* J2 C. S: k5 C& k  U& i
MultiAdjListNetworkArc<WeightType> *p;
4 |) y3 ?# U+ o p=vexTable[head].firstarc;
; I; L0 }+ V* n2 f- N  K if(pre==-1&&p!=NULL)1 ^* `6 u7 u6 a5 g
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
' i+ V! Q& x1 p/ O( V //pre!=-1&&p!=NULL9 T, |2 y1 b) _1 r
while(p!=NULL)
! Q! z; x# v: d! s# v  C8 ] {5 |( Q; S/ u2 M
      if(p->adjVex1==head && p->adjVex2!=pre)# N/ K# w* R+ R% I, Y& b5 S
         p=p->nextarc1;
) }3 t2 c, O1 e5 ?+ x1 m2 v) a6 _       else if(p->adjVex2==head && p->adjVex1!=pre)
2 k4 U/ R, o" J" a          p=p->nextarc2;
1 {; J3 X! |; _4 d+ K       else if(p->adjVex1==head && p->adjVex2==pre)7 ^7 h( E% H2 m+ G" ?/ r
      {
; e  m7 Z+ M% D! o0 p* w! V% u          p=p->nextarc1;4 d3 H  V- g& b$ \) G6 M* |
         break;
. @* {. T( w/ I. L. O* P% `       }9 o, K) }( P4 \3 b2 @- Y
      else if(p->adjVex2==head && p->adjVex1==pre)
  a8 B+ l* }3 b$ i+ X) K# L       {
- Q6 S7 u4 {" z          p=p->nextarc2;. ~6 }# J/ K3 O1 Y, G* f& V5 {1 v
         break;3 [. b6 f) q9 L
      }1 @2 y% ~& `3 C& e
}
/ |/ }, B# z" G3 {! f4 W if(p!=NULL)
# B' r. }' l- B) _ {
% e& m' Q, I6 f       return p->adjVex1==head?p->adjVex2:p->adjVex1;) Q  y3 p$ h6 m1 |6 p) b) t( ^
}# [9 P0 s! `( H; S+ a  n
else" D4 _% t) A; |9 O" A
      return -1;$ l: E: _' n( D. U  b( {
}
1 q* d& G8 w  K8 i! w8 y, a7 z
  ^3 T( x+ T$ q# C
- {. b' t) V! @$ F/ ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(). B8 _, `4 |3 s  \6 ^* i' |
{
1 C( R. S. Q3 z. E0 | stack<int> s;$ v- n# j9 l  u8 W. v4 \8 K0 }9 a
int p,cur,pre;$ z0 Y, A/ \5 X) K0 D9 ?; ~2 N
//MultiAdjListNetworkArc<WeightType> *p,*q;( ~5 N* K' h# j2 X8 f. y
for(int i=0; i<vexNum; i++) tag=0;//初始化
. f1 a0 Z/ j" W" [0 [' N' z6 U9 h( T- L* w. o
for(int i=0; i<vexNum; i++)
6 u7 ^' q4 j; j9 O* [& u {
  C3 b# s+ C0 B       cur=i;pre=-1;
) L/ X8 F% a8 ]! d       while(tag[cur]==0||!s.empty())6 T/ @: q+ o$ Z5 @  o
      {
  I0 a7 k4 ]) U6 B          while(tag[cur]==0)
3 B0 K1 M, d" S5 Z          {; w& t3 G" O3 ^& p4 }5 e
            cout<<vexTable[cur].data<<"  ";
: q2 L+ J7 h/ [% n8 x             s.push(cur);
4 r5 y/ B, @( ]! _             tag[cur]=1;# ^1 C+ w& {! J7 J7 u/ r2 o
            //初次访问，标记入栈  ^6 X) Q4 A/ V

! F3 g2 I! N0 f0 n             p=GetAdjVex(cur,pre);//p是cur的连通顶点, t7 [+ J* }% X& f( W* z
            if(p==-1)
, ?$ s, v  {; w' [7 \             {
3 K+ |. F9 a* d! A                pre=cur;s.pop();2 S' M7 p- ?( j% U) o% w5 J
               break;
( V# s* d8 Z6 h# b4 Y( d             }; y# D# j( _' j2 p* M% Z# w
            else1 Q' X7 g5 L; a; K1 |' P
            {
$ X0 y1 a) @: U                pre=cur;
6 C8 S" ?7 P! H# Y4 G                cur=p;
3 u! n* N1 _5 g- }             }
% V! s# B7 n- t* Z- u8 a5 q6 u
9 u9 K( p: }6 N6 M" m          }
! X# O; E# T3 [" T          while(!s.empty())' W( q* _* e& @0 L6 C
         {
. |, c+ B8 i& u& A             cur=s.top();
# ?- i& E: x3 \* h  c5 n4 C7 Z             p=GetAdjVex(cur,pre);
3 F6 `5 _& ?8 w' a2 q             if(tag[p]==0)
+ ^. J& K* v7 _$ k             {1 j# d4 U& \7 o& u( C! L+ A) y
                  pre=cur;, r! y' j+ r* V; ]  l4 O8 ]! J' f
                  cur=p;7 s% P# ^, y5 U: Q
                  break;6 s. a  E# u% P! _5 c+ _6 y
            }
4 j" E+ ?, Y0 _/ O             else5 E6 Y  b9 m7 M# z
            {
9 \. H  {+ ~7 ?6 e' g$ l" i8 ?                   pre=s.top();
. m8 S. z* s2 a: _( j, a                   s.pop();
& A! H( L/ @: H: X2 B4 U6 g             }+ K4 O( l0 x  }4 i8 X) ~& I

. F# c3 o: Z- Y( Q8 k& \* Y5 W" N          }
$ `$ Y) E, U+ a$ ]$ F; i/ s8 Q* V3 L
      }! r" ?7 w2 W7 |4 x
}
+ q  Q. P' O3 `& K  U3 v& |  k}7 s% n0 h4 f4 Y
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()* O* o4 q9 Z4 \! ]7 @1 M
{. N% f; I$ z2 h) w+ ]5 e
for(int i=0; i<vexNum; i++)
0 x6 [; P# y1 G5 y# j% h% _+ [: Z       tag=0;
4 x: s$ j+ v$ }7 L! r" ]3 w queue<int> q;
0 C$ K* V; @. Y- ~) h int tmp,t;
1 R# W  a+ N) x: f9 I MultiAdjListNetworkArc<WeightType> *p;' x% f, x! h6 ]
for(int i=0; i<vexNum; i++)
1 z' Q; N3 ~6 d, S5 G+ j+ h) J" c, q {! Z9 t. q8 T0 S4 G  u- w" i
      if(tag==0)
( F& w  \- M, Z, i4 R! Z4 F: L       {
" D$ J, W% G' M6 K9 J5 c  l          tag=1;
+ `4 k, ^1 O0 z8 g% \7 h. z# \3 d          q.push(i);$ M* L* r. B/ q$ |( z% a% {$ t& R
         cout<<setw(3)<<vexTable.data;5 l& z6 _0 i- Y  k& J4 U5 Y
      }
6 E6 i4 L- t3 [6 ?) e* _       while(!q.empty())
+ ]: \! E: d, I       {4 @, D; [& B& j! I' s9 K- s
         tmp=q.front();
' W+ Y1 I, [8 Z3 g2 n) J          q.pop();
8 R' p/ }9 F! |          p=vexTable[tmp].firstarc;
- i2 a9 }2 v3 J* h( Y          while(p!=NULL)
& b, i7 O- y* n          {
4 W9 K: I6 T, V. x+ t2 L: B- ^             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
' \( Z' m5 S0 [/ J. B, r             if(tag[t]==0)
6 H( ], H/ K8 Q' X+ d             {
$ t- q; \3 b8 Y# ^4 ^) J: N                   cout<<setw(3)<<vexTable[t].data;( q9 W; w3 U& M/ g6 [' {( ^
                  tag[t]=1;# A1 g( G/ t5 a
                  q.push(t);
3 f5 m# r  k% U: i" O2 ~! c# n+ n0 C             }: }% ?+ c8 O: {) w0 K  t& W0 @
            p=NextArc(tmp,p);' _( ?/ g) x' [" L! A5 U7 }
         }' q: w/ c$ b" V9 z7 k/ P
      }4 y7 x& E* V" u: H9 a
}% ~& n) ^$ M  _2 Q: u# l2 l
}
4 k. o7 U- N  j$ b( ]. Vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()( i. a  U; U6 h, D% b" ^$ Z7 a
{( Y  a' Q5 e$ T& O0 C. f6 s
MultiAdjListNetworkArc<WeightType> *p;
# S, n8 i# n3 P7 w/ U! k/ J' G4 l cout << "无向图有" << vexNum << "个点，分别为:";
7 B" S7 z; h3 A+ [/ [" l8 r7 }$ V" e/ Z for (int i = 0; i < vexNum; i++)4 I2 E7 Z! O% o4 C. D9 K
      cout << vexTable.data << " ";
/ F1 `! e( n/ Z& @; l4 g+ O cout << endl;! _5 R4 O$ o% Q/ E
cout << "无向图有" << arcNum << "条边"<<endl;$ \0 a1 @2 F0 U& D) E/ j- a# |+ P
for (int i = 0; i < vexNum; i++): z* q) c  z* j. W
{' H2 H3 l; q! P* j& e
      cout<<"和" << vexTable.data << "有关的边:";, B8 a1 Q* O& o# W1 e( R
      p = vexTable.firstarc;1 M) p$ E7 h1 @6 e( S# B; z8 A
      while (p != NULL)
: G  E) M) N9 ?* d' {  ~, P) \       {
6 q& |# X% _' z7 E5 |! c          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";2 B$ o  d; p3 [9 Q7 i, ?
         p=NextArc(i,p);
/ N0 d+ o& G( A3 l& E       }
) E$ Y) E0 a9 H$ |1 A0 n       cout << endl;
7 h  t+ Y, @# x0 s% v }
% O( J! Q8 Q. B/ [( u8 \7 o}
+ b& }" }/ N" g* R
; x. C7 p+ V; J! I) a
$ A$ l2 d- |4 N邻接多重表与邻接表的对比0 k, {! x* J$ s' ?
! X4 I5 Y8 i2 U- K% i2 M) r
邻接表链接+ `5 ^* ?* ^. v0 T
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。: p* C* C3 X) x% V& S# a
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。0 v3 c$ m4 @2 S: N
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
0 r# G( G9 J6 ]9 d( V$ A5 j  A————————————————
$ p) D5 u$ N: I& Z  {5 H版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。( [/ x- H2 e. t
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958: K  S/ \& c, K' o
! u1 g9 H1 ~! O1 i" n) @
# _- @" k9 J0 j

, {/ Q6 Y# k3 N& U. w1 E& r( d2 a/ O7 J8 }
————————————————
& r, r) }1 }# g* P$ u# S版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; Z/ N0 R( D1 M8 Z4 ~$ \' K
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
1 [, ?& `4 x4 d
) x$ c" H$ F! r3 o' E; |% j
8 U" x% b! C3 }6 O3 q