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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
3 p" e' T6 L# B& O0 l; E" U0 Pdata域存储有关顶点的信息； P) R; c. U# v- W2 B
firstarc域是链接指针，指向第一条依附于该顶点的边。, \" Z+ I; F, C C% _+ j
所有的顶点结点组成一个顺序表。

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 Q. ~5 d; s) x1 ~ for(int v=0; v<vexNum; v++)4 E  [$ u+ P9 L7 Q7 [) s* _
{; j' h& l- y8 X- g: R
      if(tag[v]==0)
7 D4 m' [% G" n6 R          DFS1(v);
  c" F6 G6 y  k }# O& r6 i- D  T% c2 `/ F7 Z
}
! B& `/ f, _5 l  Htemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()  G0 x& o9 h7 g/ r4 `, W* {
{$ s1 o/ m; {: \8 G  M: h
stack<int> s;
' ]7 I3 I; a. f# K int tmp;/ \7 ~8 [+ }# t2 ?( L
MultiAdjListNetworkArc<WeightType> *p,*q;
* Y$ f( L# a+ P8 q4 b/ ]: K5 h for(int i=0; i<vexNum; i++)+ t  |) ~! L; W# I8 @7 @" H% Y, r
      tag=0;/ f8 g' W& Z& `3 x7 l# E4 w
for(int i=0; i<vexNum; i++)+ P, K7 c; ?; [7 ]3 l
{
' ]- [0 H, w& E- N6 V# _6 i       tmp=i;
3 ?) d6 X0 F+ \       while(tag[tmp]==0||!s.empty())
/ c+ ^# m" E% V' h) |       {( _! }! ]: r, M8 [6 B9 W6 e
         p=vexTable[tmp].firstarc;
- X/ f8 ~$ e# y, p- ~' m# o  s9 Y          while(tag[tmp]==0)/ ?, Q. Z3 w2 A. \* x
         {  }  C3 p. {& p* b! _& O" s$ T
            s.push(tmp);
  ~  L. A2 z5 K. _  U/ p             cout<<setw(3)<<vexTable[tmp].data;
4 K2 Z) F& I: v& M2 W             tag[tmp]=1;
/ j1 J" r* c# z6 c% C* }             p=vexTable[tmp].firstarc;% \% `- u8 H: Y
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
9 t: z  q1 v& K+ U5 p& }             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);1 Z9 d+ ]9 f( c  H
            //cout<<" 1st    tmp="<<tmp<<endl;' t( S, b# f* T- q
         }
" I$ v. `- M3 W; @! c6 M) `% O2 a          if(!s.empty())
( w" X7 n7 u4 P- F% G          {
0 u) A2 F7 D. A5 }$ H* V             tmp=s.top();
( J( \2 [! |. U; B. I. o             s.pop();
3 y" g/ B! T8 S  A2 _             q=vexTable[tmp].firstarc;% D8 y' f% q5 m8 R: @3 x- @
            int t=tmp;
4 M& `1 k# ]- L             while(q&&tag[tmp]!=0)
) y- d, s* G3 u+ H. W+ n9 N             {/ N4 R( H6 K% i& X2 S2 _
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
4 ~6 M$ q+ E; M5 v+ n                   //cout<<" 2nd    tmp="<<tmp<<endl;
% B1 Z! l* S/ j9 p0 X                   q=NextArc(t,q);  P: R" l0 G8 c4 ]2 m5 m
            }& V6 T6 N- W9 C/ ^/ r
            if(tag[tmp]==0)% |# N$ m6 H3 G2 I: b( n+ {
                  s.push(t);4 v$ ^% E/ ^% d1 C
            ///1、对应上面连通分支只有1个点的情况
, L& E& m3 ?- L             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
8 E" K' k' N% l! o             ///tmp要么等于找到的第一个未访问节点，
. o" R0 m6 s& p             ///要么等于与t相连最后一个点（已被访问过）
2 p. d/ \/ l+ Y. n* X5 Z( }             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点% i/ O* H# {& x" Y4 `) b) `* R
         }
+ ^2 r% _) U/ }! u7 s! W0 K       }9 {4 z( y8 n/ Z- b3 f+ C5 H
}5 m3 \! O! E: g5 X
}
  L9 Q$ p7 r- h# Y( f, g//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-13 g2 j  t( ^9 V! t8 g% Q
template<class ElemType, class WeightType> int0 g0 [! P4 |, \" U
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
; J) O9 ]$ o: a* U* Z) `{7 y) H: p+ ~7 z, K5 n
if(head==pre)
- ^( }6 m: C% e) |       return -1;
' N2 Y/ O! E' e3 P
$ ]4 P* X% Y: o% g7 |9 ^/ i MultiAdjListNetworkArc<WeightType> *p;
5 g1 a4 u' P6 s3 t& { p=vexTable[head].firstarc;
$ R8 a+ S$ X+ y: I) c5 a if(pre==-1&&p!=NULL)
2 d7 }$ l% Z2 h9 r5 o4 t       return p->adjVex1==head?p->adjVex2:p->adjVex1;. o* B/ x4 W$ y# Q$ P0 I( c3 A
//pre!=-1&&p!=NULL
5 I* C" A  K8 \1 s- H2 B5 y( m while(p!=NULL)2 T9 \5 ^8 Q# ?- h! A  g( b- g
{4 a# C" ~& Q4 O+ J  m8 ]6 R
      if(p->adjVex1==head && p->adjVex2!=pre)% y! J) J8 B' d$ J  l; E7 D3 R
         p=p->nextarc1;
