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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：' Q9 P: c5 p& q& O& q' R
data域存储有关顶点的信息；6 t& T, i3 j+ w) S
firstarc域是链接指针，指向第一条依附于该顶点的边。7 N' y: ~8 w$ ], d4 D: E
所有的顶点结点组成一个顺序表。

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;
0 q! f) d' C# t for(int v=0; v<vexNum; v++)2 |7 `  ]* e: M& o  ^6 T
{
/ ~  z1 w8 g* [7 ?5 ?       if(tag[v]==0)$ A5 u' d* z6 v+ A, ?( g
         DFS1(v);
3 c: w; `: W& S# c( E) r$ g- \ }2 s! s* t" ^. ^
}
; g3 e5 ~9 s5 N# ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()( Z! v/ Z) Y" n. N1 Z; A
{
" C9 g. C. H9 x# m stack<int> s;
* j) i& u7 _/ G$ L1 I7 z7 ]9 ? int tmp;9 b5 ?* f3 ~$ T: U. q/ c
MultiAdjListNetworkArc<WeightType> *p,*q;. w0 w- m' P/ j
for(int i=0; i<vexNum; i++)
+ V. @& r- W+ [3 _       tag=0;& T$ R0 M. k. R2 q; a0 l1 R3 f
for(int i=0; i<vexNum; i++)
$ d, P- ^4 c0 R1 [4 N {
. n+ T4 H( F& b       tmp=i;
& N. N4 a, D$ i       while(tag[tmp]==0||!s.empty())
  B- z; z0 l7 o4 o       {0 C1 E) b; _+ F1 H1 _3 }
         p=vexTable[tmp].firstarc;
8 |8 A/ b( Z0 u! J% ^1 [          while(tag[tmp]==0)4 b' V0 }# f8 U; e" A
         {
8 m$ J: \  w  I$ ^- s             s.push(tmp);; g$ {1 A9 f: z; X) H6 l1 s- g
            cout<<setw(3)<<vexTable[tmp].data;) ]/ [: n: C4 r1 ?4 z0 ^; I
            tag[tmp]=1;- D2 t9 x5 k7 K- O6 S
            p=vexTable[tmp].firstarc;2 U3 ^; \8 U+ |" V
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
- X+ V& U* l  _$ f! U" q1 v  J0 y             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
# J. P* d  R4 C* l! e             //cout<<" 1st    tmp="<<tmp<<endl;
! y: |3 _- X) G# X# U! T/ w" k, w% F          }
) v' ]1 Y4 F6 r4 r% m- H          if(!s.empty())" m4 x& f3 s% T6 b7 G5 x
         {
9 w" R2 V( N  \4 P5 @8 l& D* I             tmp=s.top();
% l$ U1 j' M9 M7 H             s.pop();4 d, o. U. D7 K0 r# W! X
            q=vexTable[tmp].firstarc;
0 i6 }2 j* u' @9 Z             int t=tmp;4 O$ V* @1 D" g; i
            while(q&&tag[tmp]!=0)' F% P* v4 T( b5 Q( M
            {
+ `* |' `2 |7 j( W# J- D# [                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
8 t9 C$ h" g3 m6 u                   //cout<<" 2nd    tmp="<<tmp<<endl;
/ M" Q, u% h( a% q! q3 e                   q=NextArc(t,q);
. C9 S" \! G* ?2 j             }* t5 l3 p! S( }5 @* \# T, }
            if(tag[tmp]==0)2 I5 f/ w) G# s  _5 ]/ X9 ^. w3 y2 n
                  s.push(t);; `+ A  h- J. o6 b& W5 r4 I
            ///1、对应上面连通分支只有1个点的情况
) g# W4 x0 C  M3 H$ D             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
1 u  U4 K5 V7 n, I. O             ///tmp要么等于找到的第一个未访问节点，
. [+ u7 U. z# `/ F% _. q$ {( P             ///要么等于与t相连最后一个点（已被访问过）
( {& d& ]4 C6 f7 v8 C9 w             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点' q2 x9 N& H) W# {  K% `
         }3 d) w1 Q+ s5 F* ~
      }: g1 |0 {- B; }0 J' y
}
& z# e4 [) ]) z+ U( b5 i. D5 ?}& H5 J' y/ u7 w0 e! r# r
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
  y& j7 W8 [! Z+ Btemplate<class ElemType, class WeightType> int
% I$ E1 R% N! A( G$ Z0 qMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
6 j# a! \) f7 J2 q{
' Z& l- \& d4 m0 i- }; C if(head==pre)
, ]' g+ N6 I% G) w* I' T       return -1;
: @/ x1 z$ w. b( Z
% n8 d0 h9 `) o0 V MultiAdjListNetworkArc<WeightType> *p;6 E1 Y( r4 B" x1 _/ q% S, U' S
p=vexTable[head].firstarc;2 ~8 [! V! ]- P: G- t' ?
if(pre==-1&&p!=NULL); L8 ~1 |. T3 W# S5 f# L- f
      return p->adjVex1==head?p->adjVex2:p->adjVex1;6 m# z6 o3 k5 l+ `. J) B1 x  U
//pre!=-1&&p!=NULL  T; F2 \  E0 t
while(p!=NULL)1 u2 n( W8 {* V$ @
{1 l2 N! J  j9 I
      if(p->adjVex1==head && p->adjVex2!=pre)
5 o7 A+ n' `0 G9 ^          p=p->nextarc1;
5 ]  v; C0 x3 `# H7 `: W       else if(p->adjVex2==head && p->adjVex1!=pre)
         p=p->nextarc2;
4 X$ b) D/ O4 F5 y       else if(p->adjVex1==head && p->adjVex2==pre)
; n# \. a) ~8 m- F1 H* g& G- Y- k       {# c0 t7 o8 |: i4 i
         p=p->nextarc1;9 `2 [, D9 ^1 b
         break;
! D9 e, k# H5 A! ^9 x8 L6 x       }
, N! I: U3 F6 S5 k- c       else if(p->adjVex2==head && p->adjVex1==pre)
4 x" _) V* }* _1 _       {
7 [( J8 [+ o& ]( N; ^          p=p->nextarc2;4 z! I. L( ]6 p) u; R8 |
         break;
, V  ?' ^- V" K: ]2 e       }
9 l' a/ L3 r9 w9 i6 o3 x }
0 Q: k. s# @: m if(p!=NULL)
* x- N' N$ F5 q {' h! |3 W* S, `$ V$ V9 @7 _6 w3 }
      return p->adjVex1==head?p->adjVex2:p->adjVex1;% W; g1 c6 @4 k
}
* R& U+ E! O6 \3 F else* ]4 Z/ f% y, F% q( M6 n
      return -1;
/ Z5 G! W9 @! @* n& u  u! I0 _}7 q& v" j9 i; c7 S& y: ^' I; v0 A

