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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
: f. c+ t0 i: W" T" Xdata域存储有关顶点的信息；8 }1 l O0 D# ?/ C1 p. c# b& t
firstarc域是链接指针，指向第一条依附于该顶点的边。
所有的顶点结点组成一个顺序表。

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;
3 x. m: ?$ E+ _. I' \ for(int v=0; v<vexNum; v++): i* D9 |* n0 O+ ^
{5 W0 L* Y9 b1 F0 |# F
      if(tag[v]==0); x8 Y# y  V! g( L
         DFS1(v);3 Q: |* M! @9 B- r! t; {
}
6 x1 N" g1 C% [5 b  n4 o}
2 w1 \& n4 t) T8 ]7 [# i+ {1 [template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()6 q. ]0 ?# R4 T; ~' }4 E% t
{: z, u6 X: A3 r
stack<int> s;
+ g8 G6 J0 _; ?; G% Y int tmp;+ P8 q! |3 G  D. V, v4 z% i
MultiAdjListNetworkArc<WeightType> *p,*q;- V6 T& k" s) w( ?" o
for(int i=0; i<vexNum; i++)
3 d; z# A3 v+ l       tag=0;
( f+ ~" {3 r. X2 l( w! X' d for(int i=0; i<vexNum; i++)
, I8 g# |0 w" Q: n& [$ ^ {- N$ O8 L6 f% N" b
      tmp=i;. i0 u% k3 \5 G
      while(tag[tmp]==0||!s.empty())
' x2 x0 G: `& c2 u, Q1 q7 V       {
  c9 B- x+ b. i  w" v+ X8 L          p=vexTable[tmp].firstarc;4 d0 k$ @9 a3 c# M  Z
         while(tag[tmp]==0)5 F% q1 B5 D/ N0 O6 g, S0 x
         {2 W; Z; k. U0 h7 w3 ]3 h
            s.push(tmp);4 Q- ]. z+ x; I4 k
            cout<<setw(3)<<vexTable[tmp].data;; p  A9 W) v9 \6 e+ {/ I0 [
            tag[tmp]=1;
1 a: @) a9 r. g' S9 B$ @             p=vexTable[tmp].firstarc;$ Y  @, t! K7 T6 V" F: g3 O+ o
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
9 T% p  |! j- z+ W/ z             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
$ z# g% [2 I' A( Q. [             //cout<<" 1st    tmp="<<tmp<<endl;
0 |* [2 a- a3 J/ `' R! w          }
/ O: I3 z) |4 e4 C* w5 ?3 ?, T4 u          if(!s.empty())4 q7 M' u  i6 M% T3 p
         {! t) K5 F, ?* x4 ]
            tmp=s.top();
1 h4 E/ E6 h; @' I             s.pop();
: u9 w# Q$ Z1 H7 z7 Y3 i9 D, N             q=vexTable[tmp].firstarc;6 U9 L- k: V; T$ Y  ?4 P
            int t=tmp;7 x$ ~. ~! H2 F5 T( v
            while(q&&tag[tmp]!=0)2 c5 {* f7 ~( \/ R$ o
            {
& \# U5 E; m# L) z- G# |                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);* j9 r" ?' |4 L$ ]# c2 i# x/ {
                  //cout<<" 2nd    tmp="<<tmp<<endl;
) B% @8 S& m$ i4 W                   q=NextArc(t,q);
/ O1 K- h# D# X- ~             }
$ r$ O( f% q7 C; }. w& r" W             if(tag[tmp]==0)6 Z8 Y! Y# e3 N0 r5 x6 D5 c+ Y; _
                  s.push(t);) ~2 y8 d. Z# I9 R# D" b# r
            ///1、对应上面连通分支只有1个点的情况
2 j* c5 o6 N$ s9 }: a: \             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
" J/ r8 a0 Z/ U; A- {/ ]. p             ///tmp要么等于找到的第一个未访问节点，
; G2 S* B' ?/ U2 K  @             ///要么等于与t相连最后一个点（已被访问过）$ q7 T5 D; ?" L# o, q" a8 [
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
0 V% j5 e7 k4 U: Z/ W& m; j          }# F3 m3 n( q+ _
      }
8 {( z- v, f/ E2 I5 {3 o& G" {. v }! E+ E2 [" D: H, l/ X- T# z" d2 o* M
}( q% W( l( S6 S  Q  }+ v
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
* K% e& f) P0 u2 ^4 ltemplate<class ElemType, class WeightType> int6 A% R3 C" i& B$ B$ b+ K7 z; }
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)# `4 t; ?9 {( ?5 J. Q1 Y' W% ^
{0 u$ k$ U: y- S* [% e
if(head==pre)' ^, y9 w1 A& D1 W; v
      return -1;
/ x9 q) u) c/ P0 e5 z8 q' |+ G2 b6 b4 \# ]
MultiAdjListNetworkArc<WeightType> *p;
7 z& H! X; [9 J' D! m( N/ [ p=vexTable[head].firstarc;) r( {1 f! ~( j8 o- _
if(pre==-1&&p!=NULL)
! T5 q9 \* M$ c) c6 N; r8 u6 B$ p       return p->adjVex1==head?p->adjVex2:p->adjVex1;
; H8 v1 m7 u1 ~) r- ? //pre!=-1&&p!=NULL
* k2 w- N, M3 B' O4 z+ C1 P while(p!=NULL)6 x, b5 V- f0 ~) ~( M
{! f; \3 i. Z5 d4 |  c5 W
      if(p->adjVex1==head && p->adjVex2!=pre)
* F% q0 H  n' s) ?          p=p->nextarc1;' W! i; q7 _& i. |+ [# E
      else if(p->adjVex2==head && p->adjVex1!=pre), l; x) @' V2 N3 r0 A2 l
         p=p->nextarc2;3 ~1 g. K$ n: j8 @  n* I8 P  j
      else if(p->adjVex1==head && p->adjVex2==pre)
( R) _4 N& o: U* ~" @       {
2 K, ?8 T3 V/ A3 V( M          p=p->nextarc1;" ~( d. J* j! }, l# }. b( b
         break;( }6 d3 U6 ]) [4 W% {0 ?
      }
/ |$ w- @. B4 M' }' j       else if(p->adjVex2==head && p->adjVex1==pre)
8 I  d6 d1 R. O: {# ~       {
5 E1 a$ o2 e7 G- t; @          p=p->nextarc2;
& k2 {  ]/ C% b2 g. [) X& Q          break;5 \9 t* |6 L( f" ^& n! j/ H
      }& C4 F% N) R1 R% h- P. Y7 B
}& o5 k5 N( p; N0 X* V% a" U
if(p!=NULL)  g+ S9 X$ U$ w3 ]5 ?. F/ X4 O
{
" t% O6 z" [8 v$ Y, j2 a7 Q! J       return p->adjVex1==head?p->adjVex2:p->adjVex1;
/ w+ N. F( M7 t }: c5 b  b% ^2 }8 _* k# m1 m3 i* r! O3 ?
else
9 F& G) _3 A- y( Y. A- I% q       return -1;
; ]8 _  y) h( t7 A( ^}, X. q4 j6 b4 _/ }
7 Q1 m* M# t9 ]: z

4 K* O  ]8 b6 G& w# J, U2 Htemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
- `( \8 d0 i1 W4 m{
$ \7 W2 l; O! B8 h& ]8 P! Y7 [; e' w stack<int> s;  M- m/ T7 Q) u4 v# ^9 x: W  [* R( k
int p,cur,pre;
; g+ c2 F& Q5 Q2 g7 Z6 y' M7 T& W //MultiAdjListNetworkArc<WeightType> *p,*q;
* e2 X; x2 [5 a' } for(int i=0; i<vexNum; i++) tag=0;//初始化% m, I! Z7 l1 k" R- b# C; e- ~; y
  g- V6 F: E. x2 ^* D! C
for(int i=0; i<vexNum; i++)
6 W+ i4 t3 E7 @5 E* h- A {' y5 ]1 N7 P- T% k3 u6 N0 I' s
      cur=i;pre=-1;7 O4 ^$ h# Q0 D
      while(tag[cur]==0||!s.empty())7 L- z" `& _: v  X
      {7 A0 S) h9 ?; u9 F/ G, H
         while(tag[cur]==0)
4 \% a" W  ]; D0 C' @          {
  X/ b/ L* N8 O% S0 g: f+ o             cout<<vexTable[cur].data<<"  ";
1 v1 l3 h4 O  H; ]8 E             s.push(cur);
4 |7 G( ~2 d, y             tag[cur]=1;
) |2 `/ z5 G3 V3 `* \# B' g) Y- S             //初次访问，标记入栈% K. x8 ]) [0 [5 E4 W" B- u& G
- ^2 ~$ W9 b3 Z, \1 T$ C% q, f
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
6 _! h2 @2 a6 K2 w+ k! C" k. b- U0 T             if(p==-1)4 Z7 m" O, W8 H6 |" ]2 j6 N
            {9 Y1 f- d* R+ a& ^5 V
               pre=cur;s.pop();
8 v- `. v) T6 E$ f+ y% M1 P  _' z                break;. ]5 ~3 v9 E2 }3 I1 `+ }
            }6 `. f* `, X# Z
            else
