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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：+ T, P% |8 r$ I- ?. h
data域存储有关顶点的信息；$ Y3 B" Y# d2 \% l* `5 y0 P! Z
firstarc域是链接指针，指向第一条依附于该顶点的边。
所有的顶点结点组成一个顺序表。

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;
9 ^* _2 ]. ?+ ]9 o* D9 @ for(int v=0; v<vexNum; v++)
6 j2 z. G3 b  [- n5 z {5 q2 p1 p- p# ^* g  [" d0 e( f; M
      if(tag[v]==0)  l0 z' f. D& t
         DFS1(v);
4 J: w3 ?/ @# B7 ]$ q2 y& u }
, \# v3 D2 f" T2 ~5 W/ F9 ^}
  P/ H, e  N" b5 z4 }( Dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
0 I) {' S2 H: ?% n3 c{$ A; m, j8 Y" k; P( s
stack<int> s;
3 V3 v2 g. y. M% y# V% e int tmp;# W# s2 Z% i2 W% P9 i  U
MultiAdjListNetworkArc<WeightType> *p,*q;
7 ?* R- E7 `& X3 }2 j) }9 b for(int i=0; i<vexNum; i++)% T8 E2 N5 ^. \$ h
      tag=0;, l; o1 G  W. {. W; }7 Y5 a1 E
for(int i=0; i<vexNum; i++)6 A! f2 v/ S/ V
{
5 a4 Z9 c: g  b% G' f! P! f% x       tmp=i;
% c: H/ s/ k4 e" A) P       while(tag[tmp]==0||!s.empty())0 Z" X2 d( m- Z. n
      {
; R: E- O5 V4 j" e' s" h          p=vexTable[tmp].firstarc;( R/ d: L3 @! V; i* U! j. B
         while(tag[tmp]==0)
7 S' t- i) I& F          {; L5 S9 {- L, N9 P
            s.push(tmp);
* n/ ]' Q! U8 n/ @             cout<<setw(3)<<vexTable[tmp].data;
5 ?3 I0 Q+ u+ Y/ g0 }" E             tag[tmp]=1;9 {  _4 h( ^% G9 p7 D% T
            p=vexTable[tmp].firstarc;$ H: q% c0 y7 K5 ]6 w
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for7 i5 |2 L. t) Q
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
6 b! l" V& ?: n/ E7 D             //cout<<" 1st    tmp="<<tmp<<endl;, B$ a% ?; [0 X8 K, m4 s( `
         }
8 \( [! ?$ R! y; L6 H# f/ m          if(!s.empty()), p. V: d& Y9 N
         {
0 g9 Q! [" u% D% L             tmp=s.top();% F: E2 n0 L9 O8 H
            s.pop();
5 R7 f; {# L4 i+ {& T( s9 T             q=vexTable[tmp].firstarc;
' Q+ x; @( Q5 i2 p( W1 ], i% f             int t=tmp;$ u' O( G1 E6 G- x% x4 X6 b  V* j
            while(q&&tag[tmp]!=0)( [- x" B' `6 I* [$ r5 f) @5 O
            {. O4 n3 R- j% c2 e4 ^, P
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
+ _6 y" i1 U( i- p1 a/ f5 I+ l5 e                   //cout<<" 2nd    tmp="<<tmp<<endl;. k& }0 D8 Y+ a  w0 X  E/ B
                  q=NextArc(t,q);0 \; p/ R" e7 R) |. q
            }5 }/ g$ `7 d, R; M( \
            if(tag[tmp]==0)
/ C" E3 H$ [' r$ Q4 \                   s.push(t);9 c/ \0 b( Y* B, E0 P
            ///1、对应上面连通分支只有1个点的情况
1 Y: y% D$ o% u2 x             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈8 I0 r$ h) X9 L; N3 r' u
            ///tmp要么等于找到的第一个未访问节点，1 F% E, h' ?* I: `" R: F- N
            ///要么等于与t相连最后一个点（已被访问过）' ^) V' w5 G2 V
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点. G+ m, j7 o3 x0 _8 S$ ^
         }& ~+ |6 f; ~, X% z' ~
      }: ~. Z9 W9 L/ k7 D8 u7 T- J
}1 g# P- G# _( J, r' i
}
+ _" ?/ ~' x8 u, {//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
8 x, g5 K4 R+ P2 E" `template<class ElemType, class WeightType> int/ ^  q5 F3 l- J3 g0 U
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
- r$ r, B5 P1 s( I{
% r: y: E& m& E1 _  I if(head==pre)% Q! O2 s9 b5 W# u  V
      return -1;) K1 C" m3 ^/ E/ @; R# S; K

' |3 }; F% ?2 @ MultiAdjListNetworkArc<WeightType> *p;6 n* E. q- r- ^" ]6 ?$ s3 i
p=vexTable[head].firstarc;
5 E8 }6 O' X7 r) J if(pre==-1&&p!=NULL)
9 t3 g; W. @9 r4 y       return p->adjVex1==head?p->adjVex2:p->adjVex1;
7 ^4 ^, c  w" n //pre!=-1&&p!=NULL
& Y& g* D' K; K4 G# I+ {. H! F while(p!=NULL)# V  |" A' h* R
{
% ?8 f+ |" z- Z! b6 k8 x: J; @       if(p->adjVex1==head && p->adjVex2!=pre)8 }. P' ?! e4 O" h
         p=p->nextarc1;2 T8 H! i9 Q4 g' n' G
      else if(p->adjVex2==head && p->adjVex1!=pre)
3 I0 y" W0 V4 s5 R9 C7 ~          p=p->nextarc2;
6 W( n3 e( U. P       else if(p->adjVex1==head && p->adjVex2==pre)1 C& `* @8 @4 X( G
      {
+ z/ Q; S3 F# W7 l. |          p=p->nextarc1;3 ]+ a& u, }! V  r) v/ g- a
         break;
( `9 D1 v6 n; S. m       }
! [) s" _' F' D( r+ s3 a* h$ j       else if(p->adjVex2==head && p->adjVex1==pre)8 D# N! E! u5 F! l- e8 B4 G7 y. N
      {' e6 m. P, `- h5 ~9 |: A: f' l
         p=p->nextarc2;/ |/ r8 _6 s: ^
         break;
3 v+ a3 X9 o6 ^       }* I( l( l* F; K( Q/ y6 k2 p
}
2 v) g2 O; U+ ]( e if(p!=NULL)
; u0 B* I* x9 Y5 i/ J0 d: A {
" P, p& l$ n% f) O% {9 F/ w8 G       return p->adjVex1==head?p->adjVex2:p->adjVex1;% y7 [5 j! p" ^! i4 Z5 U
}1 @6 b: l- x, e
else
0 G1 l5 K9 l5 ~, x3 z       return -1;& `# h7 ~! N. d0 ]% o& h
}
4 n7 F% @2 u; X" a% f
% }1 W; ~# `- F; l# s$ I
8 w' K$ n7 D& `+ P! t, }& utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
5 w  b; H' l* [2 ]' [% q{
/ p* M* F( j8 n' _9 J# q stack<int> s;
9 K; P, F6 T/ d9 m; k( @: | int p,cur,pre;
5 O+ L0 l9 K1 f; O/ M; A //MultiAdjListNetworkArc<WeightType> *p,*q;
1 K% |; c* L. S1 L6 b for(int i=0; i<vexNum; i++) tag=0;//初始化
9 q+ ^. W. K) V; O4 X1 J( C' m# F9 r( x0 ^. A! y
for(int i=0; i<vexNum; i++)5 m8 c6 ~9 W3 _( s( P: x( M
{
& q8 u) F+ G( V! L  g       cur=i;pre=-1;6 c  k9 g/ ~! H0 R6 U, o
      while(tag[cur]==0||!s.empty())+ H7 ?: ~: m$ v! i- j6 @" t2 H" g: [
      {
6 Q! p; m5 g8 E' G: `$ V. \2 ?          while(tag[cur]==0)$ N' Y! X  J  ]7 L
         {
" X1 S  F" H: [, l! M* g3 E             cout<<vexTable[cur].data<<"  ";
" q9 A5 ?* R: Z8 y             s.push(cur);
4 _" j) s2 P/ g& v. C4 X( |7 F             tag[cur]=1;
, t3 e" g7 z, @8 ^1 f# [             //初次访问，标记入栈
: f3 j! @  _* [9 u# T$ T9 I+ U' t( D- n" H' @( K+ |
            p=GetAdjVex(cur,pre);//p是cur的连通顶点4 Q$ u2 P) Q" X9 c: U5 v5 {7 \
            if(p==-1)  @: @: e1 K- @/ B) C7 J2 B
            {
" `& W* l* X# l  I% ^( ?                pre=cur;s.pop();( \- F6 Y) U2 |1 Q( P
               break;5 n3 `$ O( A8 H5 L
            }
% ~* b9 U8 t! Q             else
% O0 n5 Y5 _4 A( x! I0 F$ z             {7 g4 p% j5 j; I5 U3 L6 y- p& \
               pre=cur;
! x6 U# \; s" c! q) x7 j+ s                cur=p;/ @* I5 d5 W5 m8 `' |2 F4 j
            }) J, _; d- f9 j/ y# d
+ n9 j: t2 Y: s4 t7 \
         }" i4 ~+ O; t! V5 G- y: t
         while(!s.empty())! G- m! m4 f& V: t7 L( }3 Y
         {  V8 s/ D! u5 M# S& ^
            cur=s.top();/ L+ ^+ I9 |" w7 j, }
            p=GetAdjVex(cur,pre);. E2 N, W8 m) g. e; D9 Y
            if(tag[p]==0)9 s2 e- n: @/ `) l% U+ G
            {9 k  o% ^  j) p+ Q0 L
                  pre=cur;) f! M3 e3 {' |+ c  K
                  cur=p;
                  break;) @% [# m& w0 j* |  m! O
            }* ]; \" M! O. g& B$ l
            else
: _# X, V8 P7 Y             {
" f7 K! J' M+ t3 i                   pre=s.top();
* h' J. B9 l% q8 D5 J                   s.pop();
4 f: u2 w3 ?6 b, |1 ]             }
2 l6 W2 v' a% i, L. v9 e8 B
1 q# D5 [7 N$ X0 _          }
" l  D4 v% ~+ n2 {: H# S& Z% N. v# D5 l
      }% Z5 N! Q; L$ g* @7 W0 [2 j* M
}
9 V1 R0 n6 u' M( W: s1 A. W8 k}
" U1 X$ ]. `" ]  @0 H- I. Jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()" E+ x2 b& G: s; E1 T2 }) c
{" O+ D# }# J3 K* Q( i( S1 m
for(int i=0; i<vexNum; i++)* v( H# A* R( h. Z
      tag=0;# K2 G" M9 m: W  e" M+ S# o* M
queue<int> q;
' W7 G( ~" B8 `% a' K int tmp,t;
' f, p' t& e- } MultiAdjListNetworkArc<WeightType> *p;
6 Y% x2 |' h1 V1 i( m7 ? for(int i=0; i<vexNum; i++)2 ~# z/ b# w) G* R$ O
{, E. O) T3 J" J5 f* g* ]6 N
      if(tag==0)
! M" F4 Y  g2 g9 C       {: w4 x6 p" k0 f' n, {4 b1 x+ |
         tag=1;
3 v  ]; J/ ~6 \7 y! u( n          q.push(i);
& l" e: F* U) S2 R# |          cout<<setw(3)<<vexTable.data;
: D. J( y. u# V" |: W; i/ y       }
7 n$ M0 }6 g) n       while(!q.empty())$ C0 z1 v# o9 ~6 |- s7 J1 Y
      {/ l4 }3 r; C/ T* r" [2 }
         tmp=q.front();2 n9 H( L1 ?# S8 p8 J
         q.pop();
. ^5 j' E/ `5 q7 [; f3 c          p=vexTable[tmp].firstarc;
4 E. t" t0 v1 n+ f4 w$ `8 F          while(p!=NULL)+ M0 q3 x/ q8 ~
         {4 I% S' _# y; I: I! B: X
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);0 @$ q4 a& ?+ m. z: P& y8 M
            if(tag[t]==0)4 N3 p  c7 I) u' w* f4 u
            {  m1 [+ }9 w2 K1 B5 v
                  cout<<setw(3)<<vexTable[t].data;
/ J) H5 r1 B1 y' H  @. \                   tag[t]=1;& N  q7 s" C' @* L( U% A- R
                  q.push(t);! o5 P* I0 o: i. a& O
            }
2 G$ j- H  _; x9 u             p=NextArc(tmp,p);
( d: h. m+ {. X; a          }6 T, A4 ^8 o0 c% l% Y# L# S
      }
4 N, ]+ L  m$ }+ m1 U }1 i( a* ^/ ]# M& j! z% {6 f
}3 c5 @( B' Z  b3 |: C
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
. b; R5 v0 g3 a% K{: c' ^3 \6 Y; W
MultiAdjListNetworkArc<WeightType> *p;  Z% O2 g7 C6 _6 j
cout << "无向图有" << vexNum << "个点，分别为:";
% _5 W- R+ s+ ~7 f7 K for (int i = 0; i < vexNum; i++)
7 R: t' ]* m7 @( V       cout << vexTable.data << " ";
9 p' ]8 p: {' n cout << endl;" ]/ K/ y6 J, s1 r
cout << "无向图有" << arcNum << "条边"<<endl;
. f4 t3 v# Q1 u3 T9 m# v. w for (int i = 0; i < vexNum; i++)$ y; o3 D  J7 d( e( u( C
{
/ f$ v3 p( ]& M! D, C       cout<<"和" << vexTable.data << "有关的边:";
5 [/ k) U4 K( A$ ]- n) U       p = vexTable.firstarc;) G0 l0 g) O" Z3 h) u1 m( S5 Z& z
      while (p != NULL)
9 _* V* h/ i7 I2 P; ?  k0 X       {
" W) I9 D- D. ?3 z2 {1 E          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
! E  n7 a, ~6 c          p=NextArc(i,p);
5 V% d2 p( g1 t. O# w       }7 s8 F$ t% a6 J" R
      cout << endl;  [( T, W+ `, h+ v! Z* x
}! t0 d* f) l* r6 B- c
}4 ]8 d1 g1 o. V# S$ I7 n. Y

  W$ {3 e" D' @4 k% }; p% I5 L
1 X, F- d! ]1 o" {$ F4 `3 [邻接多重表与邻接表的对比' z) x  D+ ]. y
" \5 s: K4 L2 r# V3 X. m
邻接表链接6 K! J' x3 }( r8 P
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
7 Q* ?9 A8 s7 ~在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。/ r7 q9 o  |, \) G4 z  |
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。+ }' E/ j5 E" b/ H" x- G5 f
————————————————
. Q! Z- a; S4 n# ^: d. ~8 b- Z# X4 ?版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% Q* i2 C7 w) _. ]" o; P  [+ A: c原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
# ?- n2 n/ x  n: e
9 l9 y6 W8 ~$ W' X4 T) V  E, c, |) _+ B& S0 ]2 l
# ]2 s( m, x" N& y

9 ?( {/ b1 B0 r' E4 U————————————————% b* a% o# t  V7 w/ Y; t
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。8 j9 }: O* [  B( X/ \0 Q: W
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958/ c6 ~. y* m* u4 A# n
$ N% P( H6 q% `0 @# Y+ Q
& K; Z$ X5 M9 _+ l