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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
. K7 M% q8 y( Mdata域存储有关顶点的信息；
% `, r. p. z" E; X- D) V2 S4 a: dfirstarc域是链接指针，指向第一条依附于该顶点的边。2 P( S! @: E0 O) b
所有的顶点结点组成一个顺序表。

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 O2 ]4 g! L# b! E( ^2 a for(int v=0; v<vexNum; v++)( c/ C6 ^  \& X8 ?
{
' N6 [0 k7 R- {( B       if(tag[v]==0)1 Y: {2 x" n, l. G
         DFS1(v);
2 M4 E* X" R0 y- J4 g9 Y }
/ E1 p# _, q' K6 m( q) K}6 s$ k, u* s# w, ^; G
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
( {4 M% g8 l9 k4 Q1 Q9 H$ h{
; @( V, v; x& e) B stack<int> s;
( q. F; r) Q0 q6 B! Q& z: V int tmp;/ q; k2 @, S; {3 _
MultiAdjListNetworkArc<WeightType> *p,*q;  o$ o& E2 f1 v3 A* ?6 B
for(int i=0; i<vexNum; i++)
( O, q0 h: c  h2 l4 C       tag=0;
5 B7 ]5 ^5 P  s( F: c- K& q for(int i=0; i<vexNum; i++)# K8 B" U/ w# x- G! N& g( d
{
. M5 C2 w$ G- p& B% r       tmp=i;/ n, J$ x8 |9 k9 V
      while(tag[tmp]==0||!s.empty()); H3 {3 z/ z( s" `4 A
      {5 |1 G. k% U' f8 J; w) {
         p=vexTable[tmp].firstarc;
: p9 r9 {1 V, ?/ |# o          while(tag[tmp]==0), a5 L( z  V/ P) Y/ J
         {8 {( V# t  ^, X/ F
            s.push(tmp);" V+ I* R4 A3 Q' v6 ^4 E1 p& r/ o
            cout<<setw(3)<<vexTable[tmp].data;
' Q  k* _8 U; I, T* h8 m! v9 j( R             tag[tmp]=1;$ M2 m3 r' C7 i* S9 f* \5 N
            p=vexTable[tmp].firstarc;; b/ F6 R/ `. V# k7 _
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for8 F/ I. G. `' n
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
4 B* T- s) k& s             //cout<<" 1st    tmp="<<tmp<<endl;& A' A4 e7 u# j* P' A7 y0 f# L# V7 [) U
         }
0 {, u1 b) g' u: ?: c          if(!s.empty())
# O" S% m8 W6 F7 }6 h  ^. L9 m          {
5 ^2 a8 x, X) A" {+ a% l$ \             tmp=s.top();
. T% |+ N1 Y4 @% g. i; ?             s.pop();
( j' S$ @$ ]' O( y* I& w             q=vexTable[tmp].firstarc;
9 N+ M1 d) I# f- Z. x$ o0 U             int t=tmp;* |( i, w3 l  A' L/ A. C$ p/ i
            while(q&&tag[tmp]!=0)+ Z9 ^+ {2 u) U: E3 I) j& H; M
            {& P0 ?6 l+ H, g1 D$ D3 a9 ]
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
- a* ^, f3 h/ K6 D' W                   //cout<<" 2nd    tmp="<<tmp<<endl;) _. K2 v5 _  X5 \, L$ Q
                  q=NextArc(t,q);' R1 L6 t9 b6 Z* k# A9 [1 c0 V, G
            }
2 Z, \9 W/ y- h1 n4 M             if(tag[tmp]==0)
* p9 W, v, F. Q- L                   s.push(t);) _* S0 F# B* E+ H: r7 z- m
            ///1、对应上面连通分支只有1个点的情况7 ?2 _3 R/ o* [* q! k/ @2 ?
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
; z; b+ X: t% y4 F! E; e             ///tmp要么等于找到的第一个未访问节点，
% r3 F3 r( P8 ?6 Z( X; ~             ///要么等于与t相连最后一个点（已被访问过）
( t1 j+ P* ]. n3 C: n( @8 }; i) {             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点2 H0 s3 C- s. i% m* B
         }" a/ x2 y/ S8 h
      }
4 c9 s# j9 _5 {2 _8 U }; h  Z  z3 |9 x2 h+ n+ L. y2 _! F* |
}
; M9 _. w0 d- u3 c/ w//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
2 l# Z5 E8 Z6 p6 Z* p  ~. a$ J) }( mtemplate<class ElemType, class WeightType> int5 e9 d9 u4 v# m3 u
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)/ ?! H( i$ w# u- Z4 t: S* c' K
{% c4 Q  a9 o) ~! ]$ `
if(head==pre)
$ S3 O4 I- v! g9 q% N6 [1 J6 \) C       return -1;
$ g! p3 b' t: x( [2 f2 b2 U; U7 {" E. v) u
MultiAdjListNetworkArc<WeightType> *p;7 r" V  ~: J/ i% Q% v
p=vexTable[head].firstarc;! p, `6 S0 _: }; }3 c
if(pre==-1&&p!=NULL)
  Y# k- c9 P* }& N       return p->adjVex1==head?p->adjVex2:p->adjVex1;1 @+ Y. S; \  K6 y; Y
