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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：! [, p- M, g# Z& ?, V6 W d
data域存储有关顶点的信息；
0 t" X: u! s$ ~5 a8 i' Pfirstarc域是链接指针，指向第一条依附于该顶点的边。
( D+ ?8 F6 D5 |: Z6 s# w所有的顶点结点组成一个顺序表。

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;
6 t9 V+ h7 q2 ~$ ^, X for(int v=0; v<vexNum; v++)8 U1 e# E; V& ]* p% s. A4 E7 d3 T
{
+ w: \1 O9 J  [4 N: l       if(tag[v]==0)
/ b' n  P6 S$ B) v! X$ m5 `# m' ^          DFS1(v);  @% W& l1 s! [* Q' u! R+ p7 u
}( D  E6 s( h7 f0 |
}0 f4 e! e- V) z0 ]5 @
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()+ V( X/ F8 ?, h  J, t
{( s' Z- [4 J. r
stack<int> s;
; h( y9 W: H' F; H+ l1 N int tmp;- @$ A# t4 T5 E5 P; j
MultiAdjListNetworkArc<WeightType> *p,*q;4 [0 b0 e4 C1 }4 W+ e9 M$ `8 m+ M
for(int i=0; i<vexNum; i++)
: a$ {, }4 k" s( @# L       tag=0;/ t# X0 @5 T8 {5 H" D* O
for(int i=0; i<vexNum; i++)
. U6 `! O. A* i5 o {& p) l9 J& k$ `8 d) O, C: y  i; I; W
      tmp=i;+ D  }$ F, ^6 U! @
      while(tag[tmp]==0||!s.empty())
/ A, [) N" L7 t. V& J       {
1 N7 s! R+ S9 j) q0 H# J3 U          p=vexTable[tmp].firstarc;
& x2 V0 y, J7 }4 @4 g- v  G4 b( x          while(tag[tmp]==0)
7 ?1 B& l9 R+ d$ Q& l! `          {; x0 Q! U# d8 L/ ^! y
            s.push(tmp);, i! }0 a0 m( y5 R8 r# U
            cout<<setw(3)<<vexTable[tmp].data;
6 Q( q1 ]+ }- m: P6 a             tag[tmp]=1;
$ l9 \8 @6 r& J, d8 T+ ~             p=vexTable[tmp].firstarc;
1 p+ `  h$ [# i$ j" o             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for: M; U' J$ E# y+ x0 A2 M
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
9 T/ {: {; R; P+ h             //cout<<" 1st    tmp="<<tmp<<endl;" d8 S% @" ]9 ^( D
         }$ B. Q. @6 G9 d3 l) `" |
         if(!s.empty())
  b4 p  M+ q* a1 G4 C, m          {
4 @+ d$ V' N* X1 \0 D1 M# E7 `; N             tmp=s.top();* M; u  X$ W! r; k
            s.pop();
8 r( e6 S' t5 F( N3 [. X. ^7 S5 y             q=vexTable[tmp].firstarc;
0 A& W+ T: d; q' R             int t=tmp;" s+ A9 Q6 {! @
            while(q&&tag[tmp]!=0)
; j# u) g5 j' s8 x4 G) P+ N) G9 T- N             {
2 Y3 ~$ E& H- _; r+ A  X# G                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);, E6 Q0 z- X* B/ Q( ]3 j7 l
                  //cout<<" 2nd    tmp="<<tmp<<endl;
# a8 _8 k/ F9 R+ G6 K$ D2 b                   q=NextArc(t,q);# J4 y' `4 K% p9 c2 Z
            }
9 f4 u* Y5 |/ O2 m$ L' j4 M0 Q             if(tag[tmp]==0)
0 w7 V+ _4 z, c                   s.push(t);0 c: l' B, v& |
            ///1、对应上面连通分支只有1个点的情况
1 u5 ^1 L( L* a             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈! o  ]# h; I9 U
            ///tmp要么等于找到的第一个未访问节点，
, r: \7 m+ B+ C5 Y% r             ///要么等于与t相连最后一个点（已被访问过）
, c7 o8 F3 C' b) d/ u             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
' M& k! B  x% |. l          }
9 v( D! O0 A0 S( }9 n1 n8 ]       }
. A. _: {" l' z3 D+ `% f) \ }
+ H8 W& D6 C0 ~8 i9 t% s}* ~9 U  t' [. I
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-10 a1 c( |4 p" k4 d
template<class ElemType, class WeightType> int
. m* t2 M' |" B6 N8 W0 P" xMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
0 }5 w& L" q- C0 x. Q: b+ X{, H& ?, r/ S7 \4 Z; T* K5 L9 `
if(head==pre)
  v* L6 u$ a4 j; ?       return -1;
& w9 V2 e% }8 O# I' g  n) {' s# B- J3 N! L6 v# l5 Y
MultiAdjListNetworkArc<WeightType> *p;( Q5 Q5 F: E( q) i: E7 Z
p=vexTable[head].firstarc;) I9 w' j* N  d. d8 ]7 A; A; E; N0 o, z
if(pre==-1&&p!=NULL)
3 r: a4 Z* i9 g7 ?& J9 k0 @       return p->adjVex1==head?p->adjVex2:p->adjVex1;
( x) ~' {" L$ s, M! D //pre!=-1&&p!=NULL0 D1 g* `/ [* J
while(p!=NULL)
3 K/ ]9 ?! i3 v  S# s {
$ J+ v0 s* P, X: h' G8 v8 ~$ T       if(p->adjVex1==head && p->adjVex2!=pre)
2 k6 b3 |4 w5 N4 L: N          p=p->nextarc1;
) [8 m2 u( n3 x; ~3 z7 {       else if(p->adjVex2==head && p->adjVex1!=pre)
5 c8 ], i$ U; Y8 I: F4 S          p=p->nextarc2;. ^, t5 f; a" K- e! u
      else if(p->adjVex1==head && p->adjVex2==pre)4 f/ C+ _5 L5 r* c4 S* c
      {
# s# ], |2 O& J( ^. @5 Y0 A# M5 v3 s          p=p->nextarc1;( L0 C1 u$ u: \
         break;
5 q& I9 T2 E: w       }
$ M8 L  ^8 x6 e4 j# }       else if(p->adjVex2==head && p->adjVex1==pre): [- h( {% ^* ]
      {
2 `% O, }5 E' n          p=p->nextarc2;
' q; o: q# r8 y7 Z" @          break;
  Q6 s/ I" U  J' J       }2 M) J5 O, E9 }! y8 a
}! i; X# U& t. N2 p0 O
if(p!=NULL)! K& I# L1 |$ X% A* F
{
4 k! C3 F$ @1 m& p       return p->adjVex1==head?p->adjVex2:p->adjVex1;. `4 C3 I* b! G, l- \5 a0 x& m
}
% q, ?% d" {/ K' J- E7 ? else5 W* `! N" m5 X, k1 Z8 z( h6 G
      return -1;: |6 N7 r) \/ v( j
}/ e# B7 l  S5 ]0 W/ Y. l

4 W7 b# s& w: {% B; L! q$ w7 V* c+ i) H( F# m. Z
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
9 w2 V8 U- m# \0 l# T! F; s{5 h5 b$ s3 Y  z; V3 K
stack<int> s;
8 W4 V( r/ {- U! D: Q int p,cur,pre;7 T" {9 C7 X% Q! x0 X  Y) z1 ~+ l3 o
//MultiAdjListNetworkArc<WeightType> *p,*q;
$ z6 E- R: b) S9 f5 U/ P0 u4 x for(int i=0; i<vexNum; i++) tag=0;//初始化
' H! J1 F0 ~" f3 R- p  o; Y1 f5 |' K# K1 s: {# n
for(int i=0; i<vexNum; i++)
* p' F( O7 B9 O& d& Y {* ~: l0 _: ~: O. D' `
      cur=i;pre=-1;( G5 f: v1 H- g& q2 t1 V
      while(tag[cur]==0||!s.empty()). c" V/ e1 u0 {8 |# K
      {, d; G/ G( H: G9 C. U0 V* \
         while(tag[cur]==0)
: J' V" i# B4 g          {
% l+ @1 ?$ ^; ]5 v. _& D             cout<<vexTable[cur].data<<"  ";
, R, s4 i: F& ?& K' B) h5 b             s.push(cur);3 Q+ ?/ G4 b9 P! ^
            tag[cur]=1;
1 x& P4 V$ q4 E$ ], s. y             //初次访问，标记入栈
8 W* }0 U- t4 A( a; _- Q0 M* ]. ~* t1 M7 R
            p=GetAdjVex(cur,pre);//p是cur的连通顶点# v; ]) q  z8 m6 V5 F( K
            if(p==-1). w( L9 H+ {+ `1 R5 y' J1 l
            {$ j: Y" ^8 `% P: k; p: |: O3 o
               pre=cur;s.pop();2 h) ]& H! ~% z2 w) Q+ @% w" i
               break;! x5 y, G5 \9 l4 ?5 G, b0 P
            }
# K3 M( \: @, \5 m4 j( h! C             else% J: Y' |3 R6 G0 U. C
            {& ]3 c; L. k! y
               pre=cur;
8 v/ d2 o4 P+ y+ Y; A                cur=p;- P/ S- c# ~$ y; p4 X2 C
            }/ H' _5 K, a9 k9 [0 c' _. N) E

: B  t7 k+ m! p2 S! v          }% S+ \/ e+ w" s$ k3 P% \
         while(!s.empty())
4 {9 F: M  X. K0 q          {! t, x: x; P# n" g$ \4 R5 d; R0 O
            cur=s.top();
, D5 n, N: f9 R             p=GetAdjVex(cur,pre);& B2 C7 l  x7 a( W
            if(tag[p]==0)
$ a4 m, |1 p0 R6 c4 u             {
) [$ C4 n3 J% j2 e8 l                   pre=cur;+ J7 f, Z  M1 j$ h$ @
                  cur=p;. `6 Z& \+ }1 J
                  break;
' t7 t+ w4 w; D! }3 V             }
8 {) N5 f+ ^8 p4 i! a3 _: t             else
" f+ a* S& A. \) p- g) G$ W' ]             {
) J* z3 i' d7 ~3 P$ _. ]                   pre=s.top();3 m( H! ~8 I2 V$ H5 C' h4 e. C
                  s.pop();
. O# ]  l7 U' U# _1 X% K) O             }
, ~8 U" e- X$ k0 g: o% I3 v2 k2 p7 `' w1 _, c+ ^4 ?% U
         }  g' U6 I3 W* @* A

. S4 r5 {( I: h+ V) o; N       }
0 J% f: k7 c6 o9 C4 a( } }$ G" p  a( r" z6 `# w
}
0 h" {/ p1 w& g) Y- [" |template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()5 X; ^2 Z8 `7 O2 t. i+ b2 L
{, \  B) R8 F3 h! J+ X; b/ M9 {
for(int i=0; i<vexNum; i++)0 B5 n5 d5 B# z
      tag=0;) b9 A4 q5 |, {: A5 b7 {
queue<int> q;
5 u' E. Z! O7 g; W  @ int tmp,t;2 ]- u3 h( ]- h( y1 _& z
MultiAdjListNetworkArc<WeightType> *p;
, m% R- k% y: h5 F' d% j for(int i=0; i<vexNum; i++)
: J' d7 h& I. A. E( t {
+ w$ J' ]8 S0 t3 M$ h4 r       if(tag==0)4 u, z& G0 Y2 e- L3 \! m
      {
' ]$ C' {( d7 ^. ?          tag=1;
1 k$ q; g) {& C5 c          q.push(i);% l" ]% P: W/ m  {
         cout<<setw(3)<<vexTable.data;
3 D4 ]( K" i8 ]4 F/ |; ?# ]: ?       }
) @' M1 b* f" x3 b2 A+ @6 W       while(!q.empty())
; Z! W. B) I, F1 G+ O8 w% [5 B7 }       {' U$ }4 T3 I+ ?0 B4 O' I
         tmp=q.front();; K: @9 \2 a2 H7 I3 e9 l
         q.pop();
6 y) G, t: P4 |0 b# _+ ^          p=vexTable[tmp].firstarc;
# Q6 I2 W. b0 C5 o          while(p!=NULL): y9 B2 B" X7 H5 v8 w  z
         {
- ?" ?1 U: y* s( v: ]2 K. \8 F             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
; T  S  o+ C, Q: H- I) P0 d* ^             if(tag[t]==0)1 f! n$ L9 s# \( Y9 x! k
            {
9 U: ], R( s/ K. ^) G& l                   cout<<setw(3)<<vexTable[t].data;
" v  _. V. M- r0 @/ x" j% o" Q. N                   tag[t]=1;
/ p) J5 B, \& z  W& f( N                   q.push(t);
- y0 q- _+ G! w/ @             }
( I; G, i- \6 m0 g4 V0 t             p=NextArc(tmp,p);2 u, j3 P# {7 y( I" I4 z: t; f% X
         }
' P' m" m* W$ p0 w0 Y) Y       }
& `9 H0 \! v2 ~1 i, R }8 ^2 E; \0 ~8 W  ^# U1 c6 a  ^
}4 F& F9 V" r% b& D
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()' }- n, o4 ^3 [
{
, V  V( ^0 U, T5 A! m$ O( J MultiAdjListNetworkArc<WeightType> *p;. |4 d8 G" y( p9 h/ w) {" M
cout << "无向图有" << vexNum << "个点，分别为:";
0 H3 j" o. v" e& Q( Q) p for (int i = 0; i < vexNum; i++)
" {9 \+ Z# W7 v2 S+ l/ N       cout << vexTable.data << " ";
3 T( B: [7 \1 y4 V& }8 U$ ^0 d cout << endl;
# {6 I$ o  V! y2 a7 [- X0 a6 C cout << "无向图有" << arcNum << "条边"<<endl;
3 s! @, d4 z1 G8 y( ~) G! i for (int i = 0; i < vexNum; i++)2 {. S/ D8 B" C* K
{" \( }0 r, |. B
      cout<<"和" << vexTable.data << "有关的边:";
7 D, C8 I6 w( r5 A5 o' a9 k$ r       p = vexTable.firstarc;4 _# H. S/ h& X3 o3 S
      while (p != NULL)4 L- O: z) `+ o  \8 I% |2 ~' [) y
      {, q# R: Z4 ^3 O% k
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
1 v/ ^' A' c+ D7 ]# ~1 u          p=NextArc(i,p);3 B: F( d# C/ Y2 @/ e8 }$ G. N, Q
      }
( J: s+ _4 D7 |       cout << endl;+ y+ q1 t- q. r: c! D
}
- v2 R: ^1 A  a0 L2 ^/ q5 e3 i. L}
, \. k. p! c3 r( _& ]* u2 \  Z3 K  L) d  [
( S! n( b( F% l, |6 d
邻接多重表与邻接表的对比
+ s/ A  \4 i$ Q' M
+ U3 Q$ F0 t2 n7 }; _邻接表链接) W3 X9 q3 m# Q, F
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
" m$ v& \  u! b% ]) ]在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
3 c3 T' J3 |* y- h& n为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
4 d7 v# W' S5 r: Y3 {# u————————————————
' _% t9 {1 i1 D; y* @版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。# A/ X& v, F& g
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
8 x8 i: u0 Z0 _$ l+ W; }9 L. O' p( ^% Y% {; f& A  x
8 r4 }8 Q  j6 ], ?* Q" f
: u# ~2 i$ J4 M
1 i* K$ d* E$ n0 }: `" b' u. t
————————————————- U: D9 h' ^$ W/ l- q8 ^
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。4 V2 H: A% `2 f6 s2 e0 _
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669581 N* H' t, n9 h  Q9 |5 F

! d. G/ ~, C  r0 K! I8 |
3 l- k8 v+ q7 T* O4 P! M