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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
6 ?2 a5 O0 H& D8 a  ^data域存储有关顶点的信息；
7 N3 W2 ?! W9 J  C3 N- S) e, ~firstarc域是链接指针，指向第一条依附于该顶点的边。
) d9 q" k, [- p" s  E* L% j+ z所有的顶点结点组成一个顺序表。

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;
# `: ?$ e- t8 p' d& r1 a for(int v=0; v<vexNum; v++)! |* H* P+ ?0 ]8 T
{4 Q3 L7 a  T5 N) x
      if(tag[v]==0)
3 u) {! u9 u0 B9 C/ x/ ?          DFS1(v);9 H! s, ^% Q1 v& s8 j
}
8 z! z  _( k& }; V7 ~. L}5 k. a3 Y7 d* X. s" A1 h
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()  t$ s- d9 a5 V9 x
{
  q% t8 u  m* x; ]4 w stack<int> s;
4 o, M) [1 G* x% p+ g1 T' M4 i int tmp;
: z; u+ E+ p1 S MultiAdjListNetworkArc<WeightType> *p,*q;& z- T2 c! n3 k1 z( Z( I) ~  n
for(int i=0; i<vexNum; i++)
% @, {' @+ ?$ }. R: I" s7 c9 x       tag=0;
: J& |" Q! C$ I/ p4 v4 Z for(int i=0; i<vexNum; i++)
+ S3 B' ?+ P& M. | {
/ j' @8 P; V8 M0 n5 V& k       tmp=i;
) z& K( k4 ^" }/ [       while(tag[tmp]==0||!s.empty())
- Y6 A% D! r. _3 @# r# o       {
# |( ?5 T7 z. t5 Y+ Z          p=vexTable[tmp].firstarc;1 F* h  b: F4 A( R( M
         while(tag[tmp]==0)- ^* E4 w/ U' r1 D# n' i
         {$ b% |% p% C/ R4 U
            s.push(tmp);( t: }5 b. \6 D% H
            cout<<setw(3)<<vexTable[tmp].data;
: J3 f; g+ j5 |) t2 C# b             tag[tmp]=1;  j6 D- I' ]& x2 ]6 A2 B
            p=vexTable[tmp].firstarc;
  M+ k1 @) r0 H3 D$ P6 J             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
  l* m1 M% X: }$ ^6 d) l             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
- h. O. m4 p( s$ ?6 d7 b! S) q$ C             //cout<<" 1st    tmp="<<tmp<<endl;* R7 n$ T9 W: r: x; A! k4 ]
         }
' d; X6 y) |5 p          if(!s.empty())% a1 v9 |$ S: N
         {4 q! ^; b- j8 W) V: b3 [1 G
            tmp=s.top();
5 F  h& m8 F, j7 J' ?             s.pop();
4 V$ S4 v4 \3 C( e) Q             q=vexTable[tmp].firstarc;8 q' c8 Q' O% W: \  |
            int t=tmp;  d2 Q# p! @; s* H" M, [8 Z
            while(q&&tag[tmp]!=0)
) y3 U4 ]* ~+ @             {
" v" h9 i+ p* J7 ~                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
+ M# F" V" U2 ?                   //cout<<" 2nd    tmp="<<tmp<<endl;
, Q5 I1 q2 `# X! S  ?9 a8 K, t                   q=NextArc(t,q);
0 M$ ~( S/ M1 A* x0 s) b$ |' J             }
; i( t$ K% O6 D/ I) P" {( C) t             if(tag[tmp]==0), ^+ g% I/ l, D' l
                  s.push(t);' W, C% j% A8 b$ r6 W- n
            ///1、对应上面连通分支只有1个点的情况
7 e2 j  U1 Z( b) ?6 N+ j             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
: ?" |6 j5 b- P1 K             ///tmp要么等于找到的第一个未访问节点，
! S' {! d. X6 s5 \             ///要么等于与t相连最后一个点（已被访问过）
& o! D: t0 Y8 q, R+ N5 f* R             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点' M& `7 B0 C; ~" d
         }
