查看: 1600|回复: 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 X Y, C+ P) @0 h; q
data域存储有关顶点的信息；7 @& P1 U3 L6 W9 C+ Q
firstarc域是链接指针，指向第一条依附于该顶点的边。6 `8 ^% H1 V$ R& H8 s2 z5 q' `
所有的顶点结点组成一个顺序表。

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;' l+ y5 K- A/ Z% u& O( W) u
for(int v=0; v<vexNum; v++)9 e, W  I( |. y. e) ^( A
{
6 f1 s& q3 W) W1 e       if(tag[v]==0): ]0 ]0 E0 P: }& p9 \! [( F
         DFS1(v);+ _0 n1 _4 o3 e! a4 t9 s2 J. c
}1 ?; M( M" z4 R  y7 c- X
}
/ X! t$ n' _3 T+ }template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()7 B% C2 Y; R* g0 _5 }, U+ i- z" n# e, g
{3 B" x. Z: j% c
stack<int> s;. _: q: N5 v/ O' x0 h& t
int tmp;
, `% `6 H7 C! b% c: P/ f MultiAdjListNetworkArc<WeightType> *p,*q;
- P& J" l: v& U1 V for(int i=0; i<vexNum; i++)
' @" W: D$ r- q5 f; G       tag=0;/ t. Y9 H+ {2 g+ F7 A6 o" ?0 x
for(int i=0; i<vexNum; i++)
6 I: E# d! r3 q: `1 s {4 ?* b0 Z$ o: t
      tmp=i;- a" C5 H* Q3 ~) T" ?0 M& B0 i
      while(tag[tmp]==0||!s.empty())3 ], F/ v. a0 t, {
      {% z* g+ P0 d; K# I! p5 e
         p=vexTable[tmp].firstarc;
, m4 [* c, x/ q, Y3 l          while(tag[tmp]==0)
: ]. _) e4 ]7 i$ G          {; L. r2 D3 r( t, A  _
            s.push(tmp);$ K' e8 N0 F; R2 X* k
            cout<<setw(3)<<vexTable[tmp].data;5 I/ |1 l$ G! C1 k- i8 G# g
            tag[tmp]=1;) X: C7 `' d* A  F4 `
            p=vexTable[tmp].firstarc;
6 u) R# M+ v- l  j0 g             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for) D1 J9 A" a5 P( h6 U3 ~: C: A
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
8 H/ h( a" p+ M             //cout<<" 1st    tmp="<<tmp<<endl;% d. V5 i4 P+ ~+ O, l8 \! D7 j
         }
+ v  E1 T; l3 H5 Z% o' \) a          if(!s.empty())
6 o. X/ ^3 |) t; t% p          {
, T, I# K# [! z             tmp=s.top();0 @& D$ U/ C! C0 U  Y: D: O8 ^
            s.pop();. l" J0 N& @" p) k: U; Q+ Z
            q=vexTable[tmp].firstarc;