//pre!=-1&&p!=NULL& R+ c7 l# a: d8 I( e3 J
while(p!=NULL)9 G5 W. p+ O9 `
{
9 [$ m" q) @% y       if(p->adjVex1==head && p->adjVex2!=pre)
# s* {, b8 ~- |( p. g6 O" @          p=p->nextarc1;
2 k. V* d0 O4 d3 Q& m       else if(p->adjVex2==head && p->adjVex1!=pre)
( |, E& @! P. K( {0 U/ L8 \# [0 J          p=p->nextarc2;7 F% C( g0 A6 |
      else if(p->adjVex1==head && p->adjVex2==pre)
) P  i" l' [% l6 h' T       {
/ T# N! G1 L; G  q* p) O          p=p->nextarc1;
/ \7 D+ c) ~! t( }6 c) ?          break;
' _9 v2 i* f( w" g2 |       }
! w7 C! o- I5 A  \1 M" w$ g' _       else if(p->adjVex2==head && p->adjVex1==pre)- k8 E! u) b, @( e
      {
$ L6 V2 |5 F0 m( w5 C; v          p=p->nextarc2;
7 Z. `& Z) y! A- B          break;+ y+ W* j! S6 ^, \4 A' I
      }
$ \. [7 C. J# \ }. m' t" N% `% c  S
if(p!=NULL)/ T/ n1 l/ D( R% Y% T- C
{/ Y, X# f; {, ?1 Y% H7 T8 {- w
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
& {6 _$ H7 l. W1 u5 W8 ?# x }9 w$ ^5 W$ a9 w: Y6 y4 V
else/ G# S6 a. O: u& X2 E; t+ E: Y. f* A( V
      return -1;
: D# z8 o& \$ d5 h}* P; G7 \! J" i( E/ L, b
( R2 B4 _7 Y- G& I7 k/ o- V% V

5 C  Q6 H- N) ]9 itemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
5 ~9 k4 P4 K) w# `; \{
( m" B- Q2 y8 }  o5 ? stack<int> s;0 E- O7 U( n0 F
int p,cur,pre;
: z0 R1 m) v( B' s. V: X' i* ~ //MultiAdjListNetworkArc<WeightType> *p,*q;( h9 D; K/ r) X1 p- f$ ^
for(int i=0; i<vexNum; i++) tag=0;//初始化. e+ m! ~/ O  }# X7 l! p) R
; X. N( m( T8 M7 @6 @
for(int i=0; i<vexNum; i++)
+ \6 M. |/ i% k, c {
9 ~. y& M: b7 O) e9 T% a; B3 V       cur=i;pre=-1;
5 c* U& W4 ~! b# x; {# _. p, }       while(tag[cur]==0||!s.empty())1 S, `6 E8 S5 K6 h2 F
      {7 D; L6 g% `& H0 y+ B  a/ k- O
         while(tag[cur]==0)
5 m0 a1 m& I: K0 w7 f          {
! S: o$ y3 y8 I3 L. D             cout<<vexTable[cur].data<<"  ";: ?8 j6 u& y5 u* _* e
            s.push(cur);
( ]8 k, K* f' j. L             tag[cur]=1;4 Y0 @8 U* j0 o- b6 t- z
            //初次访问，标记入栈2 P. i/ f( Q2 R% z  ^/ W# ^9 P

8 h' h5 k& B% h7 Y9 x# K; W- g9 M! D             p=GetAdjVex(cur,pre);//p是cur的连通顶点7 [% b7 p0 T9 B# y3 n
            if(p==-1)9 E* q$ A; E. \
            {5 V9 d! o! |* J& Z
               pre=cur;s.pop();# c9 r7 ^7 m, E7 C
               break;- U- g4 a% E1 `4 k
            }% @/ @0 f# A0 k8 P9 _
            else+ S( h: s) A4 u- j8 A# p
            {% h/ j+ }( b0 z* G8 f
               pre=cur;
" U: P# C( v0 r* a                cur=p;
% n+ G" R. l7 l  P             }
4 [' [: Q0 {6 g& k% q* {  ]
- @& p  g: \7 d# F, T# ^; n( c          }
. ~: k, W  [4 G9 d% u. t          while(!s.empty())) g+ b; j3 |" k' v. R; g' D7 L
         {. P+ e" C& k+ g$ @) l: Q2 F  z1 k
            cur=s.top();& N7 ?! ?8 ?- Y8 @( H
            p=GetAdjVex(cur,pre);
- b) Z/ K: x7 s             if(tag[p]==0)4 y. ~* G& G7 h2 \+ S4 @& y2 J
            {. `# @  E1 @/ V1 C$ C$ w! s* k
                  pre=cur;( B0 l, c3 @! u8 H. q
                  cur=p;
! a# J7 o; |: I, l' H+ w                   break;  g4 B* L6 B6 |# D2 V+ o9 y7 X' T5 Q% j
            }
7 v4 V( V" {/ h7 u             else$ o) f. b" _- [. g; v! e: w
            {
2 ^; c, K' m) A  q5 R- R                   pre=s.top();
7 j2 X& d  `. ~" Z                   s.pop();, A5 u& j6 e. I' V% L
            }
. E# g1 X$ ]+ k: V* s+ d# O$ q, N8 ~" N
1 c! j. E& h9 q; [3 r' w0 a          }
, V1 t( w0 z( }' b
" L8 I: H( {3 c. l       }
5 w( c+ ?) W- Z1 e  o% W }
$ e! P- O& \* l1 u}2 l! ^. V+ v' ~$ n' q
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
0 q2 q2 ~* l5 ]5 M7 o' O{
& a& T* t3 o$ W7 J3 s for(int i=0; i<vexNum; i++)
9 e* t/ M! u( Q9 I       tag=0;
) A( ?1 `( M: V( C queue<int> q;- _* ^7 [% k4 d& I1 d- f
int tmp,t;
5 M" T+ g& j# B: H. ~+ k0 p$ A MultiAdjListNetworkArc<WeightType> *p;
8 q4 ]5 s, Y; \- V, j# B for(int i=0; i<vexNum; i++)# v6 A. I8 E8 _) d
{
6 q- ?' C+ h( `9 _       if(tag==0)! ^9 m& E  O3 j# `" J  Q
      {
3 F3 ~2 _' D  U" ~5 T2 _; d          tag=1;
3 V: M" d0 G4 V4 d5 i          q.push(i);: c, R" D$ f; C) g, f
         cout<<setw(3)<<vexTable.data;
% t# B4 u! ]' p5 Y: W1 ]' j0 T! G) y       }9 M; O3 @: \% o' U; t, X
      while(!q.empty())
3 d5 e% R* H! s: D4 O- u  U: v       {
0 o! w% g! V# \+ Y4 v          tmp=q.front();
0 e$ u- g" ]3 i8 Y& G) l) y$ p          q.pop();
4 p  X! G- R9 E2 b5 C          p=vexTable[tmp].firstarc;
+ I$ ^: a( t6 T7 U          while(p!=NULL)  a0 d6 v2 s4 S* ^: \! s# V
         {  f8 v. U" ]# r* R5 g- F
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);5 a. _2 A% W% U4 d
            if(tag[t]==0)/ E1 J( K* D% ^. c4 G( D, ~" ~5 [
            {1 x, c+ j' I& D3 z
                  cout<<setw(3)<<vexTable[t].data;
! G8 i6 ]  l" A& |+ Y                   tag[t]=1;2 o3 O: t9 l+ H* F0 i; F# |! q' Y
                  q.push(t);
6 c; m+ a8 Y4 p& \) B* M             }0 `! |! I9 q4 j- j
            p=NextArc(tmp,p);
* x7 J- E) Y& T          }" U! ~$ I5 ?8 x$ b+ G$ G  c5 ~
      }
- O& |$ _0 [1 v; K }) q  o& W5 j% M9 w4 N
}6 y# ?# `( f/ r. X& j
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()* C7 {0 ?2 \2 c. x. ?
{9 ~! D: F. O# p/ K) u
MultiAdjListNetworkArc<WeightType> *p;
  C! d# E$ c$ E cout << "无向图有" << vexNum << "个点，分别为:";7 W9 Y8 i. b0 g; r# O
for (int i = 0; i < vexNum; i++)
& J5 r% x0 s* m       cout << vexTable.data << " ";
, t, o+ x* ]2 K! |; {/ b cout << endl;
2 j4 v& a- c$ |% z4 _) f cout << "无向图有" << arcNum << "条边"<<endl;$ T2 H  t, h$ g, c  O
for (int i = 0; i < vexNum; i++)
6 w: i( }" r5 F6 V; M8 i* n8 f2 c) ? {
! d  \# |; T' K" m       cout<<"和" << vexTable.data << "有关的边:";) d0 }7 o  n3 R# w* h
      p = vexTable.firstarc;
+ q, Q& c2 R. ~/ D' t' ^       while (p != NULL)
7 S) @5 h7 d7 p; ^9 p3 C       {' Q1 z+ W$ P  O1 n, a6 B. T# q- J$ {
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";2 E; V* Z4 \% A6 U
         p=NextArc(i,p);
3 Q" y5 F/ l9 x( A% j# K2 l       }+ O- m% e! b0 |' X! U
      cout << endl;0 @; x0 Q  F( {6 L' ~
}+ u( K4 @. w0 u: T5 X7 m
}
6 \& T) ^) d( ?6 L- J/ A) h# f- l: n% P# i

2 f, e) U" R  I0 W( L5 [邻接多重表与邻接表的对比8 Y  Z: V+ f4 @  ?( L6 v5 A

4 G# y3 F' D- m/ V3 N3 T8 H. _3 M邻接表链接
6 a& i$ b. U; U' P5 `4 m5 e( a9 j- I& a在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
( X2 \& z2 f8 b7 r2 |; g在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
6 c3 X& v& h  I为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。4 D  ~8 i% h! W. Y
————————————————6 k' I# Z3 i$ r( I5 Z" r
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。) L# T8 _/ b5 M' h- }8 o
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958+ b- N6 {! ~$ R

/ P8 F+ t3 W* S5 S3 Z; r* e- A8 g9 k
& E6 M  R& o/ j; z
- x6 n: Y  \5 R( \! n  d
————————————————
4 P  E# k3 p3 e; O3 h% V版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; s3 H" O/ D% }4 r
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* G" H+ F2 G2 ^* W$ k8 ~' V4 ~  I6 }4 Z7 w

/ q" W$ f( G# M' C