查看: 1566|回复: 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 d9 L# x9 l& C( d& ^" Hdata域存储有关顶点的信息；
; q( Z8 I1 } @, ? L# ~firstarc域是链接指针，指向第一条依附于该顶点的边。
9 g; Y! C# s4 l" ~所有的顶点结点组成一个顺序表。

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;
7 b/ b1 V3 O/ S' z8 x2 @ for(int v=0; v<vexNum; v++)
4 E: d7 r5 @5 }; J! Q! B {
) ]8 V; ~2 g6 p$ D$ Y2 P       if(tag[v]==0)
( i& L: M4 t4 t8 _          DFS1(v);' P6 V/ y7 i( {/ ]
}
; n# R& G/ `1 M* t, R: X}
% _, r; m  o5 h# n; p5 V: L; stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
, P5 J+ [' V1 Q1 }6 f. j2 O{
  F$ `5 C0 L/ A stack<int> s;
3 m" p. y5 c2 P int tmp;
' i$ R, S0 l1 H$ \: Y9 _ MultiAdjListNetworkArc<WeightType> *p,*q;/ y# j% U4 i5 ?5 c3 I3 v! k! W
for(int i=0; i<vexNum; i++)
: X& f5 h2 z" w: w" \) J       tag=0;/ o- \! P; U: d6 V4 t9 d3 R1 w2 u
for(int i=0; i<vexNum; i++)" `; Q: t  ?! K, w9 E8 f- i
{
4 K) Q2 d4 a$ T% w/ z2 ^       tmp=i;; d0 c+ t- m9 k7 Y- J: P
      while(tag[tmp]==0||!s.empty())* v- n4 i. D) R& o! j% e0 N
      {
& T  C8 I) G3 T  ~3 [          p=vexTable[tmp].firstarc;
" O/ a% G% y" b! O7 C. Y          while(tag[tmp]==0)6 }2 I9 m2 e# ]8 f
         {  c% Y. I4 }% W' y" }
            s.push(tmp);
5 Q0 r( u1 P* D* l) T: X( C             cout<<setw(3)<<vexTable[tmp].data;
5 u- B" A2 |/ |# ^- v5 F             tag[tmp]=1;+ w9 x' `. K* }; \6 u- {
            p=vexTable[tmp].firstarc;
; }8 ~1 E4 `2 K* M' {& R             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for# }" [, r6 ^- i) r# W" h
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 _1 k4 m  H4 P& X2 q9 }& t             //cout<<" 1st    tmp="<<tmp<<endl;
) \3 Y1 x/ m0 o* x. v          }
' T9 m8 W. a/ s: L; ]1 `          if(!s.empty())
! ?/ A6 }% C6 m4 U# s          {
. `: H" n% A  C$ ^. t7 v7 R* Z             tmp=s.top();
! @& ~+ e  {+ |9 c             s.pop();7 }  _8 A3 H) k- u9 t
            q=vexTable[tmp].firstarc;1 d! W% d- T5 b' ?* A
            int t=tmp;" y& K) V1 Z9 k4 D
            while(q&&tag[tmp]!=0)
$ m% z8 ^' |% }% U& H* S$ R             {
) x7 C( A6 ^3 N  h                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
3 T! j8 s. q) n  a1 @+ N  l                   //cout<<" 2nd    tmp="<<tmp<<endl;- Y1 s4 i& x% T0 |1 X# C$ _' u
                  q=NextArc(t,q);
  p; k$ ?4 _1 L5 _             }
* R* y) }7 R8 ]. `             if(tag[tmp]==0)
" u6 T! K  w% a                   s.push(t);# {- u' k# J( P: v) d
            ///1、对应上面连通分支只有1个点的情况
