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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：7 I( y. r! ?4 o$ T# S6 Q4 J" Q
data域存储有关顶点的信息；
$ M# O% i( `' P jfirstarc域是链接指针，指向第一条依附于该顶点的边。
, ^$ _( l k4 S+ k% S( B; 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;" T6 J) N* o: D7 u6 P% w$ u6 ?
for(int v=0; v<vexNum; v++)
" `$ G+ {; J% m; A7 k {
* v8 E4 d! Y- ~6 G1 {& Y  L       if(tag[v]==0)
9 E# L9 @% r% m  e8 L- y  \7 l' i          DFS1(v);
% K' z: k  k4 j/ T- b0 r- _ }$ M4 L7 @7 o7 ~# u+ R3 u  Q
}5 Y$ f  \0 s4 _* e
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()! i* i- _+ K* P# j" Q9 O
{4 ^* H7 d4 h9 V9 s- V7 A
stack<int> s;
! W( P" ]1 E& { int tmp;, N% A  M: Z+ D& _( W1 G2 Q
MultiAdjListNetworkArc<WeightType> *p,*q;
6 S& |6 m2 U( r3 }# V( V for(int i=0; i<vexNum; i++)
* y: g( s' O4 I8 G       tag=0;; x9 b4 L; I2 g. u7 N" {9 c$ f
for(int i=0; i<vexNum; i++)( r* p8 r4 `, U: _2 S! u0 j1 Q* z, \
{# j7 n5 ~" z# k
      tmp=i;
# h) P- S: I/ i! G) Y       while(tag[tmp]==0||!s.empty())
" _6 o: H8 m2 R2 v, u       {
- s- a) q) r4 }7 I3 x  Q          p=vexTable[tmp].firstarc;
/ h% \! D0 V7 G; k          while(tag[tmp]==0)! G! p6 t; Q8 ?
         {
7 D" D# d8 L0 {# t& {" }: w             s.push(tmp);% u" n6 b; z: \  |; v$ [
            cout<<setw(3)<<vexTable[tmp].data;! A# ]& _3 V. \, w/ C8 W
            tag[tmp]=1;
4 ~4 G5 V% Z5 s( H             p=vexTable[tmp].firstarc;
" _9 o, n* _% V& `& F             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
3 i6 `& I9 `" L9 o7 J             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);" R' `5 `7 z) T/ J/ E
            //cout<<" 1st    tmp="<<tmp<<endl;& V! Q1 c: k3 N5 O" o0 ?
         }; m3 }6 N4 q, h  y8 V
         if(!s.empty())" V, c& ~; ]7 I' w- {! x
         {
; d: o% \8 h% p             tmp=s.top();
0 K9 v9 ^2 n/ ?6 A6 v- G0 b& `" ~             s.pop();5 u+ `2 c8 G; C4 U, l  J& h
            q=vexTable[tmp].firstarc;: J9 h$ P1 B& ?1 T5 X
            int t=tmp;
/ i" E5 A+ S8 ?& K& N             while(q&&tag[tmp]!=0)9 J: t0 ]. @8 `/ j3 A" v- Q
            {
2 F' @* l: J8 N+ R! ^; {                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
9 X3 |3 z4 w: z+ A                   //cout<<" 2nd    tmp="<<tmp<<endl;7 r: H! _+ w- _% C7 a% ^
                  q=NextArc(t,q);. M. z3 g4 O# g9 \: M
            }# \, W% R/ H, Y  `9 {7 h2 Y( L
            if(tag[tmp]==0)' s5 T7 t& O: ?: D: L
                  s.push(t);
9 {, \& l3 w4 t  \9 v5 X- L# S             ///1、对应上面连通分支只有1个点的情况/ M9 A6 u( |; L, O4 C/ y
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈0 q. W+ s& i% A5 V* O0 \
            ///tmp要么等于找到的第一个未访问节点，! `- a4 p7 d; R" |" C' m6 k
            ///要么等于与t相连最后一个点（已被访问过）' j8 ~) g; R  q
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
# d6 h. |, j9 |4 B9 X% v          }. F* x1 G# {# N# Q
      }. e9 S6 I( A; `& _2 f, g
}% Z$ h: j3 o( X* W  ?1 R( l
}
; B# h' X2 ^! Q; \3 g- _//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
+ z3 p/ v" P3 d2 ^5 z, `" rtemplate<class ElemType, class WeightType> int
2 X: J4 a! n; v) y2 ~# hMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
) T2 o: ?5 k9 b, B( s{# U; ]5 b# p9 m/ e
if(head==pre)
( I0 Q' c4 f" h( E+ r( u       return -1;! B: {$ K% o* T3 n

4 R; |! W+ {# X1 }) ? MultiAdjListNetworkArc<WeightType> *p;' }2 U. N+ F, J* |- p
p=vexTable[head].firstarc;( y5 }5 {0 ]' {
if(pre==-1&&p!=NULL)
+ T/ [7 A+ {  M. c       return p->adjVex1==head?p->adjVex2:p->adjVex1;+ M9 o6 R: L% Z/ C8 u% q4 k; n0 W
//pre!=-1&&p!=NULL; E, D" }- {6 b* b1 b2 X1 V
while(p!=NULL)3 C4 M3 E& X8 w' [4 r- q6 `* v, f
{
- q1 t( _- A' Q" ?       if(p->adjVex1==head && p->adjVex2!=pre)* u' W; G0 P* Y$ _) T# t* O2 _
         p=p->nextarc1;
+ Y; {7 H7 k4 f. f, d: F5 z; Z       else if(p->adjVex2==head && p->adjVex1!=pre)" S- m- b0 D0 I: O
         p=p->nextarc2;
; L2 o2 |* |/ O       else if(p->adjVex1==head && p->adjVex2==pre)
5 P* C- a. f8 X! d" q6 ]0 J2 T1 X  p       {) l. k9 ~3 l$ a9 u
         p=p->nextarc1;
, \5 N0 l  }6 l" C5 K+ J          break;
% L4 Z& {  L5 r; i' t* e       }
" m6 P) D2 i) N  o% ~+ Y0 O       else if(p->adjVex2==head && p->adjVex1==pre)
8 M( S! f8 v7 r, M5 F       {
6 ^! T) O& O6 E" V( G6 u( E          p=p->nextarc2;
8 \! v: @. z4 }          break;- O# N4 A0 D. l% A" J1 V% H
      }
3 @( C3 ?; X# s4 w1 h }
6 E) |" d/ M- M% d" j: X* ^ if(p!=NULL)3 I( c3 i+ g  Q6 B, k- I
{
% K* P( U! c% c5 T( b4 X# b       return p->adjVex1==head?p->adjVex2:p->adjVex1;
* o* h8 u) q5 J8 K }
4 ]% y: S" s8 x, U) l7 o% E- A else
# g3 D1 K! e0 \! B7 V       return -1;
% q1 Q7 N. d4 I! x2 e3 q% }! D& i& L}
4 }: Y# y' a  N8 l: s( J8 B; m# V+ F3 j; f

" K* u9 `3 g1 K4 ~; ?template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
( u* f: ?6 r  C{
- K% \* i* x( E$ ~' d) l stack<int> s;% L3 h) V5 \- J& b/ |
int p,cur,pre;
1 Z  B( N8 h6 m+ t% t) t //MultiAdjListNetworkArc<WeightType> *p,*q;& k# \# M) e- c; {0 z& j  [
for(int i=0; i<vexNum; i++) tag=0;//初始化
. U6 y3 ~! w# ^
; e% J' F7 H  c' F" @$ I; U* W for(int i=0; i<vexNum; i++)
$ J2 J* ?9 g9 C5 Y {- i# ~0 l% a- P9 t) ^) `4 l9 y
      cur=i;pre=-1;: s) A7 Q6 G" U; ~
      while(tag[cur]==0||!s.empty()); u8 n* r9 t% X+ {' G+ C
      {2 M% p. {& B5 ^. t. L$ @0 z3 L
         while(tag[cur]==0)2 h2 K+ ?3 i" [7 l- J  }
         {7 G0 f. G5 t+ p+ M+ n( c+ P
            cout<<vexTable[cur].data<<"  ";
7 `# J0 `% W* H' X1 U% e  I4 r             s.push(cur);" K5 \1 K6 K- k, [$ G# F" o
            tag[cur]=1;
! Y& F6 ~$ t& E$ ^/ _             //初次访问，标记入栈# ?, l6 [" y- B

9 ~) [3 W) S, e$ j% d             p=GetAdjVex(cur,pre);//p是cur的连通顶点, J( J6 B& I1 j8 q
            if(p==-1)  e/ _+ v' u  c/ B1 q6 M  s" c
            {
1 X5 _1 _6 F6 L+ E  C! |                pre=cur;s.pop();# ~& F7 y; l. v/ {' p
               break;
0 `2 I* y' U5 z- }" {             }
9 B$ h5 z+ b! n1 c! z2 u" x             else/ b" L8 D' y0 l* }1 p1 z
            {& L  g3 m) Z! W) @5 z; ^
               pre=cur;
" X6 N% F, H! k) ]/ n" y3 N                cur=p;& m/ H# {9 d9 f. X
            }
3 r4 W# Q5 z+ p9 z7 Y' s8 {& h% K# e' d& ~+ t, P6 q
         }
% z: {' v# ^1 b          while(!s.empty())
3 H; B0 `% ?& [& d          {' j( f' G+ J! R9 E7 }2 \3 X
            cur=s.top();7 h6 B) z$ U4 ~' |
            p=GetAdjVex(cur,pre);
/ M1 G0 E: \- r, w. J8 w7 `# m             if(tag[p]==0), i& f6 I; y1 G; R( t, ^
            {
4 _' v% D/ G4 H8 f                   pre=cur;
/ y/ n4 e* x" ^; {/ w                   cur=p;/ c5 T' j4 x0 ]! K. l
                  break;  V/ [- L3 j6 t/ T
            }0 g7 B9 d9 L0 O5 ~8 k& v( n
            else4 _3 `" I) g+ D' b
            {1 a0 A: x7 ~4 g6 _5 d4 H) [, X  x
                  pre=s.top();
6 ~$ ]" C1 s2 S+ f% U6 h9 n; T! A                   s.pop();- I0 z: \& V; t. ^1 M$ `3 J
            }
* {2 T( d. f3 u! ~2 I4 J% G
+ M- p, e. t( K3 h& C          }$ K: A, f( S! v) c

3 r$ X5 l* e/ v1 L       }4 d+ ^5 m9 p- l/ c7 H& |
}
. c# x4 W$ q( J: G3 ~  T}2 I9 v3 q% G: ~( N8 S. L; |* g
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
( n9 f( Y  ?6 ]6 v' u* ^{
" \! g) {3 W/ D- ?6 e' _# ^* z for(int i=0; i<vexNum; i++)) D, V4 a; n5 L) Y
      tag=0;
8 U" H) |# L8 O, f queue<int> q;
! F4 u/ J- w+ T( q int tmp,t;: f5 i3 {6 N0 X1 Y5 f* Z) u
MultiAdjListNetworkArc<WeightType> *p;
for(int i=0; i<vexNum; i++)
8 N( @& [& H# @  s. L  Y3 f7 e7 R {
9 k8 `0 N& i* D; q/ T       if(tag==0)  W0 Z1 L$ K0 m( M- Q/ S
      {
5 Y4 ~0 z4 A& E* x1 b: Y% h          tag=1;
' t* I7 P0 W; P# i          q.push(i);. G4 l" X, B4 j4 I6 h* i
         cout<<setw(3)<<vexTable.data;
  L$ x  a) A/ e) g& R5 H       }
$ {, v/ q# }1 ~; W$ e) M: n       while(!q.empty())
) g1 P: }) B$ Y4 h$ D; o1 X       {6 J1 C# ?" I; n9 j! w
         tmp=q.front();( }$ ?' x: E: g1 H
         q.pop();
3 _, U; F6 B+ W( j; z. g' n          p=vexTable[tmp].firstarc;; X* _( f  |5 v* a$ }  H+ }
         while(p!=NULL)
* V9 i# v* |: F# M% R" ^          {
6 I4 T0 e) C* m, h             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
; t/ I1 K7 m$ \. s( o             if(tag[t]==0)
, M' K7 Z0 I+ z             {
2 ^/ z. l! ]/ Q, ]+ b, }8 ]                   cout<<setw(3)<<vexTable[t].data;5 w9 U$ m$ Y  o
                  tag[t]=1;
; Q  |! C% Y# ~' Q1 R% |                   q.push(t);
& G2 I# l( Z* [$ T; M9 K             }' V- d- A) P0 @0 \
            p=NextArc(tmp,p);
5 T- V: r, ?- _  Q9 }+ y7 {. c3 n          }
9 B  C$ g# b' v. B0 j: X0 \* t% S       }! |* y$ i9 s3 Q4 c" V' D. Z
}2 t3 i: z% M4 c' ]) q$ ^& Q: G1 F
}4 `9 e  ^. c! f/ ]: b# I
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()1 s0 ~# w. o; @5 e0 Y9 o8 ~; A% F3 I
{( {/ [- A% R% L/ Z: \
MultiAdjListNetworkArc<WeightType> *p;1 e9 V. J! z+ c* s+ G9 y% [3 V( V
cout << "无向图有" << vexNum << "个点，分别为:";
. T* \: N) f  w1 b0 c for (int i = 0; i < vexNum; i++)4 x' ?3 Z' q' ~0 [2 [
      cout << vexTable.data << " ";5 f0 Y& d- b: Z2 }& \
cout << endl;
, f, r. t$ @1 t9 F; k cout << "无向图有" << arcNum << "条边"<<endl;
, f. Q9 T7 T1 P! g' y2 V for (int i = 0; i < vexNum; i++)% [1 J7 x6 D4 l0 Q+ Y8 Q+ R- c
{
2 S. J( o6 @, Z' }       cout<<"和" << vexTable.data << "有关的边:";
0 G( u% {1 k3 z* R7 ~3 u       p = vexTable.firstarc;9 d6 \" T0 x0 n. R
      while (p != NULL)/ F+ x3 |8 L. }% ]' _* R% M& Z
      {+ ~9 |7 F& L4 J5 }. K
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";# I  m' _  k; S! @- H9 V
         p=NextArc(i,p);1 n& ]' u) s' K' x: s% [
      }
) f- {5 [5 L1 m1 Q7 }+ D       cout << endl;3 k3 \/ M3 G! L$ C
}
& I, e, c( p$ C( ]}# O8 a( w: C1 ]' F

& J9 d. O3 _$ g" o7 x
7 A' X) s! t- m邻接多重表与邻接表的对比& i& D# ~8 a( S6 d- H9 M+ Z" i& c4 |
6 {% h7 Y3 a- L
邻接表链接' w6 l7 I) z  B- F5 b5 O' i% A! P
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。4 V# i' E+ @9 h: [
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。( E/ m8 B+ {: {. L: n$ F$ p
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。" v% H6 C  T$ r8 x5 i: M
————————————————
6 v. S( {6 e1 R% }) m9 `( [版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) d. Z" f  v) e: V' ?3 `0 Q原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958% p6 N! k& h# ?9 f4 ^% u$ z

% j" I& T- J- L! K  Q& J& p, Z3 H  b

* b* F4 }# ?4 c: q9 c; t' c  M8 G& X1 E5 V8 J/ N0 R. h
————————————————* A- B4 M# [% g4 c1 K1 D8 J
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  {4 Y2 E3 |% ?  M4 x6 T
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* x9 n' w. A+ [! t6 V7 O! B
6 A& x; H2 e7 V4 s5 |, Q  D, t8 u0 C3 _1 L. R9 D" |8 b$ R