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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：+ d5 M& Q4 B. w4 q. Q
data域存储有关顶点的信息；5 t5 `+ J7 z. O6 F }$ \) c
firstarc域是链接指针，指向第一条依附于该顶点的边。 o% K& i$ y! J3 `) |
所有的顶点结点组成一个顺序表。

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;
! g: u2 ]+ C* _ for(int v=0; v<vexNum; v++)
- ~' M$ J2 j- a3 x3 f; i0 m7 X# W* ~4 p {
% e6 m! W0 r* Q       if(tag[v]==0)
, P! N" f/ r& h. W3 D+ p          DFS1(v);
% W( X* t* S; F% h' I& x }
  e3 z+ u% X$ d& b+ Z/ f3 ^}5 Y$ Z. X5 h3 N' X. Z6 \( t/ O: f4 z
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()* K- U5 e& i' e
{
' K, y, L5 M: g$ [% \0 a stack<int> s;
6 H# V# A8 L* e- g6 w int tmp;; C7 ?1 H4 m# g$ x3 [; S
MultiAdjListNetworkArc<WeightType> *p,*q;
* E6 e7 _( n" S6 h for(int i=0; i<vexNum; i++)- l1 x" g! D4 K8 d
      tag=0;
. j9 F0 V. F- I7 F& x6 I! o for(int i=0; i<vexNum; i++)" x' X5 q( @6 D+ X2 K& a7 s3 m! N
{
8 N3 k9 t" H7 h9 e; Y  `       tmp=i;2 ?7 I! n; x* o: j# g( B
      while(tag[tmp]==0||!s.empty())
) D4 J' r7 G0 I9 @3 i       {* R( j: S2 u2 O7 X
         p=vexTable[tmp].firstarc;
3 _) ]: v5 o  G5 ?, ~6 R          while(tag[tmp]==0)
6 g! X' [+ e9 V0 b8 J9 M9 k( x          {
5 L3 P  j: t  r% k% B0 ~             s.push(tmp);
( r$ d1 _0 P: F; l" i             cout<<setw(3)<<vexTable[tmp].data;
% H* Z9 A% Y4 i' Q" T             tag[tmp]=1;4 r/ `5 J" x* ^6 K0 o
            p=vexTable[tmp].firstarc;2 s0 a9 _! w0 o0 X" r3 H- N: ]
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
& A( z: C6 L6 H             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);' D- a) \% j, z
            //cout<<" 1st    tmp="<<tmp<<endl;- c+ Y! G/ F. r4 N3 m
         }1 [1 Y3 ^4 c" T3 q/ X, ?
         if(!s.empty())
* R/ w) L8 M  D          {
) X0 p9 W# ?. @. m& w             tmp=s.top();, C$ B$ d) M  s9 x* Z4 P
            s.pop();" ]* Y) H0 n+ }0 ]6 ]; j! a
            q=vexTable[tmp].firstarc;
! |9 q! o+ y" u+ L  a/ i             int t=tmp;
* T3 b, E; u" i. W7 y. T# W7 k( h             while(q&&tag[tmp]!=0)
5 |, ^9 ]: q1 J; x4 M             {, G6 q+ v+ U2 j# Z4 q5 u
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);9 h6 M) G) ^/ x3 e4 h2 H6 J. W
                  //cout<<" 2nd    tmp="<<tmp<<endl;! X8 `$ Z! M; T1 m1 v% _5 z& H
                  q=NextArc(t,q);3 S1 m' l, d$ e( Y
            }
" q, l6 _% e8 u. [1 _( w             if(tag[tmp]==0)
5 L" L" E& A0 y, X& z+ y* \                   s.push(t);) M4 d% f/ Z. J
            ///1、对应上面连通分支只有1个点的情况
+ K: i! Z% B; e" Z5 ]& w, X             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈; q4 [' D9 K* |8 J8 Y2 z
            ///tmp要么等于找到的第一个未访问节点，