" p2 Y9 U, E3 \; W$ e( N; o' R  e             {
3 `! H- X" R' s4 `- `                pre=cur;, P' G3 Z2 e2 M, H7 n% b3 G, B7 {. ?6 r
               cur=p;
2 p6 M  s1 v: V( t& X* Y             }0 P# R: C2 R) ^) t+ @: y

/ j) M2 P$ b7 L7 P8 {2 w% l          }
, @. `, c1 v, I" L! }1 [          while(!s.empty())
' Q( I: P) Y! I- ^! n          {6 H# ?7 [, D9 Y! o' f0 R
            cur=s.top();% b1 n5 n+ F# u: ?: C* _( v# Z
            p=GetAdjVex(cur,pre);
1 G# y9 B2 `4 j7 U7 K             if(tag[p]==0)
! O0 p; z9 c! d/ G: b: V             {
/ F. Y8 b2 w' |! s% R                   pre=cur;
5 s# h; R- U* V2 O/ ?; w6 R; [                   cur=p;( p, c0 @+ ]  U/ h/ ]. @5 i
                  break;
& ~. j: a: _1 F$ I( E             }
' @* I* @! X5 o+ D3 z' u             else
6 X. t( z# H0 H$ W             {
( o3 J- T3 a. T0 a+ D                   pre=s.top();* u9 s; ]* l9 [* Y# @: P) z
                  s.pop();) Q  Q- p! g: `' J. _/ u
            }; ]6 U6 }' h  @/ L# \1 F; S1 G
5 X+ R  U2 L' h% w4 j9 H( O6 }& h
         }' y) {4 t8 f: u+ |4 Y, j
1 O* n/ ~) N  r  K
      }/ O, q6 d$ M+ u( E& G
}  T% S/ B2 w, ]# N6 q8 I" \
}
9 U3 P* o) o8 C9 ktemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()+ X1 x' @) f1 n, J
{) [: r% }+ z- E5 o: u
for(int i=0; i<vexNum; i++)* G. h& Y7 K2 z
      tag=0;
  Q4 F2 u7 M$ ]1 |- |  Y queue<int> q;
9 t* g/ k: l/ j6 G/ H int tmp,t;& s, }% ]5 f9 `& ^: z. ]/ U8 b
MultiAdjListNetworkArc<WeightType> *p;2 ~1 O/ V4 {3 l" T- @  P
for(int i=0; i<vexNum; i++)7 c+ k' U" e% Y, T; O7 s8 J  E! `
{* ?3 A7 s1 Q3 _' z% x, f
      if(tag==0)6 n3 N3 L1 D, L6 k' f4 ~
      {2 G8 Z0 [0 ]0 N( {
         tag=1;; O( d7 |+ i: k. @( ?) K
         q.push(i);
1 g8 ~& z/ n! s% h3 e          cout<<setw(3)<<vexTable.data;
5 y) y" O* ]( r+ ~       }
6 t% J  ~. R. y       while(!q.empty())% n2 c" p* p' R2 ^. u& o7 G
      {
7 |3 k! \8 {& C( u          tmp=q.front();
( X" r8 k* z4 s          q.pop();# l2 V8 u8 g( O. l/ n9 f5 m- e
         p=vexTable[tmp].firstarc;7 l7 D4 V  T2 [! [; r( `  x& `4 F
         while(p!=NULL)
- X! ?4 e) x0 ^- x' d          {6 p; n# [9 W' Y0 [: N( U
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
8 Y0 y  ?  E$ Q6 D% b0 s             if(tag[t]==0)4 b9 P% G; v1 p) [
            {. J5 r% U# i7 N
                  cout<<setw(3)<<vexTable[t].data;% T( c/ c; S. S% }, G+ r* ?( M
                  tag[t]=1;
8 W! S, P: `$ U  Z                   q.push(t);
2 E8 v& v1 C1 J* h5 i6 P7 R             }
7 b- u5 S2 H$ d2 F( _& f             p=NextArc(tmp,p);
: L( x% s0 i, W/ _4 R4 j          }
9 T& A2 i  x' _2 a0 l0 Z! m       }. ~5 t! G, _# Q7 C  Q7 i8 W
}
6 G+ A) S0 h, O# i0 p; {  ]}
, D0 i* ^& S; l" S; mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()0 l7 a: M7 O3 l1 V4 w: p4 U# ^
{: d; i5 ?# Y) [( N1 `) i
MultiAdjListNetworkArc<WeightType> *p;- [9 P+ Z2 F* Z
cout << "无向图有" << vexNum << "个点，分别为:";
- Z3 @: r6 c! E2 M for (int i = 0; i < vexNum; i++)7 p0 F/ O! G" b% t' _) a1 }
      cout << vexTable.data << " ";
; R/ D- @8 ?( V; s; S/ j) y cout << endl;
( y7 j- q+ R6 q/ U( b% B# x cout << "无向图有" << arcNum << "条边"<<endl;
& \5 z' b) }+ b, C: p# o for (int i = 0; i < vexNum; i++)
0 a9 J6 A7 X6 P; D1 ]; z' B; N {$ [) X! C% f& `7 Y7 R
      cout<<"和" << vexTable.data << "有关的边:";7 j) V, y) ^6 Q
      p = vexTable.firstarc;9 V; T1 G  u, v
      while (p != NULL)
5 f& g5 }4 `" y* ~# `+ U2 j+ H* s       {
2 u9 T# p  t9 W  P$ c          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
( T2 z/ C6 D' B; k5 y0 E          p=NextArc(i,p);
* j* k. ?7 @/ @* h- H, f       }0 g: t( T- A, \: I- k  j
      cout << endl;
! O3 n; s* m$ @; {4 }# e }! [5 Z8 ~; e# q/ [' S' F
}
+ O; k- }/ k* {; w  k
+ f* o9 Z$ Q( r7 B: V
2 z% z% d! ?' X- e( W- j7 L- l0 q邻接多重表与邻接表的对比
+ M: D. H6 K0 E/ Y8 R7 o5 G  I' Y# v  F4 @8 o% h4 n
邻接表链接( o" ^5 v1 k9 F. A3 m/ U
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
/ u0 w3 ~* ^- _5 M( r在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。1 R* N% [$ J4 s& W
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。2 B' F  Q  C" `; G5 o, w
————————————————7 C3 U) b9 w" n. I
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。) d, ^9 z+ e) j6 r0 _
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958. G# a# R! p. q, I2 ]$ P

/ p4 z3 [9 e4 H4 b: t6 O# }, K* f6 B7 J+ C8 H. B- m

% `$ U9 I- K) L) K( y5 W" V0 J: u0 Z+ n1 a0 i# K$ A
————————————————1 @0 {5 l$ R* m" K0 |8 e" o& b
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 P- W) K2 @4 F- ~$ M3 T原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
+ z! \5 v( x  @% l) ^" S! ]& D+ {9 Q  [2 x& Y( [# X) w0 v7 Y
1 V; A( \) x' j  z1 e