* ~: B3 ?8 i5 E# B: ^' K0 M             int t=tmp;
- G- |6 Q3 g; p0 R4 G/ e; q9 \             while(q&&tag[tmp]!=0)2 j" b! e% ~6 b) _! L( ~/ Y" |! N
            {
* E2 N0 P0 A4 y- ~5 l9 v+ Q0 B+ w                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
+ A( X: Y4 g' r) W- C. F- u                   //cout<<" 2nd    tmp="<<tmp<<endl;4 P3 `- R6 R; W
                  q=NextArc(t,q);: E0 [- F" `  ?/ @! Z
            }
1 I# W. ~6 V/ O" R: [( v- B* \             if(tag[tmp]==0)
5 F! A- l. R; \8 W7 l1 o( @; t                   s.push(t);% a4 g0 S9 k1 C/ q2 @
            ///1、对应上面连通分支只有1个点的情况
. N; a. M! ~$ M+ E. z             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈4 I9 ]4 f' D2 ~* p+ A" p3 f
            ///tmp要么等于找到的第一个未访问节点，
; \4 m9 U* p0 d             ///要么等于与t相连最后一个点（已被访问过）
$ k* ?) _# k: ?2 e             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
9 w8 i1 g% {# \% ^/ K          }
; a  E# z% d' ]  g       }+ j$ r; e5 l3 _" _' W4 p4 U: s! Y3 Q
}  Y) ^2 {: u' |! @/ |3 Z7 J8 C
}/ W, ?/ F; B% @% P" H1 s
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
( Y; ?$ Q( Z3 ytemplate<class ElemType, class WeightType> int4 Y3 ^1 B# T$ o! ~" i
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
+ F5 d- I$ Q- w{$ j1 I7 i+ Y; q, p
if(head==pre)/ ^- J1 P* W7 i6 {% C2 H
      return -1;
5 [5 P- J6 k$ f  p8 n
) g. {/ m9 o; b. w# G1 z4 y# I2 P# b MultiAdjListNetworkArc<WeightType> *p;
7 }( d9 a  q% b1 [0 I; M2 e$ A p=vexTable[head].firstarc;
' t# r' f* e5 y; Z+ ^ if(pre==-1&&p!=NULL)
, `0 w* r, D# K2 [" V       return p->adjVex1==head?p->adjVex2:p->adjVex1;$ l0 e% k, R5 N
//pre!=-1&&p!=NULL# I( a- H0 k" u  s& V8 f
while(p!=NULL)& {5 C& f, L3 |  L  t! C% ^# J* P
{
5 i  c- t& [8 k3 Z& |- k' y% n       if(p->adjVex1==head && p->adjVex2!=pre)
$ e/ K# o9 `' T1 s$ j          p=p->nextarc1;, P) ]6 j7 V) N
      else if(p->adjVex2==head && p->adjVex1!=pre)
" Z0 F7 w( o3 Q6 A. y% g: A          p=p->nextarc2;
! |! H6 m7 L4 H' m! o       else if(p->adjVex1==head && p->adjVex2==pre)- H2 w# R/ p( }
      {! E% a  v4 j6 f: l, R3 `7 A5 D5 z
         p=p->nextarc1;; ?1 M. B& R1 M3 n
         break;1 P: B% F1 z! v# e0 L
      }- |& @6 `  f4 @$ v- C$ N
      else if(p->adjVex2==head && p->adjVex1==pre)+ ^* e6 U4 t4 K6 Y( b
      {9 Y9 e, E' \2 d% l  v( w% q6 E* c
         p=p->nextarc2;
) p+ `) ^4 E7 z6 c: f2 I" x          break;
9 V6 ~1 _. ^; X/ x       }6 x0 |/ u% M$ S! q( B( X& T% A8 V
}
8 A. n* F  |6 b: b9 D if(p!=NULL)
7 F4 o6 F9 e7 A% ?9 F: z$ J: Z: J {0 h# o# m' c7 t: l, u. i* c9 A  m
      return p->adjVex1==head?p->adjVex2:p->adjVex1;* D" K+ w* E# V7 B" k& [" K1 }. [
}; T: _( p) {" y$ N! L
else
& U5 E; @/ c5 s& f6 V8 W) F- M       return -1;$ Z: z9 L: o( T6 f0 _' O
}
& M) C( K( y. `  B2 x/ s3 [/ D" ~  r
" C$ _0 [' I; s& z/ q7 f
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
2 x4 A( N, F; e6 `9 ^! _" \/ Y% W{" x" ?8 U. O& j4 {' D6 N9 N
stack<int> s;5 Q  e) ~  n! s
int p,cur,pre;5 x4 o7 Z( P' a0 S- }
//MultiAdjListNetworkArc<WeightType> *p,*q;
7 O" Z! y3 d. [ for(int i=0; i<vexNum; i++) tag=0;//初始化
; R( L7 Q8 ~- b8 V+ V0 C# p4 g  B3 `" ^6 ]( E
for(int i=0; i<vexNum; i++)! d" F% f3 d( J/ n# V- X( }+ N
{: D/ d# R  S' G  N5 X, d& R
      cur=i;pre=-1;
1 \7 j0 n! r7 e1 v, [, G7 J. [       while(tag[cur]==0||!s.empty())
2 a: Q5 a& [1 k5 [1 A  y5 n0 h: Y       {
1 h4 z5 @1 V: S3 W          while(tag[cur]==0)' S: f' `" ~$ _+ Y  o1 k
         {* m0 X- L/ b1 H& G7 \7 K( r4 f
            cout<<vexTable[cur].data<<"  ";
# b. `# G( ?$ m5 F% @' E2 g             s.push(cur);
; _/ q; G& {9 Q  w             tag[cur]=1;
4 v. ^% q) r* g' O             //初次访问，标记入栈$ N9 @  ^1 g6 h* Y4 z

0 D, c6 `0 d6 [2 c) U$ [, t             p=GetAdjVex(cur,pre);//p是cur的连通顶点
; @( A- G) q1 E" i3 c. [) }3 H             if(p==-1)
: J4 b' w0 N( P3 N( @6 d: a             {
$ J; j7 \# }6 `! b6 C; s                pre=cur;s.pop();
+ ^6 A7 F7 t' E& f& `, R# E                break;' s8 `- \# K4 m( H1 t( h) l2 |, j
            }3 O4 ]  H! }: V0 E$ N
            else# m6 [8 i5 d% l1 a7 ^
            {6 V4 N, T' C5 d# d
               pre=cur;" x# Q6 O  w3 X: T. i% J
               cur=p;
0 C3 r+ e0 |" |) k/ `4 X             }. H0 x. o3 ~. e4 A7 z; _+ l2 ^0 [
8 j; I. T. N; \( I% e5 Q$ R
         }
- Z* N* ^  P4 U4 N+ X          while(!s.empty())$ \+ n' x* o+ a' q/ I% u) ]
         {
, d5 p) m  T) G. W             cur=s.top();
  k6 y7 I6 j, @3 Q             p=GetAdjVex(cur,pre);
0 o9 m5 z: B4 A; i! U             if(tag[p]==0)
  o0 d  Y7 p: `8 ?* ~, a             {
7 u( F# i+ j! L' U: }$ t2 y                   pre=cur;" |7 D& y3 ?3 V! K# I4 K6 w  v
                  cur=p;# I" i) S7 |8 E7 Z
                  break;
- y7 T5 r' T: [2 u             }
) P* S7 y+ V, o+ W/ h/ M             else
$ t7 t( U; Q9 k9 _/ Q+ m             {/ c+ T: x/ r; u! H4 t9 R
                  pre=s.top();
) Q3 Q' ~% `: e* L5 ]* F                   s.pop();
- W2 V1 `/ @; |# v& M& w3 M% m; x             }9 C2 [6 D2 Y# N' U! O

8 r$ W3 o* W2 D! K          }" V$ E+ D/ f8 F& I% F
5 u% F1 C  ?1 v! ?3 H/ \( E
      }
( n3 `3 ]- H* k4 N, ~- p3 S5 r }
! M) Q- a% @! R}3 i% w8 E6 |2 a, v! Y4 [* q% ?2 B
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()* e5 U" f1 {4 a% [4 m$ m* h
{- n  c. [  s4 o0 v) I3 v4 i. `
for(int i=0; i<vexNum; i++)
, W# t8 p2 _5 O       tag=0;- v0 F, `7 R7 m) O
queue<int> q;5 N- S+ s! Y. L- D7 l) r; [7 K6 p7 n
int tmp,t;! }% B, @0 x$ {! G
MultiAdjListNetworkArc<WeightType> *p;9 b% U. `6 C% @% j+ A1 Z& H8 L% N
for(int i=0; i<vexNum; i++)/ o0 K7 Z) b8 \( c
{) u4 Z6 L/ ~3 `  n; r
      if(tag==0)
0 ]- K. S4 k4 S* N+ }, N       {3 e' m& P* }4 W; l9 k
         tag=1;' l1 K- M, w& x1 i# L" E/ J) L
         q.push(i);% c# @2 V! W0 U9 r! I/ _5 Q
         cout<<setw(3)<<vexTable.data;  n' c: W: E9 F( j9 Q  R5 [
      }) }& a# R3 N/ m2 H/ V  V
      while(!q.empty())" \' h/ d0 j( M' ]: U' \7 j/ d" J
      {+ t" X! j% V0 ?5 \# q5 o
         tmp=q.front();$ d9 W- f1 E" q9 _4 J
         q.pop();
/ y0 ?8 V, H2 S7 ?/ n, {; e          p=vexTable[tmp].firstarc;; q* [2 y" I# w/ ~7 ^
         while(p!=NULL)
# p: ~% }, {- t# p. A: @( {  g          {/ E8 O! {! \9 D0 m1 n! v
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);% i) o* U5 I$ O1 G5 h( S
            if(tag[t]==0)  o+ Y7 \/ i  d$ [/ u
            {
, X9 K2 p/ O; J: H                   cout<<setw(3)<<vexTable[t].data;
- q+ }8 H- u0 u                   tag[t]=1;% K& `6 K1 a9 {8 w4 |3 i; a
                  q.push(t);
$ f. `- B% v' ^0 ^# i+ D2 L1 W' O             }
" E8 F& A5 W. {+ }7 T9 R$ j  J             p=NextArc(tmp,p);9 G" R* ]8 }/ y" a  j2 c& j
         }  y+ j6 M) B/ z0 ]7 J
      }
; i! O; O9 x' d' ~% T }9 c* j1 h! {% R
}
2 y9 Q# D6 J8 h$ }- Y% L) D7 o. mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
: z6 E. {2 d) z3 v{! b; @+ J( [; Q# `/ |% o
MultiAdjListNetworkArc<WeightType> *p;
1 I7 v  U! H4 M cout << "无向图有" << vexNum << "个点，分别为:";$ o+ n5 W9 _" G2 C" [
for (int i = 0; i < vexNum; i++)
" O8 v; K9 v1 N1 W2 _       cout << vexTable.data << " ";
- a! l* d& [* R+ L9 ?4 X! r: v. ~4 W cout << endl;9 \0 {  e9 q7 i: H
cout << "无向图有" << arcNum << "条边"<<endl;$ Y3 {/ j. z* i2 @9 e( m
for (int i = 0; i < vexNum; i++)6 J$ q% d! k8 z) Q0 o0 m
{- \( k! p' p" H$ _
      cout<<"和" << vexTable.data << "有关的边:";
  O: {3 ?! `; ?8 h/ A' N       p = vexTable.firstarc;
  n! X4 u0 l( Q6 D7 q       while (p != NULL)
) ?5 a6 M+ w* j" a! b, t* ?       {2 ~! S& l. R6 x$ j
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
7 ?# l9 _3 Q9 q# u( q          p=NextArc(i,p);
7 n  Q% y  s# e/ F3 ]7 G       }8 a3 T, _" v$ q' s  ^
      cout << endl;
/ d; |% e) B& ?1 l }
2 V( F( t5 b) t8 N5 c}
2 r5 h7 z, x7 [2 F
/ j& z, p: k$ D3 [. r* o3 y9 X0 G1 I. t: M! V
邻接多重表与邻接表的对比
, `3 C. F9 `% a' L6 K7 M, p0 M$ j
邻接表链接+ r& @2 R9 Z* C& G: d
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。( T4 G. |- j8 j: Q- _: u) ^
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
0 e& Q3 K0 e' A/ j+ {* L( H- Q为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
1 ^, i1 n5 ?/ J/ u% o' @————————————————
& L* _7 U  n  r版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, U: j2 M, ?9 C. x8 G1 J- J) n原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
# U+ v' E: W  X7 V6 G
, N/ V: }- g7 Z4 X
  {( w3 S4 ^5 Z& ^0 g3 X/ r! I! E; C# H/ Z' T. T
" T. g6 i; q) d- |1 }
————————————————
! ^- |0 L* I' Y" \+ S# L版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. m/ x( ]4 z. d原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958- M" a3 D, ~# q% ?* H. U- P1 b! R
4 k1 m* M/ y/ o8 |, L; V# C

% u  X  F% i! M