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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：2 q; P4 f" Y+ Q4 P% W. e! ~2 x
data域存储有关顶点的信息；
3 Y4 t2 }& a% w. ?2 I* a/ \9 |firstarc域是链接指针，指向第一条依附于该顶点的边。8 t" Z$ F% k. d. T! x
所有的顶点结点组成一个顺序表。

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;% f# W  j8 A  A9 d" G9 f
for(int v=0; v<vexNum; v++)
8 }% S6 }9 B- t8 d; `! m$ O$ V- U {& f# W' y8 L( m, E. K1 a
      if(tag[v]==0)% d9 H+ i5 N3 `+ Z$ m: @
         DFS1(v);* `: L3 S2 N3 E8 M' z! l( H, m. B5 F
}3 F; N' Z7 i2 t' R
}
) B4 G0 v" u% Ltemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2(): Z, J. }( j2 d6 }* V4 I
{2 U: @. T- y' \
stack<int> s;
( p9 _- z+ }: J' ] int tmp;' C# v  K7 i0 F7 r5 G9 }
MultiAdjListNetworkArc<WeightType> *p,*q;2 D, r, P! C* |1 Z
for(int i=0; i<vexNum; i++)
+ r8 M1 ^$ c0 b; ^       tag=0;% ?+ N/ x5 e- o
for(int i=0; i<vexNum; i++); s) W% k, f* d+ a* n
{$ Y* H9 R4 f) x
      tmp=i;6 [  P. b# j. n! p. q
      while(tag[tmp]==0||!s.empty())
% U$ B; S1 o' j( o: {( q       {0 q# |. S6 q0 \( U  c, `: i- o3 Z
         p=vexTable[tmp].firstarc;
9 ~; ]5 d9 r% c! D) i  b7 C% g          while(tag[tmp]==0)+ _- v3 h6 c, [; g) ]/ `
         {0 m4 V. u) Q$ _5 ]6 O% P
            s.push(tmp);
: X+ `9 u) G: b# i             cout<<setw(3)<<vexTable[tmp].data;
3 v& W) c: w) |1 n; v8 ?! U; G5 n  y             tag[tmp]=1;
. q3 f* b0 O8 Y             p=vexTable[tmp].firstarc;
/ @* s4 S0 I# j1 c+ H3 X; z             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
5 b  x3 D, Y9 P$ h8 C# Q% q             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);9 b  |) l6 p7 L
            //cout<<" 1st    tmp="<<tmp<<endl;& N7 b8 M+ ?! z5 |, V4 U! Q
         }: o  c5 B$ `, ?% B
         if(!s.empty()), q" X9 _/ \2 t6 J8 F& b8 M3 e, N
         {
: m7 k9 n4 k! j5 L1 I, l             tmp=s.top();5 K$ d* d+ v! s$ I6 W
            s.pop();4 `9 I5 Z) P4 k+ H
            q=vexTable[tmp].firstarc;! g: \1 @8 F, _5 K4 t" S  s9 }
            int t=tmp;% C% J& D8 G) Q: u+ G& ?; m* g1 h
            while(q&&tag[tmp]!=0)
