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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：! J) Z- R' V5 a, y8 ]* A/ l
data域存储有关顶点的信息；$ a2 `- d7 L4 k8 k/ [
firstarc域是链接指针，指向第一条依附于该顶点的边。
9 w% q5 j: t/ b7 ?- T' Q+ ]所有的顶点结点组成一个顺序表。

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;' \, P; C3 q, K7 z& C; q- i/ x. o5 D
for(int v=0; v<vexNum; v++)( r0 G* _! i8 r& l' y( p$ Q
{
* h% f8 X1 ?7 \" {7 A       if(tag[v]==0)
- ^6 ~  x+ }3 I- H( m          DFS1(v);( w; T2 w5 ]: ^  f- U3 Y
}' M& R7 Y1 ^4 U* n% B/ i+ K8 ]9 f' N
}: F6 l9 m( x' S4 g! Y% p- k
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
, e/ C) Z, T! t! M, p+ T0 B{/ }# o" g) c5 N: {6 ?' K
stack<int> s;
8 e8 i7 F- x9 d2 x$ c int tmp;
3 T: \9 l: r0 o: |/ r: E MultiAdjListNetworkArc<WeightType> *p,*q;
' T8 a  B: v- V: P for(int i=0; i<vexNum; i++)
5 P* z* _  y3 ]- l" k9 r7 T$ Z1 }       tag=0;! i+ Y: e' k4 u: C" I
for(int i=0; i<vexNum; i++)
+ Y# Y0 [3 C1 k( Z4 ?$ V4 b, V {
6 W( l% K. a$ `       tmp=i;7 ]2 n; j3 G. e: y  F
      while(tag[tmp]==0||!s.empty())
5 O! n# ^* E+ Y       {! E5 l  |7 H, }* o- p
         p=vexTable[tmp].firstarc;
9 K& ?" S7 }' s1 a& Z0 u          while(tag[tmp]==0)
" U3 P% r! P) @. M          {: g5 Q: N; V) I2 s/ L6 n( h
            s.push(tmp);
* W% D4 @' H. X             cout<<setw(3)<<vexTable[tmp].data;' F/ ~8 P& M3 y2 r
            tag[tmp]=1;$ Q. q2 u! G6 d. e( w% M
            p=vexTable[tmp].firstarc;
9 j" k7 L4 U* {4 A7 S9 p8 s3 \! R             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for0 E/ T3 i' B" h% q& S; `% t
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
/ t* C7 \/ y* r* X; U) o             //cout<<" 1st    tmp="<<tmp<<endl;& e3 v7 P" H* R# w1 o! q
         }
6 p* }3 D9 |( M9 C9 B! o/ D          if(!s.empty())
1 o! g8 Y+ o  n& I          {
! E5 |/ u9 _2 j             tmp=s.top();/ [# i2 T, R$ v6 J+ l/ N1 d
            s.pop();
! S8 ~* v% @1 K0 {             q=vexTable[tmp].firstarc;- P# D- E  p- r7 [7 w1 |
            int t=tmp;
1 I3 s$ v5 ]4 J7 {( |$ T             while(q&&tag[tmp]!=0)
/ L9 X% \" o  [- X             {
/ e/ ]6 V0 K+ e: }. ^                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
/ ?5 n" E( D; _0 N) u& m" ?3 a/ s                   //cout<<" 2nd    tmp="<<tmp<<endl;
9 R- _. k& G! n( Q+ m* ]8 d                   q=NextArc(t,q);1 _7 P' D0 q7 T( F, Y! T! K& |
            }% d% h5 z1 T1 `/ y# A& k
            if(tag[tmp]==0), \0 A. h5 E6 S, C$ f7 o# ^
                  s.push(t);
* |6 w6 t/ i" Z, G& ~: P8 m             ///1、对应上面连通分支只有1个点的情况: W4 o- F. p. ^- `+ R0 f
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈/ K  c3 g5 p2 _
            ///tmp要么等于找到的第一个未访问节点，4 S. r2 i4 a4 z9 O8 l" k' Z( S' K
            ///要么等于与t相连最后一个点（已被访问过）
8 R6 f6 E$ Z2 f' c, f             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点& \% D, E$ B7 p8 H9 T/ P7 Y! y0 Z
         }. c2 Z' r$ L$ o. G( Y
      }
