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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：# A2 k# i4 k! p3 x4 D% v
data域存储有关顶点的信息；
0 P1 K# S& N9 bfirstarc域是链接指针，指向第一条依附于该顶点的边。" L8 K4 {: y$ L' w$ E, ?) J1 W' 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;, I5 b/ a' C8 Q4 z. O
for(int v=0; v<vexNum; v++)/ I+ j. Y' E5 a9 l, f$ e5 R
{
3 U  @, t+ w# B. r) ^, Q       if(tag[v]==0)
( K) I" D7 F( [# L6 \+ z          DFS1(v);
8 m' L" F2 ^" e) c! ^# C }
. i' K  n: S4 k: }6 }6 ~}
0 u; s& V3 U8 w2 l  O9 btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()$ c1 d4 h4 C; C1 O  T( {5 N
{
& c7 F* `2 c' n4 p& Z: f1 }. c stack<int> s;
: ?  n- C2 L+ p) G7 V int tmp;
  ]2 U0 V) L% @4 T* A MultiAdjListNetworkArc<WeightType> *p,*q;6 t( A2 Y' u4 `
for(int i=0; i<vexNum; i++)
, H) B0 j4 B5 u+ g8 ]% x       tag=0;) p* O! C& D* D. F- f. t
for(int i=0; i<vexNum; i++)
4 u, b/ T, d3 }8 |; t1 n {1 q& K- ?2 {' F+ J
      tmp=i;7 Y" o$ f+ {/ U' ~
      while(tag[tmp]==0||!s.empty())
  N3 ^; l) }; i5 e       {2 u) n! ~0 G3 q2 K. B
         p=vexTable[tmp].firstarc;" R/ n0 f0 V2 {5 @
         while(tag[tmp]==0)
' E; f- d0 H# `/ q" c4 a9 m" `          {
2 x; ?0 K5 M% O/ h( T: C$ E! c7 O             s.push(tmp);% b% y# N+ [  R! N- g9 ^- R
            cout<<setw(3)<<vexTable[tmp].data;
9 Q0 @4 y4 \0 N7 a             tag[tmp]=1;
) ~/ |7 g8 {; r6 w# A% V             p=vexTable[tmp].firstarc;7 f8 c/ U2 W& ]" ?" c
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for" P9 F- N/ b) `: R" }
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);+ u$ i' X5 e2 X8 p9 y3 q
            //cout<<" 1st    tmp="<<tmp<<endl;: E- b& g' ?$ Q7 w' P/ z2 z
         }
