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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
6 e* Y* ]4 _! G: z6 j- Y7 qdata域存储有关顶点的信息；9 ?3 \7 _/ a$ @2 }" `
firstarc域是链接指针，指向第一条依附于该顶点的边。
& K. I! Q1 i/ ?) ~' L, W所有的顶点结点组成一个顺序表。

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;
1 D: p/ O" h  T2 A+ ^& f+ N' x; q for(int v=0; v<vexNum; v++)
) Z; ~9 y" l2 ^0 ` {- T; p! j% @+ a
      if(tag[v]==0)
* a# E+ B. V1 |, M; E8 O          DFS1(v);
1 n! l1 @3 M4 b! y }
- x8 h. C& c% T2 c# |% E; g4 M}. J5 w7 X4 A6 I$ Z* @: a7 O- e% v
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
) J* G2 F; q. }  m; }" z, s{
6 Y- W& l! U4 L( ]. w8 T- j stack<int> s;1 ?! v+ z6 K1 Y
int tmp;8 g" N' @$ v7 Y
MultiAdjListNetworkArc<WeightType> *p,*q;
" b" c8 l' e0 [9 {7 n for(int i=0; i<vexNum; i++)
2 |! x& J! T1 U       tag=0;
8 ^) ~9 j0 z- Q% A% r for(int i=0; i<vexNum; i++)
3 m! c. e* M" b0 E. r* X2 o {
7 ?" d( x! i8 R/ s       tmp=i;, F$ g3 [' t4 T; B
      while(tag[tmp]==0||!s.empty())
% X- ]# {; t. m       {* a6 Y! W8 u7 ~4 _
         p=vexTable[tmp].firstarc;