! g" C, S9 }( l) v8 e0 e             ///要么等于与t相连最后一个点（已被访问过）- t- e! U- H. E
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
5 t4 m5 @: L" w* G4 g" U  A          }& }& ?0 j0 l$ f/ i) I
      }
/ }5 _3 u8 `4 _2 M. H' s! F }5 x/ t8 w' K# h. m
}' D8 b" U( w3 ?# P
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1  o4 T& ]8 i& }2 P. T& U$ ?
template<class ElemType, class WeightType> int# D" J( [! N; H9 P) `5 n) _
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)( e2 m& z0 B) x' ]9 D8 p  V$ @  o0 [9 M* @
{
, U# @5 M7 K- [ if(head==pre)
, l: V9 x0 c2 r0 R       return -1;/ _$ J  D6 y0 i* b% |- e- R" U

. Z$ u6 a: n- L; c" n5 n MultiAdjListNetworkArc<WeightType> *p;$ `/ v" B/ [# d# s$ t
p=vexTable[head].firstarc;
# y# R8 L5 X. ?$ R& p0 G if(pre==-1&&p!=NULL). ^) R' E8 m2 I/ V- o
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
1 g5 ]: u( R! A$ l* m //pre!=-1&&p!=NULL
1 \1 H" o% T4 E3 @ while(p!=NULL)' L( Y' k$ z- c# x6 Z1 b* }2 ^  M
{  U2 E; ^  J7 C/ D" L; o1 ~# g
      if(p->adjVex1==head && p->adjVex2!=pre)
5 ^6 H& v! V; E  k1 @4 R          p=p->nextarc1;: q# N: B3 k# r
      else if(p->adjVex2==head && p->adjVex1!=pre)9 l& r) n$ f0 Z! m
         p=p->nextarc2;6 X+ t& r" i, t3 t# r' q
      else if(p->adjVex1==head && p->adjVex2==pre)% ^$ r, S' g* ]0 u
      {
$ U# n/ E5 {' }$ S* [7 |3 c& d8 E          p=p->nextarc1;- S2 S/ q0 z0 U1 e) i3 y$ c0 _
         break;
2 A8 k6 d: K8 z% K       }
% Q' E' t' [$ H( t8 J1 N       else if(p->adjVex2==head && p->adjVex1==pre)
3 F4 c3 V4 F" y) k       {
% t) E8 J- f4 {8 z+ q1 i          p=p->nextarc2;% O0 d7 g8 I$ S) @6 J5 I( w% v
         break;
# E% O0 S% Q. Y" Y" ]; F% z  A( k       }9 K% v& n9 W* `9 k! ?( \' C
}( w: R6 _: E5 [, O
if(p!=NULL)/ o& ]' F; K7 {# Z2 q& _
{
. A& k- E2 H! {) i$ `, Q       return p->adjVex1==head?p->adjVex2:p->adjVex1;
  L7 _  F2 v$ P# |3 I }
* Y) U2 }7 h& I; z else- w: t, m& o& n. T; a/ s
      return -1;
* M- k  r6 T- s% E6 h: ]5 O# {# J}' [5 X( A. L9 V& J. `

7 F) k4 p4 n' [/ B. X% _8 V
8 z5 g7 H# P' ]$ J" O  b3 v! J% Rtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
. J- @1 p9 k7 x: m{
3 X# j  V: i& T7 T/ y$ L stack<int> s;' o9 X; `! K' F/ [0 ~
int p,cur,pre;6 }2 ?" E. u- z, e% Q
//MultiAdjListNetworkArc<WeightType> *p,*q;2 @' S! _& C. a& v$ G# \
for(int i=0; i<vexNum; i++) tag=0;//初始化3 g  ?$ S# f$ X
7 ^. U: |# o9 L, p7 `3 L7 s) G8 N7 ^
for(int i=0; i<vexNum; i++)
7 E& P" d  `$ Y& |8 H {
) y* j; r- Z% @# z' B  z$ q  j       cur=i;pre=-1;
$ [* j. O% I( l- P1 \1 J       while(tag[cur]==0||!s.empty())6 P- Y  w' F. f+ W* T+ G; H
      {  X  q8 S* Y" {1 ~9 j7 `  C
         while(tag[cur]==0)
* a) |1 P* N# s* ~7 z          {
; g9 X# E; F9 D5 w- S             cout<<vexTable[cur].data<<"  ";! F6 @) P1 f) [
            s.push(cur);5 v" k5 c7 i9 f% r- y
            tag[cur]=1;, x6 [% f' E- A: A: d: Y
            //初次访问，标记入栈5 `+ f/ |9 g; R6 [0 ^
8 R( g8 \2 `0 r$ u3 U4 z( n, _+ h- M
            p=GetAdjVex(cur,pre);//p是cur的连通顶点. x# Q" q2 A* G! a0 [
            if(p==-1)/ G' ^/ y' i0 \! Y
            {3 `4 Y% |& @" \" O" p
               pre=cur;s.pop();- D# ^/ ]$ p2 Y# G
               break;
( N" B$ Y: i( j6 i# G# [             }
5 H1 o2 J& W1 q1 c0 k             else
2 x% O6 o. m. j. N, Z9 B/ Q             {
  y  K1 P3 }- r- B- {1 |                pre=cur;
  ]& {- z6 U: |; Y                cur=p;* q5 \9 F0 E4 u( S& i+ w# I5 y
            }9 w5 X; W& P, P

0 K- [: D. A7 `. @2 a          }
  T5 n) J& @# X  J0 n) r/ p" X          while(!s.empty())
9 U1 s3 y( Y( \; W3 d, R; u          {8 [# d+ K! N% e
            cur=s.top();' M. C! P  l: J3 `
            p=GetAdjVex(cur,pre);* ~: a0 c" D9 Y5 h9 V+ r
            if(tag[p]==0)
- g0 P1 r5 M  [3 d             {
- C) k# g5 m# k; ]% l5 O' K                   pre=cur;$ N, Y+ G5 m; `$ g8 Q( I2 o( n% g
                  cur=p;2 f1 K& z4 {0 y8 j
                  break;
+ o7 d2 L$ L& m/ }) R1 r             }
; F: Q' a# b% M* R, j# B/ y* r$ ~0 r& b             else; B1 M% Z% W% A7 M
            {
; u+ D4 F1 L2 W                   pre=s.top();; ]) p. v! |" W! y( a  a: d/ t
                  s.pop();$ N" Q3 f  t4 y0 ]0 S1 P$ a
            }
5 R/ U  C/ {: v, s  t, e3 p! h0 A) }9 y  D5 F% B: S6 K
         }
' n$ v' D) m; R! Y3 b% k- {' X8 O1 a/ x6 ?/ N6 w
      }9 B+ M2 F5 u# s' X3 m
}! s1 }) S4 B2 S* y5 `+ P7 e
}
/ H; X, _9 ]/ G4 @/ p$ n' Y0 etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
2 z: ^" \2 a$ o; g2 ?$ ?{- y* P8 x6 ~8 a) K$ D
for(int i=0; i<vexNum; i++)5 l! S# ^' W6 Y
      tag=0;
: F; S: N; s) `5 l! H& l queue<int> q;7 u" M, Z* ^8 G0 Q/ e
int tmp,t;
/ _, L! I  `+ }" H9 B5 ?! A2 `; B$ | MultiAdjListNetworkArc<WeightType> *p;
& ?" J+ J' F5 ?6 \8 n for(int i=0; i<vexNum; i++)
& v7 V1 O# b$ M9 n {
, e) }. W8 M* Z6 H       if(tag==0)8 H$ _# ^% P7 C+ J+ `8 ^5 L& i8 a
      {
* W+ G' ^5 E& b, H  c          tag=1;0 t# [, G7 b  r/ ?
         q.push(i);; Z3 a! P( P9 U
         cout<<setw(3)<<vexTable.data;0 T5 u% u- P$ k* |
      }
2 y) M, k2 p  Y2 i, T% z       while(!q.empty())
* g& q: K2 q) ?. t) ~& E. W       {
2 ^9 J5 L6 w) r9 B8 {# b) ?          tmp=q.front();; }* e) s0 W3 l1 v5 W
         q.pop();/ G  g: p% z8 [
         p=vexTable[tmp].firstarc;1 O7 C: I5 Y, D: c! |) d
         while(p!=NULL)
3 t: @  p8 Y2 v+ I; T) A- R          {. p1 M. g$ L% i& L8 c
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);+ U/ g3 r$ L: v
            if(tag[t]==0)! }& K% R% L: k  h5 |
            {
1 C* @7 D0 K1 P- O2 A5 k  p                   cout<<setw(3)<<vexTable[t].data;
6 x/ c, k2 z6 o                   tag[t]=1;
* o; |- h, P3 n4 b) e$ q                   q.push(t);- {: y# H7 q# f0 A
            }% A3 U2 b8 S8 ?9 e$ j
            p=NextArc(tmp,p);6 M; }5 y  \' [2 n5 J: t
         }