1 X9 X" ]+ ~! P7 j. F6 A: v }
) p, _/ F6 R* |* F; U}/ E3 d6 N% v+ ?  c. i: ]" C. B6 ?, C
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1; x  f0 }. Z. c7 o. d
template<class ElemType, class WeightType> int
' ?$ A5 P+ T4 j: R( S5 M  lMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
1 U3 L4 b- C! O- ?; i+ u{" u# U8 e3 D; j8 q7 x
if(head==pre)
  P" ]; @4 `$ [4 R       return -1;( O9 f" v* t: A* c0 J
& Y# v; i  O( ]5 d
MultiAdjListNetworkArc<WeightType> *p;- v6 x  Z  w8 V) m
p=vexTable[head].firstarc;' J) {/ s1 s7 w9 D5 ?) C; R0 I- g
if(pre==-1&&p!=NULL)  C3 E% B/ T# y  W9 A. {6 \
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
  u. Y9 l' b7 @ //pre!=-1&&p!=NULL
2 D# V& H6 ~+ h while(p!=NULL)' c4 O% ?% @! j% I" t- x
{
) H  j% b; C6 l       if(p->adjVex1==head && p->adjVex2!=pre)
, P7 E8 {, H2 `* u  A          p=p->nextarc1;: Y0 {% E" T- m5 j; d
      else if(p->adjVex2==head && p->adjVex1!=pre)
9 H7 ^$ a, q1 \          p=p->nextarc2;
; }6 ~% z6 @% o       else if(p->adjVex1==head && p->adjVex2==pre)
# |2 k" _! u  @+ G2 L& v. J       {+ }; ^  E# m: E! E
         p=p->nextarc1;
2 g: P% S: N4 z" k          break;+ l7 b4 k+ w# B% H) `6 n
      }
/ ?7 L+ g% C3 Z+ m* [: Y  l7 H       else if(p->adjVex2==head && p->adjVex1==pre)
1 T# v( Q$ Z: l       {
! n- B4 l# {9 r: s9 X# ~  W3 P# A          p=p->nextarc2;
3 n( `, s0 g1 N( h4 @$ ~- e          break;/ `/ }6 O# z  y0 H* m
      }; C; d4 j& b# [" I% |
}
& h# _# o, L" o" d: z if(p!=NULL)
5 |5 ]1 l: w$ } {
+ @- v  o8 k5 A( L  v2 Z" n       return p->adjVex1==head?p->adjVex2:p->adjVex1;
( r0 N* T% p. V6 \! h }) I  U8 N  U# l* c: E, _
else
5 U% d  p6 {- j+ }% J' v$ E: p/ c6 G       return -1;5 `3 E; s% F% b" O) Z
}
0 u( D6 M; K6 o  V+ i- j6 a; e, R* n  y) U3 b' R

