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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
2 Z4 ^8 \4 Y8 U8 b. idata域存储有关顶点的信息；- @; G1 ?' c* _, G
firstarc域是链接指针，指向第一条依附于该顶点的边。8 [' v& H! f% k" ]; ~4 }
所有的顶点结点组成一个顺序表。

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;" x8 Z& }; a9 X
for(int v=0; v<vexNum; v++)
+ ^: [/ ^% e2 i9 o$ j, V {! s+ o! b9 [# C+ M7 s
      if(tag[v]==0)2 N# p* ?, U9 J' v/ r7 p- g
         DFS1(v);3 S/ x  \1 W7 q+ W8 J2 O9 X
}
9 E( u5 U, K( ~  n* O}
- ]! \3 F, D- X+ \2 Ktemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()! f6 }& i7 h0 O3 p3 F3 l
{7 u0 W/ [" u! |. M
stack<int> s;
$ ]( k. h  Z- V* J int tmp;) w/ i4 N! R8 p* C2 j: O  ?# x
MultiAdjListNetworkArc<WeightType> *p,*q;
, K# E' p; d7 z for(int i=0; i<vexNum; i++)* w, E) F( D$ F3 H, ~& S/ E
      tag=0;5 Y9 z: I2 z* X8 p: l! W, h
for(int i=0; i<vexNum; i++)0 Y) x- Z+ f1 {
{
. q1 ?6 s$ k( m, t3 H+ G4 B% A* q       tmp=i;. i% b. Y& j4 Z3 A. L" o; B
      while(tag[tmp]==0||!s.empty())- E9 c0 V8 I, g  T1 t3 q
      {
4 I0 ^1 u; v/ e; s4 a5 w4 x          p=vexTable[tmp].firstarc;& B. C: Y" c7 \
         while(tag[tmp]==0)* v" a7 V0 F: D, O
         {
& b, D: A- L9 ~- ^! ]- h             s.push(tmp);$ P5 p6 O, O: H: |4 X" g3 j& G6 _
            cout<<setw(3)<<vexTable[tmp].data;
1 l8 n7 x& T8 \, v2 ~0 i             tag[tmp]=1;$ Z$ T9 ~4 S4 Z% g+ j4 X# s, o
            p=vexTable[tmp].firstarc;
* f' U0 F" H2 C3 ^) e% U             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
! z% s/ z3 I) A0 b3 Z: `1 s             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);* |% m: S# J' P0 M0 F& J- u* b
            //cout<<" 1st    tmp="<<tmp<<endl;3 i8 Q1 M3 w2 M& N; M+ C1 z
         }
5 h- c. G- }( D' C# G          if(!s.empty())
6 J4 J; E6 z- M6 \          {+ Z) R4 s( s0 ~- g* N. _8 }
            tmp=s.top();" R, u) D5 n6 V
            s.pop();
% ?) X* b- \8 V; d5 m1 N0 E             q=vexTable[tmp].firstarc;/ ]2 ~% k; D1 t8 @3 N% F* @
            int t=tmp;
, K: _: Y$ @4 I, N0 |. P1 l             while(q&&tag[tmp]!=0), i  c& m) w1 P0 D1 {$ c
            {( v( N# L/ o6 W2 i% f
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);: h) I! J, ?0 h/ y6 @
                  //cout<<" 2nd    tmp="<<tmp<<endl;
2 F7 Z  f6 b" G# b                   q=NextArc(t,q);4 v9 I# a6 v% U; `8 E' p3 P' D
            }3 Y8 ^4 |1 L$ _* I0 u
            if(tag[tmp]==0)
. I4 L: ?, }( W! D6 Q. O2 N: l: H                   s.push(t);
% {, ?6 y( q3 n" b; o             ///1、对应上面连通分支只有1个点的情况2 E! H4 A- K0 K/ f
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈+ A$ [! X# T/ K
            ///tmp要么等于找到的第一个未访问节点，
/ x0 X: D! ]; V5 m% Y! e& d             ///要么等于与t相连最后一个点（已被访问过）
; M5 |5 P4 E$ C             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
( X- ~/ B* |7 R* P* {+ G- L          }
7 J6 z6 S. `$ {0 S       }& m& H& h! Z$ R% M7 T9 f! G
}0 V+ X, d( \: V1 g  }) o
}, K2 r0 L( l/ e2 f* y* P, A% B( Y$ z1 F
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1$ Y* I( H! [$ t# {% H  g
template<class ElemType, class WeightType> int
' `9 B6 B0 A' F( e' t! _" }3 k' rMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)% f& B, g  [, s2 q
{, n2 H5 n$ b1 n: ]. _7 E7 l) f- v
if(head==pre)
1 i" z' Q. X! `3 I0 Y" v       return -1;0 f6 |; z# m2 p; R" f" b
* D: M. ]* z# `3 P$ p
MultiAdjListNetworkArc<WeightType> *p;* _; q; `2 q/ h+ p
p=vexTable[head].firstarc;0 I) n: }+ X0 U/ P# \/ W
if(pre==-1&&p!=NULL)5 k8 J5 y5 e1 C/ s) S0 J, {
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
9 U( p" Q7 E1 B0 } //pre!=-1&&p!=NULL% I: M. N9 V1 e& C, S0 v9 C
while(p!=NULL)8 b- Q& o  P1 F) F+ T9 U. |; e% U
{' i1 R+ z/ h4 d0 I- t- v
      if(p->adjVex1==head && p->adjVex2!=pre)
: [% b( S) |0 D1 k! \- @          p=p->nextarc1;# o9 `) F% D/ U7 i6 l! A8 P
      else if(p->adjVex2==head && p->adjVex1!=pre)
8 W. m1 E* F& x0 V3 W          p=p->nextarc2;: ]8 c' l8 Z' k/ P8 X9 X
      else if(p->adjVex1==head && p->adjVex2==pre)
, ]/ N4 O$ `% t       {$ [3 j( {& }( t% u
         p=p->nextarc1;
5 n( h& D/ X9 ~! q+ d$ m- z          break;
: V" ~7 \% u/ O# K/ \  n       }
/ i& p% z0 N# h       else if(p->adjVex2==head && p->adjVex1==pre)
, @8 H. W$ T' v1 Q# ~- W; e6 w9 N       {
6 f# u. e& o" x1 [. r  n- U9 P          p=p->nextarc2;8 z* u+ y& _# p% X+ O, ]* U
         break;$ Y7 s, {# s0 h8 ~% c
      }4 L2 Q9 l8 h" _. y2 T# o# W
}
& u# i4 b1 }1 S: Y- g if(p!=NULL)
1 c) S7 ?. N0 O {' G& |# [! i/ M
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
4 Z/ ~$ l1 o$ p7 o) F }
- X: C% f& H5 I* l+ e* F else, {4 v, c" R; c* B$ S/ n( b
      return -1;
. {+ L* [4 y( F! Z1 m% g8 e}
4 C! }( I) K% r- O! ?6 R0 j; q) E% o
! I8 K' i5 `* Z% S
  \5 b2 |% }9 U/ b6 Jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3(): i9 K5 I4 ^' u& l# a
{: f. a! B' D0 e' Y: t% G7 n
stack<int> s;
/ T& {* C# K& Z5 n6 F int p,cur,pre;1 ^9 D+ d" E) {; [; S
//MultiAdjListNetworkArc<WeightType> *p,*q;
) d( g: P7 [+ l; H* e for(int i=0; i<vexNum; i++) tag=0;//初始化2 E# M- M/ i5 s$ ?( \5 I6 W  }
' D8 m7 _$ R2 @
for(int i=0; i<vexNum; i++)
3 _8 ]1 O7 T5 h/ a1 z$ I {
& J  C9 R/ G4 j. N( X0 b/ B$ `       cur=i;pre=-1;/ C% V  A. |, Q1 ?. D5 m
      while(tag[cur]==0||!s.empty())' @  h% s) R4 S* g5 g
      {/ X' M- N4 }+ d! ]$ o
         while(tag[cur]==0)1 \) x$ J8 B" q* g. V- f
         {2 `9 g; S. t6 ?5 O* H$ D6 l
            cout<<vexTable[cur].data<<"  ";
0 t# @+ J& L4 G) K8 I             s.push(cur);, p! I7 C4 {4 T' H
            tag[cur]=1;
4 ^  B. L8 z# Y. B! {  B3 ^+ [8 |             //初次访问，标记入栈
( `$ f6 {' K: ]$ V
. v2 W, X* M: M% C             p=GetAdjVex(cur,pre);//p是cur的连通顶点, l; f0 ~* w5 J) o* t0 d
            if(p==-1)9 V$ ^4 Z( n9 v
            {+ k5 A2 b) p: u. ]/ _# z& y  l5 r
               pre=cur;s.pop();7 T5 R1 R" M0 o# z9 l5 A4 ^4 |
               break;
* E7 l% z5 c. @             }' z( J" |0 y6 Q; ?. p' d) L
            else
5 s' m8 P* ~0 @9 `, S) s" V             {* [0 j, S3 g: D
               pre=cur;
/ h0 i0 b! @0 |/ C                cur=p;+ `* ~: I8 \8 E  l
            }, L* [- i8 z& K8 W
/ l) X$ ^& M, C8 T3 e
         }
6 E" z/ _& D* M2 ?          while(!s.empty())
9 z: k8 ^3 ?( n4 p! v          {
* D0 ?; X5 w1 R- r, P             cur=s.top();* ?8 t4 ~. z! f+ M
            p=GetAdjVex(cur,pre);
( W# c+ |( R1 l- h# b             if(tag[p]==0)
8 m+ k1 V3 m2 e- b" l$ `4 Y; u             {- |2 E; z9 s) ~. a2 ~
                  pre=cur;
) [* |  m& E: F- L# D                   cur=p;  D; g- _. d0 b. e8 V
                  break;# _! ^5 r; S5 t1 I+ ~- ]' ?
            }; _! j! s& _; ^) c' A" Z3 N- n
            else
, u  N. c2 n6 V; P% A8 R             {6 [0 Q2 i4 `6 _
                  pre=s.top();
) Z* S6 |+ x1 F+ A6 f4 W+ }+ s! r: Y                   s.pop();2 j! H  A1 @, r* l- N
            }
- l: l4 m3 D$ I  {6 z8 X  q; r( ?; a5 j/ V1 V. }# L" E: f
         }
3 ^' ?" z/ _5 q+ Z; A1 y4 x* l! {, D7 W% ^5 ]
      }" P1 n7 o! D. Z9 R- l3 \* c5 n
}
2 l# D+ o8 K' M" g6 v' V$ H; v}
# g5 p* y# O6 h5 ?+ Ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
& g" z# f5 S+ Y$ r7 y5 y{* T( i0 r/ l- ?/ @- |6 D# V* A
for(int i=0; i<vexNum; i++), q2 x1 B, C  _5 U4 w$ y. h* X
      tag=0;) I. e7 l, p* [
queue<int> q;
: c) v% w+ q( N4 ~ int tmp,t;
- e" B+ d/ m$ c" U' ~' E MultiAdjListNetworkArc<WeightType> *p;
" H3 K4 C- @( G4 p for(int i=0; i<vexNum; i++)
! U- [, w1 h. D" y {/ o& r3 {) T2 U% X$ \& j% z
      if(tag==0)
; I/ U5 J6 A$ c5 S$ W, [       {0 [5 i0 y! C& c; w, J
         tag=1;
' |8 b7 b% Z" g* L5 \* J          q.push(i);5 Q1 F0 e, M; T& o
         cout<<setw(3)<<vexTable.data;  h0 U5 s* c4 V: k
      }
& x! T# K( i3 R9 ?3 r) P8 @       while(!q.empty())! j4 D; g& h" ]" I% A  C2 X
      {( T! ^1 c. f+ d; O3 n4 ]8 z
         tmp=q.front();* G5 ~; M( }5 ~
         q.pop();* S5 ^6 _$ I& z  y9 l' q
         p=vexTable[tmp].firstarc;! c- y* R& @) w3 [! n5 n" y
         while(p!=NULL)
1 v2 `% B4 c* }5 M          {
6 h; l; H7 U: L5 v             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
; }1 B! I- q, L) }- S3 d             if(tag[t]==0); d! f* ^% T. p7 p+ ?
            {9 V3 S3 ~$ Q* A, o3 {2 k
                  cout<<setw(3)<<vexTable[t].data;$ y' R+ S; L+ h, N: i" S) t
                  tag[t]=1;0 x3 L1 Y$ m3 F# C7 f
                  q.push(t);: g, W5 Z0 U+ A; }) Y5 ?* Y
            }% c$ `# D" N4 w9 E  [+ ]+ d
            p=NextArc(tmp,p);1 x/ n/ N8 M: c
         }
6 e) x- k4 f6 D& r" o$ r       }
8 l. m1 |& E. i9 q9 k }
, K* o3 x$ @- m, f$ |* w0 Q}
$ ~' m! S) Z! ?" g- ?! ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
8 G6 ]4 J8 l: a& d{8 Y2 |$ B, C& y% E/ e+ k
MultiAdjListNetworkArc<WeightType> *p;+ I& v' ^* w" C8 H( x' _1 i
cout << "无向图有" << vexNum << "个点，分别为:";7 |, I8 c4 ?  P& ]3 P+ M
for (int i = 0; i < vexNum; i++)9 d- G1 f! ^" V* ^. y! F* e. h
      cout << vexTable.data << " ";/ `4 d  G+ ~$ y% U
cout << endl;
( P% I% T& X; W; t9 u' h3 J cout << "无向图有" << arcNum << "条边"<<endl;1 {7 `# u- ^0 [1 c0 h2 l
for (int i = 0; i < vexNum; i++)
. Y6 {' q( L$ j {
3 a! N% S7 I5 v7 i4 C       cout<<"和" << vexTable.data << "有关的边:";1 T& p: [7 ]% {, _" D0 R+ q5 O' t
      p = vexTable.firstarc;
! R" u& ^& ^; ~: g+ r7 J       while (p != NULL)
( q1 z" p' M8 r2 f$ c       {+ w8 A5 T+ X3 ]6 i7 w
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
, s2 |) d9 R! [. u+ W          p=NextArc(i,p);
1 `9 w! M: w$ g8 L5 y' k       }1 d" `! \7 G; c
      cout << endl;
$ B; b! e- N# p* z: ^8 B }
; B) H. ~& @1 K* p/ D+ T5 m' s" V}
" L1 K% {% u* B! D' Y
& Z/ `  w& x2 g
9 m1 ?$ Z1 U# T) i邻接多重表与邻接表的对比
2 p$ f0 a. E/ W" J+ V9 J  A" n: e7 L, E2 f  L; l4 I4 Z
邻接表链接- f/ t4 `5 X, W: i" X+ `) E
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。5 Q, o9 Q" V- A/ s5 d9 E% B
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
1 B# V9 V# W/ y" |( v2 A6 W为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
+ v! w! e/ C2 e: Z————————————————- q1 b7 Y' K( a- G
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。1 D& ]# w& E' x+ O3 b# y* {& t
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
1 L( u. Z6 I! B& V$ z% V( h4 Q
* M1 B) j& x6 k! X+ y! A" F0 m) e+ N' B* ?

* [4 h4 j8 B5 m4 e2 w' s; N: j; V
————————————————
. J6 g+ m& G% o; K版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; `8 l. H+ ]) u+ O. ^# M* {+ R; n+ W
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669586 G. ?) }4 m! S. W" J
; G$ b( h, W5 t; J  |7 r8 a
7 _/ F# y* P6 p9 x7 S" S. ^' |