$ N/ K7 Q2 m: `) \             {. E4 a: m# W: C* Y, Y/ C5 p+ b2 [
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
+ R2 [: e7 A' F( [! L. z                   //cout<<" 2nd    tmp="<<tmp<<endl;
. O  ~; T# a2 d9 a/ s! Q8 m                   q=NextArc(t,q);
5 \! }1 p# x! W             }" N3 M" L! G# Y8 x0 \7 ?8 j2 T9 T
            if(tag[tmp]==0)' k9 m* I' B$ H8 m2 i/ c: {
                  s.push(t);
9 C( \7 b, X! t" d: @             ///1、对应上面连通分支只有1个点的情况
. ^: F4 N. C% s2 S+ o8 a             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
( C( ^. C; Y" d! j( q9 p  j             ///tmp要么等于找到的第一个未访问节点，
# t5 i$ x' o6 J' m             ///要么等于与t相连最后一个点（已被访问过）
' h6 H) M" V3 V             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
5 M' u3 E, r" e; \5 c& t          }
( W! p7 Y& C* b  h% O( _7 E       }
# E8 W3 Y! F/ s9 w) \ }1 m9 [/ \& Y) A+ i# a. r
}5 C, `" k' F' E0 T) K% e) X
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1: r0 V" u  E8 x  a- w2 [& x/ h
template<class ElemType, class WeightType> int  Z' P! Q9 _$ q" V) ~
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
, ]9 a# N/ |9 N5 {7 Y1 c' m{
7 U/ Z9 c' j# B! e) i2 ~ if(head==pre)
0 w7 [/ r2 B0 n3 f$ P, V       return -1;
! w, x3 e$ S. R& |* i
, U$ I8 E- H% a3 Q. E% R3 W. l( f MultiAdjListNetworkArc<WeightType> *p;
/ G3 ~5 F, k' y6 n* A p=vexTable[head].firstarc;
6 {2 M( w: t1 [2 \! L! m* ? if(pre==-1&&p!=NULL)
% A% m' I$ _  q1 X& |) t$ G! z       return p->adjVex1==head?p->adjVex2:p->adjVex1;  x; O1 ^$ D# m8 f8 c
//pre!=-1&&p!=NULL4 @/ Q. g+ `: e- K/ R- u; D
while(p!=NULL)' j* t$ Q& R. ]& ~3 M( @
{$ K+ H: L7 i+ d) m( P# f& A; z
      if(p->adjVex1==head && p->adjVex2!=pre)
) `/ c$ x- T4 q* l8 G          p=p->nextarc1;
; s$ W3 @' n; H% h, M+ w* L  y4 n       else if(p->adjVex2==head && p->adjVex1!=pre)7 Q( @5 e8 v9 L/ a# V: U
         p=p->nextarc2;
' Z1 h' o# S* I7 G$ O' G       else if(p->adjVex1==head && p->adjVex2==pre)
$ O% I+ z9 o$ M) Y  w0 L& @6 e       {
3 M" @( h6 r1 x% @( f" h9 J          p=p->nextarc1;( X1 D' W+ p( G: X! {9 |( X
         break;
" r* b( [  o! ?) m9 H, P       }
2 n; ~! ^3 p8 B0 Z2 r       else if(p->adjVex2==head && p->adjVex1==pre)
- @3 N" S" J0 d2 p* S4 c3 u/ U3 d0 l2 S       {
* {+ b! R7 r, L* \( X# S- P3 a          p=p->nextarc2;, r8 s! ~2 U+ N3 i5 i
         break;
6 U% K# m6 v0 g. J- R2 {# y* u       }
! }% }7 B. l4 ]) @+ q }" {4 W/ x- g6 V1 O, l
if(p!=NULL)
& a% ]9 D& P( C  {6 h$ }3 D* R {
+ J) a7 e: S% f7 p3 y. s       return p->adjVex1==head?p->adjVex2:p->adjVex1;
# f* Y& O/ H1 P) o! F }
$ m" H8 _! I3 m+ I- M3 w! y& e else
2 \4 n+ A" Z" e+ V       return -1;
0 d3 U* d& ~- E! a% U}8 ]% o+ j1 ?4 q9 |% o( z
: o" D& y6 Z; z4 P

1 s6 Z% g) ~6 g& U2 G3 k0 _& n8 ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
5 e, R, F8 o. m{
5 v6 ]0 b) E- l" ^4 U1 i) g stack<int> s;8 k0 d- J4 r% t1 F9 q7 F
int p,cur,pre;
0 J4 ^3 j! B, l. l  G5 I$ C$ F% w! Y //MultiAdjListNetworkArc<WeightType> *p,*q;/ v9 H; J" @! r
for(int i=0; i<vexNum; i++) tag=0;//初始化
/ q+ M4 O8 h6 i8 f2 u: X! A$ P: ~! ~$ q6 @8 m; L
for(int i=0; i<vexNum; i++)
; r5 t% K" {! g {
/ Z) F! h8 W" q' s5 T0 V       cur=i;pre=-1;
& M/ N# L5 m2 U: |5 A       while(tag[cur]==0||!s.empty())9 j9 v/ U3 [9 V9 w% H- N+ }
      {6 A. J: z- @3 G( ~7 r
         while(tag[cur]==0)
* l& B2 B4 g7 x( c9 O/ _) k          {* }4 x0 E  `* g4 o6 t, q
            cout<<vexTable[cur].data<<"  ";
3 E; Z  y% }9 s" a* V             s.push(cur);- @( q. y2 a9 B
            tag[cur]=1;  P: y# [0 G  H) z
            //初次访问，标记入栈- z9 E6 B; G$ X" X& z  O, k

! w+ M$ W/ B3 o4 j             p=GetAdjVex(cur,pre);//p是cur的连通顶点8 g7 `/ @+ b% X8 w  V8 I
            if(p==-1)
& N. \" `" z/ }6 f             {: N2 `# u1 g& I7 S
               pre=cur;s.pop();
5 a3 c6 ]! e+ m! i+ i. ^                break;
  q! Q: S$ M# H6 {+ w             }+ M5 q+ C) j" Q* V
            else
0 D' C) d) N+ v6 P             {
5 ~, U, Q/ Q2 @1 G$ x                pre=cur;
5 L; M8 o; x7 F4 g/ ?  L; R/ {                cur=p;( F$ H! Z2 v/ t5 H; w7 L* B
            }" a0 y6 S2 T! }0 P  r: }
2 U# s, o8 ~" ]) [( F- D9 i/ J
         }1 [) w- D/ K9 X
         while(!s.empty())
/ p( I% q" `2 E! _, F) d4 K, t2 r5 K          {, p. f* d/ d! I6 Z9 G
            cur=s.top();6 j, b# X3 F7 @5 k. t0 y
            p=GetAdjVex(cur,pre);2 A& `1 L# n7 d9 s' d1 j7 |/ \
            if(tag[p]==0)
( P% s5 s8 m( A& S6 \             {; h% z+ y  p' v& V3 Z7 u$ J
                  pre=cur;7 G0 ]6 w1 e% J( U( E
                  cur=p;
$ \: v  \3 e, Y: ^# ]                   break;# L+ P/ |6 s" `" ~
            }
2 w- u& V: _4 ^* Y" }9 h8 I; G% _             else" @+ ]  u" A) f1 H, B
            {
9 Z( [/ h  ?& S                   pre=s.top();7 m  H  ?: t6 S) {. A
                  s.pop();, W( [$ z* z0 w+ C
            }8 H; x5 Q. U; E

# B1 d# B! ~* `          }
! A2 V2 L5 v1 m2 }) {& H- h9 t- G* o. Z( P. [8 T9 j1 x
      }8 e5 V8 o- H3 w5 K& i5 y& [
}) j- d6 ]4 }. Z2 K5 q& R7 ]
}
. v! }( @. a! r- n  a! xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()' x1 L8 Y7 y$ @% L# y
{
3 M: X+ h" Z' r  m2 a for(int i=0; i<vexNum; i++)
3 f8 U/ `1 _! e- a: R       tag=0;
9 x. l7 C) r# {  z6 a1 H" c6 V queue<int> q;
2 ~) ?9 t  G0 \: @# ^: R& M int tmp,t;
' d! d7 |7 k( p3 N MultiAdjListNetworkArc<WeightType> *p;
$ `/ t+ v' C: |* U1 j5 |3 _ for(int i=0; i<vexNum; i++)% J: [6 o3 v7 T/ v
{
% Y+ B+ i+ l& Z       if(tag==0)
/ r0 x8 w8 c& W! [$ u  C" Y       {$ R( ~- D0 `/ m5 Y, A# p  z9 f8 y
         tag=1;
% _) t5 V+ Y# G4 a3 x2 q, c- n          q.push(i);
% H9 \1 z2 S2 _! \" o8 V          cout<<setw(3)<<vexTable.data;
# [3 }( z/ b. U' {% }0 f7 s8 n! t       }( G  F- x( n7 j' G) j+ o
      while(!q.empty())
- k9 f! R( B& h9 C8 ~       {- {$ Y5 Q3 y0 {7 v" P
         tmp=q.front();
1 a# d. R; y. `1 j: f& z% O" ]          q.pop();7 Z$ J; R7 J) ~0 G. p
         p=vexTable[tmp].firstarc;8 t+ j! q8 k* u6 Z0 P1 \
         while(p!=NULL)
; w5 i7 m4 c3 m$ P1 H% U0 ^0 U0 I          {
$ T- m' c2 U. p0 O6 Z% V) g             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);; _$ d! N8 ~1 j/ M' h% Y
            if(tag[t]==0)1 p: e" n& w9 k/ w$ i
            {
( g% v% G' d; z1 I2 E% a1 D                   cout<<setw(3)<<vexTable[t].data;8 e+ ]! Z: k  v5 I
                  tag[t]=1;
: M! Z' Y$ l  Y* H                   q.push(t);& V  j% G% m. C6 k) V
            }( u  R* ~# d6 X# }* C6 i
            p=NextArc(tmp,p);
5 s+ O' ~: [6 q5 `          }
, j2 V9 l2 n2 ]. c9 S, o$ d. [1 [       }
6 o/ O( X- P$ D$ d& C+ X+ M }
( t2 H( G& L& Q' o0 L- M; r}7 y2 Y: p4 s) A: t5 ]
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show(); ]* ~  V. [. m2 I, v& \
{
3 u( [8 W* j5 `1 b% n* v MultiAdjListNetworkArc<WeightType> *p;
( Z9 p) f) e" Z4 N3 f cout << "无向图有" << vexNum << "个点，分别为:";) H1 ?, E! v  O6 {& y, a0 n+ N! V
for (int i = 0; i < vexNum; i++)7 I+ F/ [7 k/ g" @9 v( S3 o
      cout << vexTable.data << " ";( f1 m, i% N" q$ T  D
cout << endl;
3 k+ `9 G0 K1 |- t/ i  a cout << "无向图有" << arcNum << "条边"<<endl;
3 \% C, Z$ m$ a2 M+ p9 q5 s& n for (int i = 0; i < vexNum; i++)- X. {& B* X6 D  C8 [
{+ R9 z1 S3 k4 w" l. d3 J  r
      cout<<"和" << vexTable.data << "有关的边:";
! F1 E1 z5 y1 |; V( I       p = vexTable.firstarc;6 d% V/ V- T$ @9 M6 S# d1 u& M- N
      while (p != NULL)/ \0 R6 B( l* X. L1 ^
      {: ^  W2 ]- K, _2 w7 k( M$ [7 t
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
# H3 G' X1 n- V# T2 q          p=NextArc(i,p);
. S6 O# A$ W' H* q) ~- g: [- ~       }& l) R* p: C5 H- B2 Q
      cout << endl;
. U: Q7 H& U/ P. x  W8 { }/ A: F9 K, N7 }5 Z' I; {( a2 X
}1 o$ e6 P3 e& Y2 U
2 a& ]$ ^1 D. ?) u  ~  g
; C9 h% n" j1 d8 y0 @
邻接多重表与邻接表的对比0 e$ h6 J, a) O0 R, j, t3 r
2 A& s) X- V5 Y8 V
邻接表链接
5 g& B+ s' A( k在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
7 {" H8 J3 v8 @2 }7 B在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。! Y: o/ S& \% M
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。+ @  V! [& _0 E. j+ X! I0 o
————————————————
; _3 ^- U3 k1 y5 R4 o版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。: U1 {6 _1 @- l
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
( ^1 d7 j6 j& P- n; x% L5 }
6 w; `5 E. \& {% L, |  R# }: v2 @2 w; K5 S! @
' Z8 O/ z" S$ j* O2 f- ?% Y, f! ]

% p# r0 J4 c& ]( ?, s) Z7 ]————————————————
6 C0 A0 \( j. \. O1 t; E6 b& ?版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。& S0 }& e6 C& ~: [
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958. s4 O  E9 S- n

; b/ ^, g* \0 N& Y1 p; ~& K* m8 T8 R