$ t  @5 s& P4 Q" ^8 o7 H# g/ E# Q! ~       }
& g, n- B6 ~, V4 N }
" N9 d( G  B) f* q' s" f5 q- |}
  n% s" i! d/ s# Y6 u6 Otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()5 P2 f* T- p4 Y6 s+ u
{
1 @5 q9 w4 O8 [- f! I MultiAdjListNetworkArc<WeightType> *p;
) s# e4 C" K2 ~; x cout << "无向图有" << vexNum << "个点，分别为:";
) |" z+ c, e, G for (int i = 0; i < vexNum; i++)
! c. M; L* _" w" \5 A+ r  v8 |       cout << vexTable.data << " ";( x, ~& D0 j+ @  j4 d5 D: ?4 C
cout << endl;/ z: a1 p- s  _
cout << "无向图有" << arcNum << "条边"<<endl;
5 p- o9 h2 A: c7 K# b for (int i = 0; i < vexNum; i++)
+ \# c$ E" G2 E; x4 S {
. R# Z2 t0 L/ v% N6 j* c5 z! |+ L       cout<<"和" << vexTable.data << "有关的边:";0 E5 V- ?) K. z( y: P; w
      p = vexTable.firstarc;' x* O  I1 K+ A. A. `, T  q
      while (p != NULL)
. j, o% q- k+ g0 K% J9 q       {
$ }8 g& t9 [) a          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";  g: m4 g1 J' F# a" p' p
         p=NextArc(i,p);
; _$ k! A2 L- F3 Q; x* l9 p+ s9 x       }0 D! z" [+ U/ L9 A1 C
      cout << endl;
* n9 o- i  Q0 A }% q, _& b5 V, m% J& c+ `& d2 I
}% c; @& T5 O0 O$ Q8 I, T

+ n, G& N4 |1 |& q" W! f
" R# Y, b$ t. }9 E邻接多重表与邻接表的对比
' q7 A+ e$ I4 s9 g) O# i) K- T* Q3 ?; x4 U% S; [
邻接表链接
2 K4 l" V2 I* Q$ G7 A在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。* H( {3 R- g+ O% r& H
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
/ @' I: I  q. Y2 E9 K为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。" g! v3 l' u7 N! V  X3 f5 Y$ z
————————————————
8 L# U) s0 r6 i% Z1 J( ~版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。: E) i; }0 j" K1 d
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
: f$ j# T% E- a
$ @8 J4 d8 p! \* A" ~% p
* L6 e4 y% Q- D
" D" j5 R+ z$ p% ~& v! v9 q; u% _: x5 e# M% g8 f* d4 C
————————————————
& i6 m) ?% M$ I0 J版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。( N  R) E. T4 e4 s: a6 I
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
5 `# e# R0 B6 r+ k3 }! t* ]' t1 |) A+ W4 S4 f8 I

% ^2 F) E& }$ m4 g) k