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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：0 O1 s* c; O$ Y0 L; ]/ \$ ]( {
data域存储有关顶点的信息；) z* a, R% p2 D% D
firstarc域是链接指针，指向第一条依附于该顶点的边。
, u* V2 _6 g# K* p4 V所有的顶点结点组成一个顺序表。

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;( y" g. a( L* o7 O1 V( k
for(int v=0; v<vexNum; v++)" g, S4 k: G$ m
{: `5 _$ K# @' S# a' V
      if(tag[v]==0)
( ]; _) |9 R. K7 j% |          DFS1(v);; m& U2 Y7 ]1 O/ s1 k. l( V2 r7 v$ x
}" ?2 `& L  b5 l( z8 O- X
}2 b' F6 k6 \& R, N5 h- H
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
* V  |8 y' H  A% M" q{3 J1 ]( n  N; W/ X( x8 R% N
stack<int> s;3 _) [1 R( s6 P+ G
int tmp;; X: u4 M1 q/ T- T) h/ `) `+ D( {# o
MultiAdjListNetworkArc<WeightType> *p,*q;+ _5 e# G+ t' K/ z: M/ l
for(int i=0; i<vexNum; i++)# t# @" P: M# Y2 E
      tag=0;0 _+ ]% h! K. F4 y" |7 g+ H
for(int i=0; i<vexNum; i++), I- t2 V9 S+ x8 T  Z5 k1 y8 P
{% p! g3 i. B) v
      tmp=i;0 a& \# b' E! h3 O4 {  t$ F) x6 O
      while(tag[tmp]==0||!s.empty())
( U0 `5 }1 y0 @: |$ g& a$ G       {
& g, V0 c8 s5 u$ g. s+ U          p=vexTable[tmp].firstarc;
7 H3 [0 |2 ]2 d8 v          while(tag[tmp]==0)
4 H0 h4 p( k# F4 R0 Q# c6 K" J$ Q6 E          {/ u& H" Z, [- m8 L: p: ~5 w" G/ ~- f
            s.push(tmp);
' j8 t$ {4 j! I& H$ `8 g8 J) {             cout<<setw(3)<<vexTable[tmp].data;8 a8 z: Z: E$ e0 n4 H+ x- ?
            tag[tmp]=1;
3 L0 e% s6 }0 [. u4 \1 v             p=vexTable[tmp].firstarc;
5 L! F! z# F% F9 l2 C% {0 x# ]             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
4 P% V" V% ^; ~' J* R# S: K) `             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
2 Z$ Z- w& K8 k, |+ s             //cout<<" 1st    tmp="<<tmp<<endl;- |' x4 y/ w, H
         }0 P( \: k6 H: R1 U" Z: ]
         if(!s.empty())
* Z" w; J! \' n4 c' N          {
( o  _' G+ {) S6 U+ Y& n/ [             tmp=s.top();) K* J. W2 s4 c% `7 l
            s.pop();0 N; R$ E/ N. i. j
            q=vexTable[tmp].firstarc;4 S% {$ W. W5 P/ A# P% m
            int t=tmp;
  K3 r% A& m# J! L0 e! h* s             while(q&&tag[tmp]!=0)0 }6 c) P5 H$ ]7 b8 g' [9 o- f% `
            {
- X( S" F! s* l3 L; [                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);- t: @9 l$ X$ a  ?' |& e4 f
                  //cout<<" 2nd    tmp="<<tmp<<endl;9 |& x! e. g" L2 X: [/ t
                  q=NextArc(t,q);8 t1 [6 k: Y0 `3 ^
            }( `  y: `2 g# L$ m8 z! a, Z4 O5 F4 g
            if(tag[tmp]==0)( H1 I$ ?' k7 F9 V5 x3 t
                  s.push(t);
3 $ H9 C0 u' J" e" H) k: S             ///1、对应上面连通分支只有1个点的情况
7 Y$ b% V2 Y3 c3 u, I1 `             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
- `! E0 w+ ^, \5 v             ///tmp要么等于找到的第一个未访问节点，0 L- L' t# X2 I: b- ^
            ///要么等于与t相连最后一个点（已被访问过）3 P; O4 y4 ^0 j# E& w/ n
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
, J" Z# v1 v% y: R          }3 i3 b9 _5 f, y+ }; Y
      }
1 ^: @: X( U! c! e }% ^) p4 {* m: c4 k
}! _0 I$ O# B# O7 {2 k0 e
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
: $ W6 W  q# |+ F: f) {1 jtemplate<class ElemType, class WeightType> int& U' @2 S' E  J" C- @6 U7 b
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
$ x$ y  k1 l& M3 s2 ?9 F; [, I{
2 U/ U" F: H( H if(head==pre)5 n4 f, s2 G% F3 a$ L3 b
      return -1;& e' [9 g7 P; H" U

6 A) |6 ]' C& w MultiAdjListNetworkArc<WeightType> *p;
/ z8 q" V8 i+ I" n: `- ^ p=vexTable[head].firstarc;, M8 F6 E$ ^; ]  [$ K6 J' J& N
if(pre==-1&&p!=NULL)
2 f& P: U, Z. C$ Z8 y       return p->adjVex1==head?p->adjVex2:p->adjVex1;
! z; j: M, d  x( w2 i! |/ v: V //pre!=-1&&p!=NULL! }/ s( W, C- C' \/ V! {
while(p!=NULL)! x8 A  T: c6 k! J2 x5 y$ C
{
. J9 ]! @- g  k: p5 o7 m5 ?2 q* J       if(p->adjVex1==head && p->adjVex2!=pre)
( v$ o9 m$ o$ t+ h# H0 {          p=p->nextarc1;
: o- u6 e* Y8 Y, R2 L       else if(p->adjVex2==head && p->adjVex1!=pre)
6 }. E( {) r3 Z& T5 T. h          p=p->nextarc2;3 J! z+ u9 l4 D1 n2 ^# o0 Z
      else if(p->adjVex1==head && p->adjVex2==pre)1 Q( Z: c- E$ n0 j
      {
; W  v- \  x5 x6 ^$ k          p=p->nextarc1;
! j/ S# N  m& F0 g# ?% J4 D7 U/ m          break;/ y5 B* |# ~, m% V/ H. L/ U
      }) I! G, p3 z% k+ v' Z3 O* P
      else if(p->adjVex2==head && p->adjVex1==pre)
9 t/ _& B: O& d# L5 A6 ]       {" p  z& c: U* a( a- l
         p=p->nextarc2;
  H/ q- p0 l1 w9 q          break;0 z  U0 a# @- D- ]- `6 z0 V
      }
# ~. v0 ]# X! q0 H/ K }5 W4 X" w8 z) O
if(p!=NULL). Z2 Y' y5 o3 r0 _
{
, B0 N, m; ]. I       return p->adjVex1==head?p->adjVex2:p->adjVex1;  R4 ]* R2 u, ^5 z
}$ o0 @1 S  p+ |/ m/ T8 l4 j
else) v* W( s2 m$ Z+ w5 l
      return -1;0 A: z8 D0 `, G7 a2 z9 q
}
5 A4 u8 l  b- L/ Z2 f; E4 K7 k2 O4 c7 S3 Z

0 r; e/ o) D* F, J! ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()5 Z# q( H3 z* i9 E
{8 K4 n2 n! k( C% ~
stack<int> s;
& \2 C8 T7 x8 n* j; p/ ~ int p,cur,pre;
$ s5 ]7 {; {& d$ u. n" C //MultiAdjListNetworkArc<WeightType> *p,*q;
5 [$ z/ q0 G6 T for(int i=0; i<vexNum; i++) tag=0;//初始化
/ L3 c, k3 i1 o6 @6 z, _' Y7 e9 Q0 y2 p  V
for(int i=0; i<vexNum; i++); g2 o: U, j8 d! m+ Q9 u9 q
{! o2 R- |% _' V0 x" P9 Q; d
      cur=i;pre=-1;
$ z$ k0 I" x, W! r" ^/ S       while(tag[cur]==0||!s.empty())5 `/ l: A8 J6 v
      {
; r0 g. }5 ]* O          while(tag[cur]==0)% _( S: |4 ^/ {, S5 p
         {
2 c) Y# [0 q( c, Q             cout<<vexTable[cur].data<<"  ";
! w2 F& q& N! W             s.push(cur);
6 T' o6 F5 d. |4 O& {             tag[cur]=1;
" |7 l, o3 }6 ?5 Q+ B             //初次访问，标记入栈, Y# A- z9 ~/ D0 C- G& |

8 ~% o% Y, `5 |6 v1 m3 g3 ~             p=GetAdjVex(cur,pre);//p是cur的连通顶点
( ]. R8 O6 _% x% O, K             if(p==-1)7 Z1 }/ O/ g2 O" e
            {
% l8 S* S* E2 G7 x* ~3 P                pre=cur;s.pop();
$ M5 {7 Z. y# R$ ]. R                break;
            }4 R( s4 [. i5 S: i4 d. N
            else2 o, X! l# ~5 \+ @
            {2 q$ V3 |6 Y- L3 ]7 w8 R) Y/ S3 M
               pre=cur;
% F: h+ T2 t1 ^( N5 L5 F' c  p                cur=p;" f+ d. T6 E* `& y0 |4 m9 Z
            }
  L) u' k9 f6 C# N; w
& l, s1 y, d9 \) B# c" f5 P6 ~          }* [5 t$ i( O5 o2 G( ^& {
         while(!s.empty())0 x. X2 Q% n, C/ Z
         {+ g& q" R  `" z3 _
            cur=s.top();% E- Z9 U  Z4 Y$ |+ p5 b
            p=GetAdjVex(cur,pre);
! w  E0 _6 A4 a+ ?2 d# o* D             if(tag[p]==0)
1 M1 H) }6 {( P& {             {; p/ a5 ?  y  D: z, Z/ x
                  pre=cur;
0 c: l. x' M! {6 D$ H+ H& l                   cur=p;* x; ^/ B; p0 l
                  break;
& v6 B( h6 g7 S) D1 X             }9 k+ D, \" Z% [, @8 ], q' `
            else
4 m4 B0 A  f9 D             {" D) ^0 m0 A7 j
                  pre=s.top();# ?2 i! w- Z9 I+ i8 k
                  s.pop();1 W  o( w/ S1 B  b- U
            }
3 [; S1 X  F, u8 w  `$ h& K! h
! z$ s, |( E5 F' V          }  S7 O4 M' q1 v" P2 v) }
7 s9 C, t) D5 }$ {: c
      }1 L0 R0 ^6 S. I1 n. y
}
/ C& b* a# g$ C4 r$ X}
7 T  O. u" B. }3 Stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()# K6 i7 |% Y5 Q7 q2 ?4 g
{' U3 w/ t9 f# b! k
for(int i=0; i<vexNum; i++)
" e4 h0 O& r' [" W; a  s. a       tag=0;
( \/ u% [* @8 a1 G- E queue<int> q;2 R: P8 s+ c1 ~* x
int tmp,t;
" O0 @) T5 @* C* b* O$ G4 \2 L8 P MultiAdjListNetworkArc<WeightType> *p;
" W! A5 }7 u# V0 T7 c+ j% {9 j1 e$ @ for(int i=0; i<vexNum; i++)
" \1 ^/ ]$ L. S, e2 S) ?4 o. Y! { {
/ P7 S' U, y, M' R       if(tag==0)
6 ?$ J! v. e) h& E$ n       {
9 m, H4 ^+ M: V3 F# b$ U          tag=1;/ G+ ]2 Q$ {$ a& a
         q.push(i);$ ~6 t/ n- d$ c$ F+ t
         cout<<setw(3)<<vexTable.data;  f: a* ]7 y) b8 _0 l6 y) C
      }/ w) l- k8 K" G& `' H
      while(!q.empty())
) m) z4 q# c# S       {  I% s. U! D- J2 A
         tmp=q.front();1 [# h) Z" I6 ?7 ^
         q.pop();1 C+ @: N. p& {  g* @
         p=vexTable[tmp].firstarc;* V3 f0 @6 }3 J0 e7 u3 C
         while(p!=NULL)
, O! D, D% |. x5 M5 Y& I          {
7 C+ \. c( Q/ r: y2 i             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);) U* K6 M( X8 A2 U, H
            if(tag[t]==0)6 w8 Q, X8 N6 G, _! t0 z
            {3 D. H% `! A% u4 B) ~. l/ f5 J
                  cout<<setw(3)<<vexTable[t].data;5 C) N% Q& M7 V  R
                  tag[t]=1;
: @+ J9 h# Q" b- w                   q.push(t);/ h3 j" R& H  ^- S8 u- c& U' p
            }
  x4 Q* q9 ~! `' v7 }$ |             p=NextArc(tmp,p);
% t% Y6 b# K/ u1 L1 m! X2 k          }2 F4 F$ P, _- m0 x
      }
) }) r% ]" r7 q" g, ~ }# |4 v; b" _2 `1 d; t
}
- K. y5 X  I* b) w& x& S3 A! L% p* stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
: U4 N2 b% Y- P$ `5 u4 Y3 q{( {' u: O4 k1 s+ D. i- K. v4 r% N1 Z
MultiAdjListNetworkArc<WeightType> *p;
: D6 @# o9 u! f& H cout << "无向图有" << vexNum << "个点，分别为:";6 |* ^) O- `) k
for (int i = 0; i < vexNum; i++); Z6 J% i/ K8 e6 p3 A( }
      cout << vexTable.data << " ";, M: H0 K2 x' B8 ]# E) ]1 h& l
cout << endl;7 B& B. A" c! v# O0 H7 V# w
cout << "无向图有" << arcNum << "条边"<<endl;1 b# i3 a. ]3 Z4 d- |5 l, V
for (int i = 0; i < vexNum; i++)
3 [! ?5 x. ?+ G! i: p" \ {
5 T& E1 R5 v2 |. \( k' h  p7 A, R       cout<<"和" << vexTable.data << "有关的边:";5 Q8 x: L% n$ s1 V+ S  s! R$ A
      p = vexTable.firstarc;
( @! I' H8 G) n: i$ R3 f4 A       while (p != NULL)
" B! w! I3 {- ]0 M+ n, S' R: J       {
. E' D/ H/ |+ h$ _- D          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";7 c' H. h" Z9 r- W
         p=NextArc(i,p);
6 j* W; _, }9 H- H0 g9 K       }
1 Q$ k* K. V/ k" B       cout << endl;1 F  G, o( f8 m* q! T; p& j7 o- ?
}
# B- s; a: u1 H7 P  v% @}
' A# N( d: a3 j9 g2 r& ?- j) z  ]& B$ t; ]. L# B

; C$ l& p$ @+ N. o2 Z8 p; B邻接多重表与邻接表的对比. C& e- F+ U4 v2 r

. ]1 N& \! S; j( C6 |5 l邻接表链接8 o+ }- C. ?, I  G7 q2 W7 F& M
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
) z% R0 ]$ @- n7 @在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。+ S/ {# [. r0 T! t$ D  C
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
1 o# z' N* B9 l9 C/ p& `————————————————
, r$ G& S) o7 _+ q5 p( q5 w. s: z版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。6 n* _8 ^% y6 ~5 o+ ?# G: e( {9 u
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958! s6 D5 g3 s# a: a1 Q$ l

3 ^' e; }" c  x7 U9 y3 A' Z8 J# s- H1 J7 T
7 K. }9 Q+ ~/ ~; Z/ l- H; U3 F

" k( Z1 ]" S+ P% ]————————————————  K& T- [3 R- o/ w$ I% u  D' x( B
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 R$ R' M, j/ b. O2 T原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
% G' R" j% }  q' w( v7 l5 }9 b4 e& q7 `' G. V, z) I; p4 p
& l, g4 C6 N& \8 M