( X4 l+ W8 Q' N: {* z4 W          while(tag[tmp]==0)
  v. n3 Z7 E* P* T6 M6 b9 A          {" N! x, L! c; o2 \* ^2 M5 K
            s.push(tmp);
' a4 ^1 c6 q) v3 K  O8 a             cout<<setw(3)<<vexTable[tmp].data;6 ^& l' F  \. ?# n& n
            tag[tmp]=1;
* F* T' h% G9 w: b* }  U             p=vexTable[tmp].firstarc;4 w, |$ q! l2 e# m
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for# m- u# R5 r9 V5 k) s
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
; z* p* ~+ y8 H" c5 Y# G( C             //cout<<" 1st    tmp="<<tmp<<endl;
7 _7 l$ y3 H, q% J; a          }! G% H% G' I% \" S% [
         if(!s.empty())
( M9 U! B% m* ~, p% Z- F          {3 [3 ?" r3 D8 Y$ @+ u0 v
            tmp=s.top();! d0 v& z( r3 r8 B
            s.pop();
" |4 @' [( D, y' G# U+ d% c, p             q=vexTable[tmp].firstarc;7 w2 F" P9 Z- P/ Y% u4 n
            int t=tmp;
- q3 X9 u+ R" W/ C" i             while(q&&tag[tmp]!=0)8 r1 c. \$ ?+ E& ^( `% k. E
            {9 U1 W, M1 i1 v& I/ C9 b% p
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
* D9 k! Y# K; X                   //cout<<" 2nd    tmp="<<tmp<<endl;4 y( R, w' j8 t0 n
                  q=NextArc(t,q);* V/ M4 G, I4 e- s7 y
            }
; ?) Y' O/ b( b8 x: D$ @1 Z3 }1 @8 K5 u             if(tag[tmp]==0)
: C2 O, F9 ]5 h1 S4 [! C                   s.push(t);# e5 o) Z2 v" c- X( R0 v/ e" V  Q
            ///1、对应上面连通分支只有1个点的情况
4 K4 g4 U, |* J6 V/ w             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
4 k# R5 f3 X0 \; }. r             ///tmp要么等于找到的第一个未访问节点，
8 O5 Z' d7 F1 w: t4 a0 C             ///要么等于与t相连最后一个点（已被访问过）
& d5 {3 A3 Q# g             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点( ^7 k( V+ O+ p5 i5 e) A
         }- h: W% r% @: ~9 P! c
      }  i, y" J' e1 V$ S' O
}$ R2 V1 v' H. K( C* L' A+ a0 n
}
5 Q  U( }. y% t# T* M//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
# J: i4 ~1 G+ g- Ttemplate<class ElemType, class WeightType> int
) S4 l* Z. f5 R% e& aMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
. O3 U8 D/ A- @( o) ]& k1 w/ z! X0 e{' @9 J5 K& ^- ]7 g7 a6 w; w8 ^- ?" `
if(head==pre)
1 d  Z* ~/ v# z" a: ?5 N0 ~       return -1;
+ ?' \* Z. ^+ M# [
5 c6 y; a3 \8 u MultiAdjListNetworkArc<WeightType> *p;4 a$ P7 Q& m* C# k# g
p=vexTable[head].firstarc;. ]- g3 s4 \8 n% |9 ^) D1 [
if(pre==-1&&p!=NULL)
; s7 G; }) G1 A3 t. W$ w; @       return p->adjVex1==head?p->adjVex2:p->adjVex1;
/ f0 [; m  A& f  J //pre!=-1&&p!=NULL
9 Y# @( _. P/ Y while(p!=NULL)4 }# @0 `" y" a) `0 {/ ]! I
{
" e9 w4 J% m9 C* w0 C       if(p->adjVex1==head && p->adjVex2!=pre)
! D5 T% m' h& h0 o8 Y0 D          p=p->nextarc1;
6 x* _5 b* C8 B. h0 V       else if(p->adjVex2==head && p->adjVex1!=pre)0 n8 J3 ]$ Z' w& X2 W" D
         p=p->nextarc2;
( i# ?# z7 t- o, K- u, F. \       else if(p->adjVex1==head && p->adjVex2==pre)% j/ I0 V8 H: _& W9 m6 r
      {; d! x$ @( D& z* I; @; t
         p=p->nextarc1;
' F/ R$ I* X0 K) q% |' q! m          break;
$ W( m- h3 d3 s1 n% K       }
3 M* w0 ^! e6 y6 H8 {       else if(p->adjVex2==head && p->adjVex1==pre)
  Y& s& P% y  {( ~       {
" O2 L! y9 q% P- S: Q" x          p=p->nextarc2;
" f+ \6 [9 v) D7 ]          break;2 i/ V. l! Q$ h, g, E
      }% F* B5 w) n2 d8 ^$ s
}2 k! ?; p. p+ [, E0 a( x' T+ a5 \
if(p!=NULL)
; s: S2 L2 p- v8 H% k {
' j2 r! {5 i6 r% @, }       return p->adjVex1==head?p->adjVex2:p->adjVex1;
2 N: q) k! G0 D' a' d }
. \7 S. P& n, |& D( h4 b  V) ` else" R( b' T- N: D3 G9 W8 f7 w" Q  _
      return -1;
% |# A& a5 G# s3 e# H* w2 c2 u}
8 @5 Z1 J8 O, Q% s. ~1 b+ @; v1 y. B/ J# A

2 n" a6 {# ^" W, ?template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()7 \0 N+ Q7 R; l. T% H0 N4 ~
{% V3 p9 H: r9 A
stack<int> s;
" ?2 e# s9 B$ s7 y int p,cur,pre;
, @, E% l8 K' Q, ~* u //MultiAdjListNetworkArc<WeightType> *p,*q;
# }4 X6 \  g! W/ d for(int i=0; i<vexNum; i++) tag=0;//初始化6 w3 d; A  S2 X0 f% O

. i3 b0 V* a# q& W for(int i=0; i<vexNum; i++)* N9 q6 j. {, d& b1 T& m4 J
{
8 q! E7 H0 I! ?- k: H% |- x9 h1 ~       cur=i;pre=-1;# m& ]# l2 k. q! v
      while(tag[cur]==0||!s.empty())' c' @' O! ]7 a2 z+ R3 W& a; f
      {9 J2 @1 I# M- p4 E9 G% s
         while(tag[cur]==0)
  k1 S( ~6 Z8 V# y  O          {% \/ `& d; e& V& U/ f$ I3 [
            cout<<vexTable[cur].data<<"  ";2 j* c! j2 Q& a  o& b7 B0 u5 v
            s.push(cur);: R" q# r2 U- |
            tag[cur]=1;
9 d% B7 y7 t' R0 R             //初次访问，标记入栈
' K1 R3 w! @- ^' N' L2 ~3 _8 v( G, A
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
' k( z- f. L% P# r8 p2 X             if(p==-1)# p7 _9 i( V+ Z* J
            {  w$ |7 C( `3 A& G1 M) z0 B2 ?
               pre=cur;s.pop();, p3 A/ y3 e; Q- a0 T# F1 J- x$ J
               break;  ]5 X- J2 [3 I3 T" D/ n( `1 Z
            }: ?* p- k1 @+ k+ V0 d+ {1 G! x, Y
            else
! y$ o$ j% y! Z0 F! ?1 p$ Q             {
1 e  d+ w8 l; G0 ?                pre=cur;2 V- C9 Q# `) M0 c
               cur=p;; b! m( L8 d  E9 e5 ^+ G
            }

5 O4 L2 `' R9 h( z6 z8 R8 x9 n          }
  x- Y/ T4 q% c% u( J9 b          while(!s.empty())
! P  E0 S$ r7 @6 a          {
6 e( H+ d0 o; r             cur=s.top();
% Q: H. [8 p) H% I" Y( J/ y7 y             p=GetAdjVex(cur,pre);
8 L; I) n; j1 J& T& B4 \: R- O. G             if(tag[p]==0)- @0 l' |% s/ q6 }$ A7 G
            {
: j" Z$ G+ B" l                   pre=cur;: ^  f* {0 `7 N# y4 y$ K
                  cur=p;
: h0 S6 y  o) _4 L                   break;9 b9 d6 U+ v  u" L! C0 E% T
            }3 D% r% i& F( E" i1 }) ^- \# N8 G' z
            else6 t6 U: _$ l, j- H
            {- p/ ]1 k4 d& A; P( F- {& `# q
                  pre=s.top();
0 h- H1 G% S) _6 X: \- Y                   s.pop();
7 m& D1 `7 I0 }             }* }& p' t: ~: |0 s+ h
; E. X1 W% i: b* `8 N
         }& ^! \' ~* d( P, w$ F

* {& m+ k7 O; O- ]; p; f       }
2 Y, {" |7 N- A3 a* U, `- E }
& h3 }1 t" V6 Z: ^! ^}) }8 Z" k0 m& K! }! B& x
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()4 U' X7 @' T9 T; x; v: h% x
{7 ?8 s4 k) ?) r) j+ Y& K: ^
for(int i=0; i<vexNum; i++)
# q# P9 ?' z; h% w) [$ @& E       tag=0;
, x! k7 x/ r, w* ?8 N- x queue<int> q;
' T* Z/ e: C' [8 u int tmp,t;
/ J4 y4 \$ ~, H$ `' o# W MultiAdjListNetworkArc<WeightType> *p;9 L" L& C1 |( @) J' \
for(int i=0; i<vexNum; i++)! r6 ^( @# K; l: D6 R" Z5 f, R8 j
{
% G0 }2 ?$ I$ u3 E* R       if(tag==0)
1 A) O% A$ S" i6 [6 k' E  U" V0 Q       {
0 Z  \5 `8 T- Y$ u          tag=1;
  ?9 ?, L2 R; k" m          q.push(i);
( w" `/ v) U1 |$ `          cout<<setw(3)<<vexTable.data;
  C( m% x6 }1 a& a       }! j/ U9 h: K# }+ k
      while(!q.empty())8 ]( l; ~* a* T+ i7 ~" V2 Z9 |
      {
- D5 B- H6 d3 u' P  t1 `( a          tmp=q.front();
% L' J1 X& r' l! b8 T9 m          q.pop();
. M/ p# _/ ~( t% u% \% t          p=vexTable[tmp].firstarc;
& \2 \$ {; y5 E6 n8 Q2 ~          while(p!=NULL)/ v/ h9 Q+ z$ T5 p
         {
" H# X  D! L  m+ o5 f' i             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);5 _2 b6 J  z) w& a7 M. f
            if(tag[t]==0)
, F0 z! o5 V' x7 U  \             {& Z/ O$ ]7 }/ T/ C
                  cout<<setw(3)<<vexTable[t].data;
& T  \  @- k+ L( f                   tag[t]=1;5 l+ d/ p# y3 a; w, z0 m+ L5 |
                  q.push(t);# @+ a) h8 V$ G7 k9 J
            }
. T8 ~% w/ w+ v9 _% Z             p=NextArc(tmp,p);, p: M0 V. Q! ?$ s& ~% j
         }
( E2 e& y2 p& E8 C       }( w1 Z4 M9 m! W! a" X% K
}5 `7 C: w) h' a' n: d! g/ h" w3 B3 G
}
  g' k7 ^+ a: Ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
# P6 u2 A: K% v* v{
+ {  F0 [0 t$ |, ` MultiAdjListNetworkArc<WeightType> *p;
4 Y& S! a5 H( `5 F5 }+ l cout << "无向图有" << vexNum << "个点，分别为:";5 j6 R1 e+ ]% |7 ?
for (int i = 0; i < vexNum; i++)( h4 R0 s) T/ [* V8 C4 r4 f) h# c
      cout << vexTable.data << " ";
+ d/ Z3 P) e5 F0 d9 P3 Z4 b! N cout << endl;+ q0 T8 Y8 q& j5 q% A" E9 c
cout << "无向图有" << arcNum << "条边"<<endl;. `. O4 e. a% O
for (int i = 0; i < vexNum; i++)1 G2 m# M5 [/ R3 t$ r; S
{+ ?4 L$ K% P6 o, P% O! H
      cout<<"和" << vexTable.data << "有关的边:";
4 P+ A/ B2 y& W* f, ^% l       p = vexTable.firstarc;4 n7 }$ z9 ~1 D- S9 P0 t/ x
      while (p != NULL)% P8 e$ a1 ^, f
      {. _7 |' l( Y0 e
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";8 _% @% {$ f8 O+ _$ q; K! Q% a: V
         p=NextArc(i,p);" H# E$ V' d& G2 m- P
      }+ w# |; P7 M+ A% {6 h& w( ^: p) g
      cout << endl;; S  u' c& K. g( a: i+ f/ s% c! H
}
' w2 `% W$ ^+ Z8 H1 _, y; e}
8 x4 h  {. r( [2 |+ A. _5 e% Z( I% N4 A( z( ~2 B- h

6 ^( S6 U- E; w( l3 D邻接多重表与邻接表的对比
) y: \" P9 Z- p* O4 z9 {6 M1 A4 }/ I' q  {
邻接表链接3 p# L0 o" G- Q
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。! a# D: I5 z2 L
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
% N+ j: f& C6 a+ S! l. O$ k9 Q为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
2 h5 C4 w2 W: L0 S; a! c; x9 }————————————————. Y2 i+ G) y  L
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; ^: U$ L' [' M7 y2 c8 F9 x" l
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
+ Y' t; w& K. @9 h. t9 Z" W3 \# }: q2 M' k1 X0 H2 E% `

( G! e* {2 L2 T: c; b% E0 ~' J7 c' S$ `; y

% A2 ^. a* Y- b8 L5 o/ Z/ n' T————————————————; i9 F3 t9 b0 ?& S8 }) l
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。0 t/ L  B/ x$ N* _. }
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669582 m( C  Y# R4 h. Z; M

+ g3 @# N6 E0 [5 Y9 [6 P
/ F+ H  f3 f, M: `4 T$ Z