' N( ?% F* m. e+ F
& ~: ?& T, n- c" Stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()! Z+ C' M+ l4 P- K  p3 B1 e$ m
{
& ^; P  D4 l! @" [  `) ~5 l$ }, ` stack<int> s;4 a8 I5 V7 b& s1 d
int p,cur,pre;
8 _& A1 R$ Z% b8 A* C; N //MultiAdjListNetworkArc<WeightType> *p,*q;& n5 @2 i* }& U" V4 l( Y
for(int i=0; i<vexNum; i++) tag=0;//初始化% r0 G+ N  o: M$ b6 [3 |& b. A
# @. `: ]* p8 T% v" ]
for(int i=0; i<vexNum; i++)
' d2 N  ?/ ?5 ~5 d {
! s* X! Y( H; o/ ?       cur=i;pre=-1;
' L. g* p8 [! D) E2 h8 t# Q! O       while(tag[cur]==0||!s.empty())
* m) K, _" {7 C       {
+ M( c! t8 n0 ]; u7 v" A- T% \          while(tag[cur]==0)5 T; U# ]# Q3 a6 m9 I! Z
         {
5 G# y) Q1 X' v5 O             cout<<vexTable[cur].data<<"  ";3 d0 B9 R+ {: d+ L% g$ N
            s.push(cur);2 ~3 w0 \# O* p, h" V' C
            tag[cur]=1;- v* [$ j0 q2 b1 ~4 g/ [$ [
            //初次访问，标记入栈4 A& u: c. j& _9 s: S/ h

# o* \- `% y1 n( g# m$ ^             p=GetAdjVex(cur,pre);//p是cur的连通顶点, ~% Q1 b" ]/ A* D0 L8 T& G# z
            if(p==-1)
0 k/ C: ^  j- \& y8 x& j7 w% c             {
$ \2 X: M5 L. p                pre=cur;s.pop();5 G( G% z( Y% \
               break;
7 l8 f* v2 m( g- H             }, t' J4 D4 }) K3 u8 u4 D9 z
            else' l, ]& f( O# n8 V! C  w- H  p# V5 \
            {8 a2 W4 u5 u' b
               pre=cur;3 A( J5 L* |0 x: z0 p, ^
               cur=p;
9 J+ M, b$ X/ z" ^; a. e0 O! ^             }) A* k8 C9 F+ F4 G5 |- ~* o
1 f! L* J$ n; h) Y
         }
( F; }" z7 T6 T0 o$ ^/ T          while(!s.empty())/ H0 _& b; e, K3 }! I' ^+ ?( S
         {
0 j& k6 u9 k; |5 ~) w             cur=s.top();8 J0 Z. p+ }% a- s
            p=GetAdjVex(cur,pre);! l3 q: h1 r0 ~: _0 V1 q' I. |
            if(tag[p]==0)
7 {# G. w4 @. C0 `: A             {. |, P: c8 D3 v- Z* U8 j5 \; f
                  pre=cur;
1 p" d. R4 E! b( @, y% C                   cur=p;
; C0 Q/ B( c9 O6 h                   break;
6 ~3 j2 ^& Y1 Q* v             }, i/ ]0 x& \, B+ B
            else
2 z& n9 \; H" {; Y  H             {
+ O* K+ C5 p5 N$ W, r                   pre=s.top();+ v) I2 w7 G0 M1 P3 o& \
                  s.pop();) [! d9 Q' ]# t# \/ ]" l
            }5 U2 m, T$ O* R

2 v" M& M; K: t, i3 L8 Y( x          }9 \0 K4 r" g' p
6 R5 [/ j' ^/ ^! @
      }
0 \; ~% F- P9 O3 e" z }
- C& r9 f4 M% _5 ]9 z7 o& j4 K}, [8 ~! M- D: a
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()1 R8 x/ Z* q& a! T8 Y( D
{
( M# s) N+ E: I) D0 k for(int i=0; i<vexNum; i++)7 T7 W, A0 O9 j/ R1 k; P8 a
      tag=0;
( L' E; Z( z% Q7 a8 [9 O7 \2 P queue<int> q;
& i- r/ h, r# F- Y int tmp,t;$ n7 \5 l) v; l9 b* W8 y
MultiAdjListNetworkArc<WeightType> *p;) n/ K3 _, W' x( b( B
for(int i=0; i<vexNum; i++)
0 y6 L" o; F: A7 t3 t {
! L+ F/ ~3 r6 f: J4 J$ J& I5 M  J/ |       if(tag==0). ^; g2 P6 l6 O1 k+ x: s1 W$ \
      {" t( O; k) }2 }5 x. R
         tag=1;
8 v  n4 H- \$ u  {% b0 l* |          q.push(i);7 q: t) Z+ B# U6 p' Z
         cout<<setw(3)<<vexTable.data;# b. M3 G* O9 M
      }
+ p: L  S! V1 e, [, g) O  }       while(!q.empty())
5 }2 J* X4 c# A       {
: M8 E  b8 b( K9 K          tmp=q.front();, T: I5 x' b" X
         q.pop();
% X- a  d# u, G! s! k3 n          p=vexTable[tmp].firstarc;; L7 j7 }# c- ]2 @
         while(p!=NULL)
5 t' ~# |# q1 T          {. l1 M/ i- o# V3 ^# U. T
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
8 @* G8 ?6 I. J7 b4 E  }             if(tag[t]==0)
& ^4 H; m; d$ {2 p0 ^             {/ Z/ U! F* A. X* a: u- j
                  cout<<setw(3)<<vexTable[t].data;9 j8 e- ?0 u9 M; O
                  tag[t]=1;( v# i3 h; E7 H
                  q.push(t);
$ t1 s: e) k. l+ z- [( X- y             }
$ ?7 @) \: O7 }9 I4 w5 A$ }             p=NextArc(tmp,p);% p- Z; {$ u8 j% ^9 G2 I- r: y
         }
9 l" p, I% J0 ]# l: R       }
% x+ u' [0 O9 [4 x1 ^2 o" v }, X6 l. _0 k3 ?! \( _3 z
}
8 X/ Y: X) J$ i% @3 W" t6 Utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()1 S$ x% V' e0 O" R% h$ f9 _
{
! j* Z. w, A2 p6 W+ |0 c MultiAdjListNetworkArc<WeightType> *p;
4 L# G% m+ O0 Y) Q. q) e, F cout << "无向图有" << vexNum << "个点，分别为:";
( R/ a* O( j8 _ for (int i = 0; i < vexNum; i++)
- @  A* k9 f) J& W( K       cout << vexTable.data << " ";1 m$ K2 i" o& n% H9 }, H( D: s
cout << endl;
( r( P$ r; l' J8 p cout << "无向图有" << arcNum << "条边"<<endl;; s% R2 a" O7 O+ _; V5 r
for (int i = 0; i < vexNum; i++); a9 y  u. y6 ?5 S& Y* K) s
{
5 F2 }! \( Z/ C, v6 t       cout<<"和" << vexTable.data << "有关的边:";
9 b, |/ e0 ~4 N# u: y4 J( C       p = vexTable.firstarc;
$ {( a6 S' l! p0 J       while (p != NULL)
* E6 H: w6 e0 K1 s3 a       {
5 f/ z0 G: f( a          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
% |$ Y# |5 F" u* @1 \5 K7 M          p=NextArc(i,p);
/ a  A, I% A+ ]: l1 e# B6 K       }; D: L4 g# j$ E& s3 U
      cout << endl;
8 {( m6 `/ e& F  ?6 o/ p' F6 ^ }
/ M5 H' ]/ O2 P6 \& ?# {. w% @}" @+ t4 i1 }8 Q9 t( I. P! j
7 m, Y) `  s1 t

0 d4 W' ]$ X8 C2 `; t/ Z, U8 y: {邻接多重表与邻接表的对比$ B1 q! X% _; |0 w
7 ^  `/ j! N& ?* a
邻接表链接
% x; d) K! d2 E: U0 d. }在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。. ?3 g8 X. p: K8 F; M6 B2 I
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
0 p8 x5 {* r; [+ r; {- H为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
2 L8 F2 h/ `& _) m3 a. y; g————————————————: t; R$ X! r1 k! ~" {5 R# Q, A
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; {# h, c; }2 j. L
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669589 Z1 z6 p$ `, k: z0 A) a6 w6 c
. `7 I! g; ?2 Y) n
; u, u3 P- e+ ^5 O- i

0 k' H# f2 B) A! `
( `; A! @7 W5 O8 I5 i————————————————
, M& C/ Y* _% m8 h" n版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. w/ S9 c" k3 @# b- x( j% K原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* `% |4 j/ j+ l* a  E
5 [. u, Q: i& Y2 e$ M% o$ D* X1 Q+ t* h5 ^! ^3 i3 _  H$ G4 }