; |) Z# _$ ]/ T' M& \' B& A* {" O' E; H             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
3 |2 [7 _& S: [' u! C             ///tmp要么等于找到的第一个未访问节点，
* N* T6 O4 q1 F4 A1 \1 T, Y, |' v' s             ///要么等于与t相连最后一个点（已被访问过）: z: ]' S) W7 I
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
' @. \& O" u, p+ a* o9 L          }% N, Z8 U2 d, Z1 l* ~6 b
      }
( h# W2 j7 F6 p% c% X# S }
/ N, J, ^+ M3 {0 F6 [}
( ]" o6 f- a* k2 {. J; s//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
* x. Y" y8 V: e" @3 R8 Mtemplate<class ElemType, class WeightType> int7 }0 ]6 r) x7 ]3 n" O# m" ]
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
  q5 c7 h7 C6 }$ b2 h{
% m& C, W% g& D  D+ ^* Y if(head==pre)
1 @- x+ Q+ h, _0 R' p       return -1;
, [( C2 A5 V  \/ d
0 t4 @- Z# w1 o4 U MultiAdjListNetworkArc<WeightType> *p;
/ z( y) _; e. k6 X+ ]7 J p=vexTable[head].firstarc;7 S9 o; d1 J" j7 G9 |% y9 O, o1 a
if(pre==-1&&p!=NULL)6 m) c# z5 e8 A
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
* t1 n# }, |# e' H7 f: ~0 D$ F5 b4 L //pre!=-1&&p!=NULL& j: v8 n7 n. H1 R$ r) _" I
while(p!=NULL)
" l3 ~. A. Q( l. X6 g {
0 [4 k" ~' Z5 r3 s& K) n# F) H       if(p->adjVex1==head && p->adjVex2!=pre)
1 i2 W. N0 |4 n7 Q1 u          p=p->nextarc1;
- j$ ]" ?4 Q0 @. N5 \/ L8 P       else if(p->adjVex2==head && p->adjVex1!=pre)
) {! |0 i1 i, a' ~8 P% s          p=p->nextarc2;
. i+ O( a2 X. r# I       else if(p->adjVex1==head && p->adjVex2==pre)
( o% p9 `: q. c& W+ ^4 y       {# w/ U* G/ q; y! I( }
         p=p->nextarc1;7 X' I3 |+ |$ e$ a
         break;
) D4 G" V2 u; L. w$ H8 |* c       }1 R5 a2 X- k. Z! a
      else if(p->adjVex2==head && p->adjVex1==pre)
0 W5 N% C+ Q6 N$ n9 w( d* v- B       {8 }, O; I+ c2 ]: L% f6 F/ E
         p=p->nextarc2;
/ x' y1 ^: I" w( }          break;3 e, [6 R4 R. ]( O
      }
4 D& J- q) V. y' _/ g }& b$ f) u6 G0 o% o: E/ N6 d# d
if(p!=NULL)4 H4 R4 O! ]( L% c% }$ A4 V9 H; o
{: H- x1 b- }2 P. N7 X
      return p->adjVex1==head?p->adjVex2:p->adjVex1;0 M- A/ H; ~) b- U# a* w
}: w# U) V+ l* y, G- X' y
else" l9 g% s$ M2 j4 ?1 v
      return -1;
: @( o3 Z( ]; j}# d; I: g1 C; M- X& x
5 ?! q) P: M. r/ a+ g( Y
4 V; p7 R" ]$ r  Z- i5 K- a
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
, X- {0 q  w6 M. q7 W  i7 K{
3 S! _) K+ ^# t stack<int> s;
; q, C' U3 E4 a int p,cur,pre;
9 [: H( L9 x9 {% E- `3 B' ~ //MultiAdjListNetworkArc<WeightType> *p,*q;- U; x; \9 C& @" C+ ~' l5 P* }) J5 t
for(int i=0; i<vexNum; i++) tag=0;//初始化
/ h. c$ E0 v1 t: V4 l! @- t* Z% _6 W
for(int i=0; i<vexNum; i++)0 u: f4 P; n) _
{# b2 X7 v4 r, w$ @$ e, x
      cur=i;pre=-1;" S# _2 Z' [7 K5 S
      while(tag[cur]==0||!s.empty())4 q  F* r7 ^% w. P5 ?* c( \
      {3 x  x) L6 M8 ^& q- j
         while(tag[cur]==0)
, b3 j  m3 M! o0 J$ t2 A          {7 K0 n; H. e) }( p% \
            cout<<vexTable[cur].data<<"  ";# v3 i- v) q6 k7 `# ^
            s.push(cur);" k/ F! i+ j$ w: m& _
            tag[cur]=1;7 j9 ?. \! ?: I% V# s
            //初次访问，标记入栈
0 b; {" m, u5 ~- M: }1 `
' _# W/ e+ ]2 r2 I' r  z& I             p=GetAdjVex(cur,pre);//p是cur的连通顶点
$ h6 I6 ?2 H" @) Y- r- \% s+ O             if(p==-1)3 R& _2 n7 D+ A8 Y
            {
! a# v4 a3 s4 k$ ^; c1 [( t0 N                pre=cur;s.pop();- @$ r+ q4 }) Y4 w# h
               break;5 I- c# |; ]* O: {- ~- q8 n* |
            }" o8 D( c4 d8 r- b$ s
            else: z) ]) H; L1 w
            {
4 P/ N1 H: W: g# D" `& B                pre=cur;
3 e6 ~- K( ~% ]( r* I                cur=p;
( r7 U& g9 z: L5 t             }
9 ]& N$ d! n- v1 }9 ?2 {% U
1 a  u9 I2 G% Q( g& X1 U          }* B" o) Q6 t0 y: V
         while(!s.empty())' F- k- `1 S( J, Z/ R
         {$ ]4 T4 z; ]6 O' X3 N3 U# j
            cur=s.top();