3 ]& M( ?  E  B1 J' Y          if(!s.empty()); i, i; X5 X  m7 q
         {
- c6 N2 Z$ N9 p4 m             tmp=s.top();4 x* @) t. X2 Y1 ^4 ~, j9 X
            s.pop();( P3 N/ u# n/ e& F
            q=vexTable[tmp].firstarc;+ O" Q4 ~( ^* |( \
            int t=tmp;
6 z, W1 B1 A+ I- ?* ~             while(q&&tag[tmp]!=0)
0 I2 A' B' e: R" B  z+ _             {
- N$ X2 I6 Q, w+ |. @7 R8 Q                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
6 F" d9 N) V/ T$ ~# T: f! J                   //cout<<" 2nd    tmp="<<tmp<<endl;; V, X( i( c# K
                  q=NextArc(t,q);. c8 z! Z/ K3 T4 T2 b( c; i2 \( q
            }$ y* V1 ^# W& j5 ]: ]! q% ?
            if(tag[tmp]==0)1 l) u3 ?& E( u0 X- C' F- p
                  s.push(t);
7 i; h! S6 V% W# K. T  j             ///1、对应上面连通分支只有1个点的情况
, f1 Y* v! C( V- B0 G* r             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈# H. S7 B" b5 J6 n7 q/ {' t# w
            ///tmp要么等于找到的第一个未访问节点，  Q" z  ?& V( K4 T
            ///要么等于与t相连最后一个点（已被访问过）
7 \6 F* O0 P3 d% _6 A1 V: V             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
: ~0 y9 F3 z3 S2 D          }1 F! p% D! @0 E4 B6 y2 F) j; Y- [
      }1 f( W  A. a& X, T' _
}
  m* g" z) b5 V}
# c* f0 c2 d# ]) b9 U' Z  q//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1, E+ b' L0 H- K0 c8 i4 Q
template<class ElemType, class WeightType> int
" {! \, r, X% K- XMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
. ^- m2 o( S# c( N9 n" b1 R{
/ V5 ^* [. A0 P if(head==pre)
$ {; j% r4 E* }' B  i/ D$ K: s       return -1;
' [5 z: E% e3 a, f0 S4 c( M+ W$ E& M* G2 \* K
MultiAdjListNetworkArc<WeightType> *p;
: @7 }* ?' U0 ^8 C9 V2 x4 ? p=vexTable[head].firstarc;
9 c' l, I  G# e: O& z% } if(pre==-1&&p!=NULL)
3 G8 E6 j! C4 l8 P# v       return p->adjVex1==head?p->adjVex2:p->adjVex1;
6 o5 k, p3 t- G8 u- w0 O% C% `6 v) S //pre!=-1&&p!=NULL
7 G5 N0 k9 u7 m1 _6 n) G while(p!=NULL)$ q6 @7 N3 Z+ v% I/ \& x, I) h, H
{# E, g5 p9 a: a0 f+ h
      if(p->adjVex1==head && p->adjVex2!=pre)
/ V8 b4 X# c; J5 A0 r) E: }. {$ V          p=p->nextarc1;) T! I, `# {9 `  ?4 X8 \
      else if(p->adjVex2==head && p->adjVex1!=pre)
* `2 ~+ R9 m1 n* |          p=p->nextarc2;  w! Z+ y# G$ m& E/ i5 I
      else if(p->adjVex1==head && p->adjVex2==pre)3 a% X; q2 x+ A
      {: R0 i3 Z9 P# [  W- w% t& a5 k* {
         p=p->nextarc1;
1 G+ w5 r, L. {* [6 A          break;
- V) Z: B7 Q: D, d1 s, \       }
! _( @; a$ c4 R) U. N- s       else if(p->adjVex2==head && p->adjVex1==pre)
% {9 Y( U' w6 T  A       {% o2 m5 n2 J' I/ p* ]3 |/ N( K1 o
         p=p->nextarc2;& I) w* _$ W! h. K3 ~, u
         break;
  |- Z, [- k) S$ t       }
1 k1 v: K: W! j }+ q. H, D' S7 Q1 z( v
if(p!=NULL)
! Z+ [" M# k: E/ L& _  g( D6 W {1 h6 {) m6 R+ i0 C4 P+ a
      return p->adjVex1==head?p->adjVex2:p->adjVex1;/ _' A/ M1 J3 E3 f9 i9 c
}
( a% Q, ]+ u) g5 b/ H/ V( L4 o else4 a. Y1 X$ x( A  j
      return -1;
% q2 r/ o3 B# r5 m' r  \2 q}
  y4 r5 l& h/ v! K" B& w( g# T# J) r2 i: Q2 {

6 ?! ^2 [8 S- i/ O1 {' e# _1 o1 Utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(); f; Q3 W8 U+ L0 ?8 n1 X$ ]
{4 S% E8 a! x0 [) Z3 Q  E$ c
stack<int> s;
7 E  r' r3 |7 e( h% w( g% y int p,cur,pre;
+ Y8 R- i8 k8 a4 n //MultiAdjListNetworkArc<WeightType> *p,*q;' {0 b" o8 B$ R6 {
for(int i=0; i<vexNum; i++) tag=0;//初始化
/ I/ s$ F, D9 V7 p# ~
4 X! j1 W  ?, S for(int i=0; i<vexNum; i++)
. T6 l- d7 s# W% ` {6 N) e5 i( n5 i* q# L( x2 H+ E& C
      cur=i;pre=-1;
+ W, ~' q3 E5 [7 `$ A0 v       while(tag[cur]==0||!s.empty())
4 v) Y  R' J5 _. ^& ?5 d, m       {, w% k9 v6 ]: k/ S8 Z/ o- y4 h
         while(tag[cur]==0)/ n% W, Y  E3 w+ t
         {
, _- ~3 p2 d" f& f  ^/ g             cout<<vexTable[cur].data<<"  ";7 b7 s# _& t$ {2 P
            s.push(cur);: Y" Q+ ]) A5 \0 L
            tag[cur]=1;
0 ]2 [+ u( q( C/ Y             //初次访问，标记入栈5 s" S* C: E' Q& B  `5 a

* \' y& y6 \, t* [             p=GetAdjVex(cur,pre);//p是cur的连通顶点
7 x6 H& k- ]/ o  X. E             if(p==-1)
2 |$ e. U" M1 W7 w# G' a% X! _             {
4 N9 t( V- `* f                pre=cur;s.pop();
# O$ X+ ]% r$ G, {/ ?2 X# x                break;& N2 d; \9 e: i' J
            }
7 G8 j) R7 _3 D% g             else' L& B% k: N0 ^+ ^1 y1 J
            {- D7 t' Q0 C+ Y: w" q1 W' n
               pre=cur;, B9 @  ?( g, X% K$ A; |" d9 \0 R
               cur=p;/ K# l& }) S# n0 S
            }
- f9 D: {' \1 _) C. y/ q9 P1 a1 e6 r# C4 O' C3 R* ~; V5 U
         }7 q2 e1 ?1 o- [, m
         while(!s.empty())7 N4 T9 o( G! e* I- {# o* P" c
         {7 h2 }5 T% J8 i2 T: P
            cur=s.top();. A: j: U, R/ C' m  z9 W3 U$ f& w/ [) l
            p=GetAdjVex(cur,pre);, r3 X; T0 c6 f' r1 T% a  @0 D
            if(tag[p]==0). Z8 M8 C0 F3 A$ g# N2 C
            {2 P* D! o& k" R! V% b/ m  `' W
                  pre=cur;
% h" ]* |3 z4 h$ N* Q/ g3 f' [* u* T4 {                   cur=p;( ^: w( G" R5 ]' b! t* k7 S
                  break;7 V6 ~6 X8 R- J# Z
            }% {, W* J7 }, `( Y- A' M5 M9 o0 x
            else
, w2 A8 {6 O0 Q0 Q: Y, x             {
* J' I0 W* A5 h3 D5 _$ J  o                   pre=s.top();& p0 I& y" n, q9 ^8 K
                  s.pop();
2 W+ }8 J4 `0 |5 b7 Y& g             }
0 H$ n% j0 [* g  h
6 v% \: K& ]* }0 p          }- d: X. l% T) D+ P, J* g
# P& R5 F0 u, L, e6 B. B& q
      }
  `: l+ M! w8 l; Y2 ]' A6 B1 u% \ }
$ F; M9 A/ ]5 g; v, C- B}
6 z$ Y4 L- G( w. d* Utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()9 s' O$ |9 W. \0 y( Q  Z2 S+ m* W
{
6 n4 m. |8 q8 r4 b: H for(int i=0; i<vexNum; i++)
' r  `: j4 y- i2 ~& a       tag=0;  U1 ^4 c3 a" A* N! n+ S
queue<int> q;7 I( F3 s( d! W- o+ i
int tmp,t;" H, J  e7 {. j8 F/ I& z$ s
MultiAdjListNetworkArc<WeightType> *p;
' c9 O3 F2 `& C; I! d, i for(int i=0; i<vexNum; i++)( x. l) s4 ]* S: S
{" m4 S1 P5 v' S7 ^% ^- r
      if(tag==0)* P, R# j2 {" G  F, h4 q+ R/ v
      {
0 J0 p7 ~" k, A1 }* W          tag=1;
9 g% B% E- [( r          q.push(i);
5 z$ V+ b  \9 V  q$ w8 s3 n          cout<<setw(3)<<vexTable.data;
' U9 j6 Z; M  A# _5 B       }
. ~, V% n$ ^+ y8 c3 B( b9 S       while(!q.empty())1 F1 I9 y- |4 o, D6 h
      {
0 A. `8 u  T! g6 V          tmp=q.front();
& ^. |* I" I' _          q.pop();
6 [7 k; v' l3 M7 Z* m! R          p=vexTable[tmp].firstarc;
; P  x. i' C" J& I+ F  v          while(p!=NULL)1 T' h3 v0 D3 n8 x* Z' T
         {2 O; }$ c( N8 N: L& g7 z
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);# V  ]2 H4 H: e# k4 v
            if(tag[t]==0)! V& h) [, S2 N3 p
            {
- {' R; o) `- D2 l; V                   cout<<setw(3)<<vexTable[t].data;
) A" x( ^3 o6 s* c- Y                   tag[t]=1;
0 g4 _6 K- s# }) T3 C  ~                   q.push(t);
2 t2 T( j2 @" O' t5 h             }
6 S0 L8 d' }+ ~+ D  o& K. i! d             p=NextArc(tmp,p);3 C+ b4 m3 }4 c& L0 \2 M
         }
! e6 q* ]' a6 X; S; L* F0 D3 L       }, U4 v0 d$ K/ i& H4 u* Z
}
  a: Q  i% R9 i& q}! l0 }7 w8 A: F# C- |7 E
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()! O: `* _1 Z- v% w- {
{
6 k9 u9 y  I5 x/ N MultiAdjListNetworkArc<WeightType> *p;0 a$ I6 r- _2 s; d, z7 z5 u
cout << "无向图有" << vexNum << "个点，分别为:";9 d, F. }/ g0 l: T+ r
for (int i = 0; i < vexNum; i++)! w4 `2 l1 [' b, Z
      cout << vexTable.data << " ";
* O" V: e7 v% v& ], q/ Z" Q; W cout << endl;1 D9 i* o+ J2 X- r3 ^3 S, w
cout << "无向图有" << arcNum << "条边"<<endl;
6 {# `, V! P4 X8 B8 r7 t! I for (int i = 0; i < vexNum; i++)
5 T- i5 A; J( @1 Y {
  J. G( W& x0 r) C2 Y       cout<<"和" << vexTable.data << "有关的边:";$ g- y" n$ t' Y
      p = vexTable.firstarc;
1 r0 `4 U, M- [0 U% K       while (p != NULL)+ L9 V6 [7 b# }; D, ^  V& E' k
      {" B) @8 `/ o# |7 ]! ~; y9 G9 z
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
4 h1 V4 n3 q$ X; w* h          p=NextArc(i,p);7 ~. j. E( N) g; F: k, G
      }
1 z5 l: K: L! g' f' r       cout << endl;4 n) X6 Z' C7 c  ]4 m
}
. A6 k& R; z( U. {3 ?}
7 s( V4 E( p/ `% u) Q. p6 k. E' E3 B7 g
/ o' C6 F: [9 i% y, t
邻接多重表与邻接表的对比
$ K- {% G5 J- i" v1 R5 f- x
5 g: m, H# W# S5 K- Q邻接表链接' x6 n6 w. M; F' k2 L+ d3 J% P
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
- u* N; m( c: Y8 j5 `在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。, v7 b! o+ }* E& l9 Y
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
7 R9 Y+ w+ E0 s& L————————————————
; d3 I: |8 I. l4 w版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。5 s2 k0 _2 D. O3 d; _# X% P7 a8 V
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958, F$ J: h. u. ~
  Q4 A& c, M1 U& Q
8 O9 `5 j0 U% [
, V7 j4 [6 _. h4 P

1 `- `9 y# x: ?————————————————
) W- s4 t! O3 J版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! j' C8 r" b- h* U7 _! M- H0 p; p- H7 m原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669585 t5 e" G; b4 J% H) h9 M

7 I. V+ u, ?# E7 y' C: v. V2 Q! d# z* O( ]