' b: n1 o6 q; k) _# T: p       }* d: ]+ x; G( S( Z, I4 `
}
) `6 \+ `. `6 L4 ]/ H8 @# Y}) i. x$ R9 z% D$ c/ g% z
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-19 }. o+ X1 ]2 t4 @1 N5 j
template<class ElemType, class WeightType> int+ w2 R% d9 K2 y& N
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)% A+ Z' Z1 P# K2 Z7 |' I  f
{
6 e( K% }7 J7 G0 ~6 M. Y  S- q" g if(head==pre)+ b4 u/ e- n; c8 s4 F
      return -1;
* M$ F7 i0 D, E* o" P8 F6 J1 c
$ J# y% ^7 W3 C. E6 k MultiAdjListNetworkArc<WeightType> *p;
& W  A! I& w. T! ^9 p6 v p=vexTable[head].firstarc;% n1 }/ P: D- \
if(pre==-1&&p!=NULL). v( @1 }3 f4 `( _
      return p->adjVex1==head?p->adjVex2:p->adjVex1;1 j7 E5 ^+ b& ?% o5 O  D5 x0 P
//pre!=-1&&p!=NULL3 J# Q% i4 b: Y. K0 I
while(p!=NULL)& I$ Y2 l" v, y. s8 w  f
{3 q* B' _& a5 w1 o5 r4 r
      if(p->adjVex1==head && p->adjVex2!=pre)
& W. A9 [3 z) q! p. u* w9 r          p=p->nextarc1;
' q8 A& q- Z0 S: O; ]  d1 s* |       else if(p->adjVex2==head && p->adjVex1!=pre)
7 C9 {7 @- r8 Z          p=p->nextarc2;* i  v8 e! t/ A6 v
      else if(p->adjVex1==head && p->adjVex2==pre)  [* V2 e. |1 l8 w+ R- q6 d* Z
      {
3 p/ \6 G$ ~; K& u: i          p=p->nextarc1;
, m2 `1 b; r8 l( d          break;
, i8 q8 \5 V3 M& B. }# t) S5 ?       }# z) M: e2 I5 l  n# Y) e+ \
      else if(p->adjVex2==head && p->adjVex1==pre)
- N' K( I, d& N0 v8 W% |: j: @       {
" Q0 w+ P; W4 \7 Y          p=p->nextarc2;( |9 A6 L/ L1 C+ \, X% ~
         break;
+ b$ S: B; ?' W# Y/ ^0 A, @* b0 h       }
9 k* v5 c( G$ p+ s" E: b: [3 v }5 w* V+ k; A8 Y$ _9 V( }
if(p!=NULL)- F+ m2 `# f: J* b
{! Y7 T+ F2 q. J
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
( Z- p, T9 a' } }) z6 l1 \: g9 e8 J) M
else. l+ i( P1 c& `+ \& ]0 b& D1 y
      return -1;8 @( Q# J1 ~8 i2 v/ _% [7 w1 }
}
; \% L, d5 t, ]/ h  A
) o* A) X* ]1 W( d+ p0 o1 l1 x8 {: e
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()/ \8 F! w- {. e, K  n
{
0 s; ]$ j. }  G* c9 P% U stack<int> s;
. x* S+ D. \: X int p,cur,pre;4 C: @3 r3 A0 y& ^5 ]4 ]5 }8 l
//MultiAdjListNetworkArc<WeightType> *p,*q;2 F( i! ]( d  x5 w$ \5 M! ?
for(int i=0; i<vexNum; i++) tag=0;//初始化9 e  g9 L6 J8 S6 C  T+ a" y

( A0 }+ E+ x2 s1 F$ e/ Q for(int i=0; i<vexNum; i++)3 |6 ?0 ~5 d1 _2 ]( }8 z5 E
{, O0 G5 Z7 z0 {* s2 {5 m0 K
      cur=i;pre=-1;
- ~7 B% M" Q, ^3 D% h       while(tag[cur]==0||!s.empty())
% u5 E, r; J9 W8 N       {
+ Y- i- N5 s& r- Z9 P1 p0 M% y          while(tag[cur]==0)
9 e  ~$ X2 d. P; g  r          {
+ m6 E8 A  s" D7 ~# L4 v1 _' j             cout<<vexTable[cur].data<<"  ";
! V9 s5 |+ `- M9 m             s.push(cur);1 A$ f# b" F: `9 h- I
            tag[cur]=1;
- U! ~6 C; g2 _5 a5 k  v             //初次访问，标记入栈2 c& u. M" @! s5 s8 S5 l- ~

, f: E5 Q8 ^& r             p=GetAdjVex(cur,pre);//p是cur的连通顶点
. }! d# C& F" ?1 G             if(p==-1)
. w. T! |- D' d. `+ ]- O! e             {
9 d2 k4 F9 F" k* ^+ f3 H                pre=cur;s.pop();
- l" ]# k' g2 O/ t" \* Z                break;
! k4 I4 C  F- [5 B             }
/ R3 ^; c, I# S$ U1 D% N1 M3 e% H             else
1 k% X% n* J0 Y! `! }6 ~             {. o# e: U# O6 ~$ i
               pre=cur;
! M1 P0 B0 y3 T6 d                cur=p;& \3 g) A4 D8 A
            }
' Y/ C. K+ B; \4 L8 n% ?! y
* [. R! W5 z- X( Q$ C! Z. S+ X. @          }
. K) h1 G% A- e6 }: e  o          while(!s.empty())
# w  l, O" [8 O: {          {
1 I4 ~6 K5 m: H. ?0 c             cur=s.top();
) [  f3 |, u! G5 C; o             p=GetAdjVex(cur,pre);
1 n3 J/ @, s/ l) k- D9 g             if(tag[p]==0)# `5 J5 w% }- X2 s& _% L4 m
            {
$ X. j0 p& F6 w0 G: w: G7 C                   pre=cur;
. \# _2 ^. X# Z                   cur=p;& x) n+ x1 v0 t) q( C9 J) I6 A
                  break;
3 P0 Z5 ]  I% d) f- s  i. Q             }' Z* K; z8 q7 p% D
            else
7 n$ A% u7 R0 ]             {
0 J5 i: V0 P, U7 K* u/ \2 L                   pre=s.top();
! T+ E8 o3 [  i" J; r                   s.pop();7 l  K7 Y% W0 N8 N/ \5 S# r3 [
            }& n/ M4 l" X! Y, z7 i3 O  B" e
3 V3 C+ q7 H/ c
         }1 q3 M8 h' P! A  e* R  x4 B
0 h. p6 Z* s7 O* D( Z
      }
* ]6 p1 r$ |' d# p }
# Q* N/ B7 O' k& l5 z8 b}% W: E" {" K( ^3 k. M! ^( \$ k
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
- r( |2 f6 C' I' s{
7 E2 r4 {; P1 T# u. u6 `* z& [ for(int i=0; i<vexNum; i++)* v6 P  e: T# P& E! T
      tag=0;
( }. J# e5 d1 ]( C$ p queue<int> q;
% a* q. h0 I4 T7 C' p. e int tmp,t;
/ |+ ~" f: R) D6 J+ e/ n MultiAdjListNetworkArc<WeightType> *p;: w2 o+ x9 B- ~0 |* E! g
for(int i=0; i<vexNum; i++): T- n% K6 i2 D0 |* u
{
0 j( h& M, o' ~- E& K2 @) ?       if(tag==0)
& m2 E0 f, _2 e6 Z7 `       {
0 Q8 K+ B% b% A' {0 ^5 \2 I) c          tag=1;8 Y! f  j. Y0 n8 S2 K$ i
         q.push(i);
2 m7 r3 C: w, U$ f( j  S          cout<<setw(3)<<vexTable.data;
: c1 Z+ B$ P2 N4 g% P       }
' {9 U: b- l" z4 E       while(!q.empty())% y) @$ }8 V7 B: v& d' k
      {- Q( D+ N6 b) |+ s, N0 r9 ?) n2 |
         tmp=q.front();
  h/ G2 G. Z0 e7 |          q.pop();/ t7 {/ c2 |" y- }. ]4 {  r2 u5 b
         p=vexTable[tmp].firstarc;7 S- D. X* @3 d
         while(p!=NULL)1 G, c8 I2 b' M, h
         {
, h) ?' r. [8 B$ y) P3 D/ _- }             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);- x* v% y7 U3 n
            if(tag[t]==0)
* j- O7 ~6 ^- J0 ^5 U( ^# |- n             {
2 a6 t: L5 X3 ?% W                   cout<<setw(3)<<vexTable[t].data;4 m3 A' r# ^% f; ?
                  tag[t]=1;# a! m$ r9 S. P! v* U% X* Y1 O
                  q.push(t);6 Z6 ~" s0 k  @' o  R& e0 x: f
            }/ \- h, f5 {6 x0 ]9 S) B
            p=NextArc(tmp,p);
' u/ {* Z* P6 S7 y! r+ m2 @& x          }
1 w2 A: d- ^5 C7 `       }4 g3 ^# x: N$ z* Q; @  f5 c6 q0 ], F( v
}& w4 j+ g" B0 O" w/ N8 C$ U& c
}4 S9 o; S. H) ^8 W
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
' x6 _" m/ @% f/ {{+ m/ \# j' D0 [, ~2 B2 y" U& ]! T8 d
MultiAdjListNetworkArc<WeightType> *p;# Y2 Q. F; G0 w' p
cout << "无向图有" << vexNum << "个点，分别为:";
1 c. |; j' f0 m8 q: b, g for (int i = 0; i < vexNum; i++)3 j0 T) k+ S8 ]2 }! s
      cout << vexTable.data << " ";
. ^9 Q. k# {/ G1 { cout << endl;8 K. M+ M/ ^7 H; t' W
cout << "无向图有" << arcNum << "条边"<<endl;5 S# U9 H( @& v" L! F% C2 f6 g
for (int i = 0; i < vexNum; i++)
( _; d0 D/ g( l9 C/ L {
$ ], X' N( S" N" C/ L: K% c6 S       cout<<"和" << vexTable.data << "有关的边:";
! D0 B) D; h! G7 b6 c) i, }; g- [       p = vexTable.firstarc;; F1 V5 O% i, ~
      while (p != NULL)7 E' @% n0 z. i% \
      {, I+ Q6 X* X- I; R1 {
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
: |$ }- ?$ d1 T% N& W& g          p=NextArc(i,p);
9 M6 m' r* h6 `6 j, M; v/ ^9 Y4 b       }
- ?3 N' u; P0 C: i       cout << endl;0 `( F6 e; j& x2 F- Y; o/ c5 }
}
. V0 z( M* I& d' H+ e  v8 e}6 Q$ C, v- j# B* y. ]9 Y) o8 ]
- M' s- y- W* S# q* b6 v7 x* x3 g) F
' s" {: c4 V" z# f3 l9 D1 O
邻接多重表与邻接表的对比
& K( j! t9 I# o  \( P9 O  j) ^& e
) a4 V1 z" _" Y- y邻接表链接- v8 D5 [- E* Y0 K
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。& |1 t8 Q: M: K. k1 R( w
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
3 J) N5 O3 U' g" e为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。" |& {; R" o7 h. m/ F4 {9 _8 O
————————————————
$ q0 i+ v; V1 e8 W3 x8 p6 Y1 ?版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' n( D4 l, O' V" D* K原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
& s) [5 e+ s( x5 y& s4 i& D
/ T) b* l# O5 Y) n/ |' s( H4 a# ?* F' y6 P8 v

7 N! z( z5 [$ I% E0 _: X0 A
1 V9 [' {+ f2 f! b0 q, e& R————————————————
2 k+ O! p& M& E7 n# W版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。9 L- y( l: F! Y8 e# q: F
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958. }9 {; k" V$ B" d  X8 T# A2 s& J

  _" P! A( b  E6 T8 Q5 R, ?! u  t" O; a. x