& t3 g8 z' y4 ^, |' D5 W             p=GetAdjVex(cur,pre);
: f- d$ O9 s' F- f8 T             if(tag[p]==0)* i8 L1 }7 A8 o6 [, B) i4 v
            {
; v, D: r+ }+ ]) R                   pre=cur;
' x. D! H. D0 D  L! Z                   cur=p;1 ?5 \6 O5 j: t: m$ B& k, L
                  break;3 }0 p4 X3 p. m, R( l3 `% S
            }( X0 t# |2 N/ f
            else
& V, P2 y* ~4 H- a: X             {! C9 q$ ~+ ]0 ^2 h1 i/ F
                  pre=s.top();
6 l7 f2 a- I; v6 `$ {2 @  _                   s.pop();' L( t9 @( Z4 z
            }" f( \5 @. H5 Q+ T- w% V6 A1 d: K7 N

/ b/ T* e- D% b" ^8 D7 @0 b$ U- E          }
" S  Z' W8 W1 R9 e- U! k; W7 x
  l, n. s/ z9 Y; g7 p       }. [) ~. I7 g  Y6 i
}
/ k- o; G; O" m5 ~" v5 S}' n( w+ v0 v5 j+ }! D5 B
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()7 S' C: y5 |7 l  x8 m  x* h& S
{; W3 f% o( W+ I" V9 ]
for(int i=0; i<vexNum; i++)0 Y# m. @# @1 ]8 |
      tag=0;
$ }: q& d* A* ~: _  H# ^9 c; D queue<int> q;3 A; d9 x, p. J) z# F. v
int tmp,t;& ]$ ?, c( o# Y2 |0 C
MultiAdjListNetworkArc<WeightType> *p;- ^1 L0 \! N! t: A3 E/ c; y$ v" y
for(int i=0; i<vexNum; i++)
" M7 J1 @( C9 l" P3 ]' f; ]# ]% e {2 P5 T: c6 N2 I& ]. y
      if(tag==0)