; ]* {# W$ r/ Q3 r! [7 @0 q% p       else if(p->adjVex2==head && p->adjVex1!=pre)
7 Z( Z; U& a: f2 v  ]          p=p->nextarc2;
" l* @0 }5 d2 X# a       else if(p->adjVex1==head && p->adjVex2==pre)
5 N0 F% m) \8 |       {
3 G! q: u; S2 t: z. a8 p* Y$ a3 Z          p=p->nextarc1;, Z8 U& J$ o; s4 t7 @
         break;; [6 w! q2 E4 |: f
      }* B0 ^+ Z% `6 ?# K
      else if(p->adjVex2==head && p->adjVex1==pre)# |" d3 N8 b- y: ~
      {) h! z0 B+ l6 E: Q" Z' S) h# b) D
         p=p->nextarc2;
* U( @. N; r; J  I          break;
- h' V; s5 l) w! C- y  t       }
$ {) Y7 E$ q5 `" `& ~5 L) R8 _ }/ F; a, p: o  k; V
if(p!=NULL)( k9 k+ o+ w. M1 P( R! u7 H- A
{
5 ~9 @3 z# f3 Y6 e2 M: T       return p->adjVex1==head?p->adjVex2:p->adjVex1;& P0 |4 z" U1 J- \: [5 Y
}9 ^; O6 q3 e3 E- K% T( }
else) D! v4 {0 H& Z: ?  \
      return -1;
9 n3 O( k! K  \. g; ~7 d6 Z$ i}- G. o8 f  ]- B0 X8 L% f
  C" a" M- b1 e  M. t

/ ~: {) q, @: v: H' Etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
( s- E, f  F4 f$ n+ Y{8 ?6 i( w; x  a0 g# O
stack<int> s;
+ V; X5 Q% Z" X2 H  S* ~. v6 w int p,cur,pre;
2 F- l/ p5 @6 Z# O& U //MultiAdjListNetworkArc<WeightType> *p,*q;
% W2 J3 o5 ^% o" c for(int i=0; i<vexNum; i++) tag=0;//初始化
* {6 }- A; W( B+ A/ r- {/ u$ X' x; q( O0 u( O' I: [  m$ l' \
for(int i=0; i<vexNum; i++)
0 z' W  |( u  z- V9 \) ] {
* m. D3 d* _6 D4 q/ M( R       cur=i;pre=-1;
4 o9 s6 S. v# \       while(tag[cur]==0||!s.empty())
" U3 Y  C: m4 U8 J" P& _       {' e5 X/ d5 K3 v6 @! Y) t
         while(tag[cur]==0)
" e3 w- f- l" Q3 b+ x          {
7 c% K# ?! {# N: }             cout<<vexTable[cur].data<<"  ";
2 W' V% y+ @. d& @* p             s.push(cur);; X) T6 t+ s# B4 A
            tag[cur]=1;2 u, T- p$ x% g. k
            //初次访问，标记入栈6 u7 R* [; k' \# L9 ~1 y2 d: I5 g1 _
6 u+ E7 c4 f  P/ O7 S
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
; {# e; j! j% O' x% Y% B9 e9 H             if(p==-1)
3 S  L* ?8 e! c0 Y/ I" B0 D             {  B2 f5 m7 n6 _. Y: d' d! o
               pre=cur;s.pop();
" R! j- B8 Y" n1 `& X9 ]                break;. L/ _; u! I2 r. d5 j# [9 Z
            }
3 K' N4 q; `9 q" ]             else! O$ L, |- t1 l  T% K4 K
            {1 T# V/ }( o* I6 X& N$ l' R0 u" ?1 E* k
               pre=cur;3 Y9 S8 I# Y7 z2 Y
               cur=p;. S* D' r, z/ {
            }
! B5 Z5 J1 j7 ^. ^
( l. V2 V+ ^& @4 F          }
% R, C+ E* m- `0 l          while(!s.empty())) m& m% Z+ C9 r! P6 f& Q
         {
7 w: {4 |7 `# |( a# {$ z, E4 A             cur=s.top();
2 \5 P5 S2 [6 e) T6 \7 I/ }# J- d             p=GetAdjVex(cur,pre);
& Z0 X# k6 h, \3 m+ o8 f9 K             if(tag[p]==0)
, [# @% c4 W. J% C9 D" M0 [             {! h% Q2 K1 r; B7 _% Y4 L( J5 E1 I
                  pre=cur;
. @9 w' M6 z1 R+ n                   cur=p;
, `4 w0 w; h  R2 ]                   break;
& L1 p8 V. q! y4 P             }
  t+ [8 Z! G& V  h- u3 j. M  e8 F             else
" K3 C0 x2 H0 D             {" m' u+ V* ?5 v/ C! R
                  pre=s.top();
! q6 ]  }! p# v4 M" f6 I/ J                   s.pop();
) k  v: h) J& [& R             }& b2 z" u8 `# k: C
  |8 M! C9 U9 T- W0 m2 @' q3 d9 M: e
         }
8 S# D1 x5 }2 q$ x! s3 \0 B0 \: U  }2 W5 v
      }+ |; U& @: I7 G; |( Q
}8 r5 w" I1 t! J/ ~, K) M' c
}" I$ J& p  j7 f! W
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()7 L5 e9 ~2 b9 v
{# O' r& k+ M9 w& {6 @* [* J
for(int i=0; i<vexNum; i++)0 O; f, i' h8 g
      tag=0;% S+ M/ l" q2 t: n/ e
queue<int> q;
! y1 e2 Q8 G1 Z1 d int tmp,t;
# p  l' u5 Y2 S* P: M% @6 U, z6 y MultiAdjListNetworkArc<WeightType> *p;. o' Y- w% j: b. `1 Y
for(int i=0; i<vexNum; i++)
) Q# G' N" u( @ {+ U  |3 |$ F, U* y) E
      if(tag==0)1 T9 P  x. P- O
      {
& X* W: N1 n' f          tag=1;3 g- k0 l' L  b  {8 s* v' P- G2 j7 N
         q.push(i);7 t' C: A' G3 b7 t+ |* ?' j
         cout<<setw(3)<<vexTable.data;5 x; B+ L- E! O7 K/ [6 Y
      }
6 |; ~2 J7 O3 `6 P$ d& s       while(!q.empty())4 }. m& k6 `/ t2 M
      {
) v9 Q/ ~% r- j4 }4 d& C( ?) |: S          tmp=q.front();4 i: Y" B, M4 H7 s2 Q
         q.pop();' ?- Y, G9 y1 O. D1 ]  ^
         p=vexTable[tmp].firstarc;
$ v$ F$ e+ w5 p( H  U3 r# H          while(p!=NULL)
* J9 c, ?# M% v, K          {2 m$ e, r  |; f& J+ M& y. F" Z! ~
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
& p' {  I1 f$ `2 `$ @             if(tag[t]==0)
% Y% m# t# S8 z* C             {2 [" I$ v2 R) d! F' k
                  cout<<setw(3)<<vexTable[t].data;4 B# e6 N+ D# E1 m' ^& z. w7 O
                  tag[t]=1;
" \% \3 y% P) R4 ~1 K8 i+ l                   q.push(t);6 |+ ?( K* \0 C$ H9 R  o9 W$ n
            }! }# x: U7 w* J% \  }1 W+ k: G
            p=NextArc(tmp,p);
5 m( f3 Y2 E; F# A. T          }8 F' l6 z; Z2 J# F& T
      }7 C; q. [5 Q- [+ ~- @
}0 A! ?% x* J2 C, }5 ?  F
}. B1 S% x$ H( e" }* H
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()( E) W0 M! ^, ~3 P# J$ k+ K4 ]
{
  z& q$ Z$ k4 n7 A$ [+ j; m9 G MultiAdjListNetworkArc<WeightType> *p;9 F' k( P; K. _+ Z# _5 N0 o
cout << "无向图有" << vexNum << "个点，分别为:";
9 ?$ v' X3 `" W, o for (int i = 0; i < vexNum; i++), n$ D  D, c# w6 w% n+ w) h
      cout << vexTable.data << " ";
  T( r) L. g" |0 r" r cout << endl;
! Y. o  g) A  }8 k/ [ cout << "无向图有" << arcNum << "条边"<<endl;
) m/ |2 L6 |; Y0 z: _ for (int i = 0; i < vexNum; i++)
! I8 q$ ~' p# O3 T {
% A2 M& I9 _* K4 p; e" [( {       cout<<"和" << vexTable.data << "有关的边:";
" j" t- A8 K% V$ e6 V, p! I$ R       p = vexTable.firstarc;
" \5 Y) I4 @) r, A! l       while (p != NULL)! a+ \+ O  q) K0 W# o
      {
. I$ @" h0 K! H( E5 b          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";# T" r, C! r0 E/ e5 v7 a2 Y
         p=NextArc(i,p);# \7 G! k7 y6 X: I8 Y
      }
8 E9 L/ q$ X% m" p$ _       cout << endl;3 k4 C) @3 K, ?. s
}
4 {% }( k; @- v+ D4 H9 D" t}
( {8 N6 @5 r$ r5 q) y- v" K" I
9 A* H2 h' @- Y$ \% X
3 b- b: v2 b4 s/ i: ]. l0 x邻接多重表与邻接表的对比
! O) `! l, M- d* d/ |  X9 @* f" u+ C' Y7 z/ M5 d0 u2 N
邻接表链接, i! W; h, e/ X0 T. ]6 l
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。  x/ W$ N2 c" z  q0 v, z9 ]& ?
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
4 Y: z# d( x. b+ J. N为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。" c8 v7 ^% L7 c3 S4 s
————————————————  I, C' F9 v# l  |% D8 o
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。" u! h  W! E$ _
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
' B6 r/ l! |, m0 E& H9 B
. ?2 _8 N6 Y( ~0 I0 H* ^
6 |/ V) S" m, o4 ^' f3 P
7 X' _& P7 X7 \* U
3 {) }9 @2 i8 N0 ]————————————————
1 l) U3 D1 X. |5 }版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  c  X, D* y! ~' r9 F
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958) t+ P1 c; R9 k: v

: R0 i! Q9 V; \6 p# w% Q: P3 v3 `+ Y) }3 ^* j