+ j$ N& E' M7 B- [template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(). z5 h$ p2 y: k) a
{
( O7 T" @* z( y3 M) A6 N* k5 M+ \) e4 K stack<int> s;; l8 ^5 {) ~, |  f
int p,cur,pre;
+ ^/ C2 V/ J# O* O0 p //MultiAdjListNetworkArc<WeightType> *p,*q;
1 @. d7 H7 e/ A8 I: R for(int i=0; i<vexNum; i++) tag=0;//初始化) h7 a  X. n/ q/ }. E

3 k/ E4 d7 w' z/ f for(int i=0; i<vexNum; i++)) ?$ U, s% _! n" I4 X- Z
{
; j$ Z1 _  Y: d  u; E" O2 l       cur=i;pre=-1;
! K0 o, E" a8 S' g       while(tag[cur]==0||!s.empty())
, p# o: C2 T0 G3 D% U       {
8 o; n$ N. E* v# m" K2 o          while(tag[cur]==0)$ _, w  z/ t* p7 l
         {! ]% G. a, u- N
            cout<<vexTable[cur].data<<"  ";& H) a. t! D- p2 F: i* M
            s.push(cur);
            tag[cur]=1;
; j" R' H( r# Y) @, ?             //初次访问，标记入栈: P7 H* O( d1 d* u& x0 B
+ N) O6 d! Y. a' ^) r
            p=GetAdjVex(cur,pre);//p是cur的连通顶点  t/ I) a( {. ^5 g
            if(p==-1)9 C/ B; k/ g* P  S2 o# d
            {0 Q0 h" `8 K, c& \
               pre=cur;s.pop();
$ U$ c: q, q& e, `( X                break;- ?5 P: |" H9 J/ Z
            }
7 x' u2 X! |8 [% L" v. _             else
& i( W" I+ H6 K             {9 U; `& K2 _4 X4 S
               pre=cur;
7 h% p& {6 U0 A6 _                cur=p;) h7 a1 H1 v; R5 a# f  `# A
            }
' h" ]- A2 u. D$ N; u# w
; W1 X- H; s  \+ ^          }) ~/ K3 {* F, ~6 p9 @$ l
         while(!s.empty())
- }3 G* j0 k  {$ K          {4 G* E0 Q+ ~* |; L& C5 \
            cur=s.top();3 b3 q3 ?# w& \: T3 g( X6 V
            p=GetAdjVex(cur,pre);8 x* N" p6 P' n/ m4 q
            if(tag[p]==0)
$ I' ]9 m5 c/ }! ]             {0 R4 W5 X6 y) z/ M( s
                  pre=cur;# |. {2 m6 \% A8 }
                  cur=p;& g6 b* u( N& g" w
                  break;
: V# H' V, i. C/ [& T" E4 C             }
0 g2 j' ]5 Y  \* x9 [$ l2 I' ^             else
2 b. o1 D2 [+ o$ x! n             {. d% D5 G2 R- b  P# p7 Y2 a, ^- n
                  pre=s.top();
( l9 n+ m1 s! j# P$ k' C                   s.pop();$ J9 S. ]! o6 \
            }
5 T. s/ ^7 Y9 X4 s/ ?9 U3 ?1 H/ T
7 }3 D& y) ^7 M3 Q6 j3 f6 S* F+ I" w          }5 ?3 C' i/ }6 ~

+ x* [7 O# ]0 X' T       }
! l4 Q: h% T& | }
8 ~- F8 G2 z( S" o" X. g}" ]' y1 h6 @5 \6 A' [* V3 |
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()$ q4 i. N6 @) E6 P+ g5 ^1 x
{! P1 |3 R! B' r: D; p
for(int i=0; i<vexNum; i++)
. e2 a3 K" l' C# @; \' Q& S       tag=0;
4 @8 U4 z4 }: ~9 i queue<int> q;
" |  L" [+ d, c) n) e; _4 y int tmp,t;6 b2 l+ G# T- l/ Z/ I* s) k
MultiAdjListNetworkArc<WeightType> *p;
! Q$ ^/ L7 u6 W) G8 `1 \7 Y, L for(int i=0; i<vexNum; i++)' V+ I. ]! w; N2 a% M; n& g
{
  [2 }9 ]( W6 _1 \$ L' ?       if(tag==0)8 ~6 D6 ~' U  Z# ?
      {
+ L$ O% ]: O1 q4 o          tag=1;& w! y/ x* ?" B$ v; g+ Y6 O
         q.push(i);
7 k: V9 q+ W/ n. k          cout<<setw(3)<<vexTable.data;! \4 H4 d' j3 a2 S
      }+ t7 M$ a3 _! |" H( k- T
      while(!q.empty()): A7 L# E1 j  p0 F  |6 C
      {
) v/ ~1 g  s; |. N/ t. X          tmp=q.front();
0 h  Z( }6 T3 K# P          q.pop();/ H2 e& B8 g' Z5 m
         p=vexTable[tmp].firstarc;
7 {3 Z  v  i1 ]          while(p!=NULL)
! s! G5 _) L2 z+ T& `. ?3 Y3 N          {: V8 N5 F9 ]0 x5 l# W, U+ J
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
6 f* E3 h. V" g( f             if(tag[t]==0)
+ _  Y9 S, `6 @3 ^+ B             {( p; C; f0 i$ d
                  cout<<setw(3)<<vexTable[t].data;4 q6 l' i; p$ K, P) _: D4 v2 I
                  tag[t]=1;
% g% W6 J: r2 h6 A( K: J) Y; ~$ v                   q.push(t);
            }6 {5 ?; W" s& A$ {7 M
            p=NextArc(tmp,p);
) k' L! r) N, r; Y5 |          }
" \. B# i0 F) \- K       }
' ?1 c+ k; u" R" `# Q }2 U# X/ c8 t: S4 c
}3 y9 D: A+ S. q8 T0 a* ~
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
$ L9 I+ ~8 c/ L/ ?5 }8 J{& p, [5 y6 g" W) @" w
MultiAdjListNetworkArc<WeightType> *p;* A- n. b7 W7 c* l4 m: Y
cout << "无向图有" << vexNum << "个点，分别为:";4 z, L. P- Z  e5 `
for (int i = 0; i < vexNum; i++)3 X2 i+ J9 x1 N1 c$ g: c$ \$ x
      cout << vexTable.data << " ";
1 [+ M) p, _/ ` cout << endl;6 k4 ^3 Q0 y- U5 E# L$ o
cout << "无向图有" << arcNum << "条边"<<endl;
. I! Q( r5 [( E for (int i = 0; i < vexNum; i++)# p7 o! o) A4 B+ g' `9 @
{
/ J. q4 I' t! z5 \0 A& T       cout<<"和" << vexTable.data << "有关的边:";- X0 ^( U3 x: s6 v. ?
      p = vexTable.firstarc;
( o9 t1 \- R9 e  q2 _       while (p != NULL). T: K5 L3 O& y, t6 x5 j
      {
3 x: W# H4 x1 q2 U          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
8 ?' q0 c5 x* f( b# o; }6 n3 q& w! S          p=NextArc(i,p);, f7 x* M& {4 q1 y5 j/ U
      }
7 w2 H! |3 M2 Z8 J4 y       cout << endl;
: D+ |4 B* X3 Q/ e8 W! B3 u" { }. I  G" `, v3 C: D, m0 F* C: k
}
% V1 E& ~6 V. u8 N- c0 A$ _, Z/ k
% _% }5 q4 C/ r0 p- X6 j; F% K+ P5 P) V* h; Q7 P& }2 F# S
邻接多重表与邻接表的对比5 O: L/ {1 T" ~. f+ X9 W

7 `  L) G& g; ^- G2 W' Y! ~邻接表链接3 @2 s  x5 Z$ R, g) ^$ }5 Z, c$ `  s
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
: m  G( \" [1 E4 j! ]! b在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。3 Z( [) W6 p* Q. i3 ^4 z
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
4 t' W* N4 V1 z1 ?/ @————————————————8 I/ l1 C0 k3 \( Y) h+ ^
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。" z6 \/ Z0 n1 ^% Y" D% }
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
: s" L" u7 L/ U' i) \: h1 L# m/ a! Z" s$ U& @- n: G- [* N! Z
6 X! L8 e, W2 {5 a8 @- F1 _

# V; X7 ~1 i+ t8 C# [4 q! F+ F0 X6 H: i# [2 ?
————————————————
3 C+ K) K: D. _4 |$ c) S版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 |& n) n* F: t4 K0 p) K原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* T$ Z/ C; X  @+ x; r+ v, N, S9 f% F) o4 i7 E* E, B9 `, N

, E" h1 d: C, R& h1 }