: [9 |+ U+ C6 A+ ?6 A/ e% ~       {
! [- e$ V% S: v8 R7 H- a% P          tag=1;
  |: J# [2 o0 j6 I. B          q.push(i);6 t, k+ F1 c& g0 K. g0 ~
         cout<<setw(3)<<vexTable.data;
6 u, o0 D5 j; x  j9 M. `+ |       }
$ |1 }& A. ^( b3 Y" `; \* C- ?       while(!q.empty())1 |+ O; w; r3 z/ `5 l
      {
7 \" u% L( U5 y+ i+ M# c/ n; K          tmp=q.front();
/ ~3 l* P# _! `: R: [9 H          q.pop();
( O- D4 J, A  z          p=vexTable[tmp].firstarc;
+ U, G. [! G% d          while(p!=NULL)2 I1 i1 b* A  S! s
         {
+ p% y6 ^) a9 E* N+ W             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);& u: h; T) }! B& C1 ]+ E7 |2 K
            if(tag[t]==0)
0 A% j5 Z. Q; H' [- Q% O; M1 c             {
5 Z& H/ N( u- F" L" T& ~                   cout<<setw(3)<<vexTable[t].data;4 x$ z2 O+ w! M/ L1 ?0 ~* R" q6 s
                  tag[t]=1;  s3 R3 T! \1 h, C
                  q.push(t);8 _: Z* u" {( `$ s$ k
            }* f2 u: z' Q4 \; f- M% m/ O
            p=NextArc(tmp,p);
8 E5 U$ f$ }* }! @4 k1 {  Y          }
5 U( Q9 {% I: X       }
9 q' j+ o  M- e! x! D1 N }
& }7 Q/ W2 A5 U% ]; w1 c2 ?- C}" E4 _3 s! N: J
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()' Y; \& Z* y2 G2 |: m5 ^+ G$ g
{
0 Z$ O5 P3 U; \ MultiAdjListNetworkArc<WeightType> *p;( z' B2 ?0 y0 i7 ~- N7 c) u( J
cout << "无向图有" << vexNum << "个点，分别为:";
4 X/ C" k% M$ ^( k8 N for (int i = 0; i < vexNum; i++)
; R7 i+ \5 O' E7 n3 F4 d       cout << vexTable.data << " ";: Q1 Y5 r# Z" d: Y0 H
cout << endl;
! f, Z) u; r" P) U- A. D  `9 b$ ~ cout << "无向图有" << arcNum << "条边"<<endl;+ M4 c* k, Q, J
for (int i = 0; i < vexNum; i++)! M: O  `0 f' \7 O+ R
{4 s9 P: h% a$ ]1 X/ C
      cout<<"和" << vexTable.data << "有关的边:";
+ f1 ^: a6 a: L& y& K5 ~       p = vexTable.firstarc;4 X1 g  T& ~% C
      while (p != NULL). s, B; r* ~( h. }( o2 l
      {
: I1 X2 A  I" u  s; d          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";! N: O- r9 E% o  G
         p=NextArc(i,p);$ l4 `9 I. Q: j5 X2 ?9 N
      }
4 F! |* H1 ?9 {8 i: U& j( C       cout << endl;5 S: }6 l* _6 k7 j7 R% R. X4 [6 Y
}
* B; p4 [2 X* C4 x$ S0 C}
6 ^+ R  V. E0 c# U, E: B* t7 ?$ n
$ j: s/ H6 s/ Y& o2 V, V1 |. L- O- g( R$ z, ?; |
邻接多重表与邻接表的对比  @/ T9 [+ D6 t- r* o6 i

9 I+ ]; G8 f0 {5 @邻接表链接; Y3 B# o- `" C
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
9 p. H: e' V7 w& n1 v' i在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
# M& p+ N/ v7 y  i为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。# q3 ?( J% u; p
————————————————
1 M0 L) U- b' y4 C$ K* ^; L( ?$ u版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。0 z# i/ {! k5 V6 ]% K8 U1 C, x
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
# M+ c3 ^, o6 Y1 h6 u; h& W& b- w$ w
5 Y6 h6 v% r* g+ o# T2 j* G/ u/ Z

- e( e$ M9 ?& Z- ?* P2 ^' l% }2 j7 O. u; W
————————————————7 _5 |! r' s: }9 P: `  M0 ?3 f4 B
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
) y6 M8 }2 f( S# s8 Z原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
- R: k0 r& G3 D4 k+ k" S9 I1 V! s

/ [( x8 W9 X/ d# K: ^1 C