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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：! J G6 U b# j; G- s d
data域存储有关顶点的信息；
+ }/ _/ H) h6 U) `% }& Kfirstarc域是链接指针，指向第一条依附于该顶点的边。9 S$ n& L2 b% D8 k/ F+ 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;
+ j; L# K( i+ O2 b; V for(int v=0; v<vexNum; v++)0 U* X) V$ p( L" o6 K0 l
{
& [/ [  l5 a( T5 o, i       if(tag[v]==0)" R, n, Y, d6 v$ j- R
         DFS1(v);
6 f" H/ k5 p  r, { }7 H4 b6 [# ~2 d( F
}; ]7 `, p7 T, O3 Z  T
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
/ \- x, N/ D3 {- W) r$ E$ z{
$ I* F  o' x, ?- A. K# M0 |) @ stack<int> s;4 e9 p/ D5 D7 S) F% `1 {
int tmp;7 F/ ]+ k' o* F; X) \: O9 A
MultiAdjListNetworkArc<WeightType> *p,*q;& ]9 D3 t% |( ]
for(int i=0; i<vexNum; i++)
0 N& T2 N+ U( A' E) c8 @6 `       tag=0;
7 U9 y7 }  R% H  B2 m5 g for(int i=0; i<vexNum; i++)
; b7 B# e: O, U- z# e' m {$ V" \: M: p4 N3 Z6 z
      tmp=i;' |! R8 K/ x2 [. ^' y$ [
      while(tag[tmp]==0||!s.empty())% k& |# }; g  O
      {
& t4 c# {  x  G! H& f; B$ j          p=vexTable[tmp].firstarc;
) h4 M: J, W- d/ B; n          while(tag[tmp]==0)( e: ~  f/ R! S7 m, P
         {8 y9 E0 f+ ^! H$ y! q# L+ W
            s.push(tmp);
% ]# g- P5 Z3 ?& I% U8 C* @             cout<<setw(3)<<vexTable[tmp].data;# ^; t. D) l- r
            tag[tmp]=1;3 V5 w. R" N  e' e; _
            p=vexTable[tmp].firstarc;
. z! N/ M, c# V: Z& n9 |1 N# [2 z0 |             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for6 f. E  j) x3 B- Z) Q
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);5 ~8 \" y) G8 Y& n" C7 X$ a- F
            //cout<<" 1st    tmp="<<tmp<<endl;
+ d" L$ D" z, }5 G0 T          }
( w1 y: j5 r$ L5 U% f' e          if(!s.empty())
7 |# y2 W+ \. g          {
& \/ O! _* ~9 N$ G; X             tmp=s.top();
% y# z4 I; m; B3 Q4 x             s.pop();: ~7 b. D$ C7 y' t* w
            q=vexTable[tmp].firstarc;
5 S2 F$ `( Y) F6 i             int t=tmp;( H1 y* `0 V$ z6 @4 Z
            while(q&&tag[tmp]!=0)
0 y; s1 M4 Z: u, ]  N% c" ~9 E# q- s             {
6 r0 X9 i& T4 S" K                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
  J: Q6 o8 \  W$ W8 w" w                   //cout<<" 2nd    tmp="<<tmp<<endl;/ t3 V9 G4 C8 F- d
                  q=NextArc(t,q);/ M1 f: s) W( D2 p. ?1 U, d
            }
1 [; g5 h+ o+ o9 C: m             if(tag[tmp]==0)
1 E8 g5 {$ E/ Y! o                   s.push(t);
3 E! E, N) b0 }& o, m1 Q; [2 Z             ///1、对应上面连通分支只有1个点的情况8 e& I# h6 n8 {
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
$ o  x0 x5 f# P  s% f+ M             ///tmp要么等于找到的第一个未访问节点，
; L+ |- H4 H5 q- ?# d' V             ///要么等于与t相连最后一个点（已被访问过）8 y2 D) N3 |9 C3 z
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点0 E$ t5 ^: ]5 J8 e& F9 X+ f/ v+ N& J
         }- |4 K0 ]' c* ?. i; j" Z
      }
7 Z' ^) F: ~0 Q# l8 K. ` }: r: p# w/ o$ s
}& y3 Y* g! K) ^1 }
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
$ u- C) b$ |% H' x# Vtemplate<class ElemType, class WeightType> int( h/ Q5 m6 ?7 Q/ d' o
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)5 Q+ `7 d8 b. m4 x0 t2 i
{* O9 r# G9 `" x) Q
if(head==pre)& l+ D% J: [8 c5 k0 c
      return -1;
- ~! @8 Y* T' n
MultiAdjListNetworkArc<WeightType> *p;
* \2 t+ d1 J) x$ F& `8 F p=vexTable[head].firstarc;+ n1 Q- E) `4 c8 f% }. n  `$ Q. m
if(pre==-1&&p!=NULL)
7 D' l( O6 }  t# o1 Q- X7 ?& e       return p->adjVex1==head?p->adjVex2:p->adjVex1;; Y: U+ G0 v5 X2 ?' q+ \
//pre!=-1&&p!=NULL
) `  K- g- \7 e1 j0 f3 E9 r while(p!=NULL)( X6 Z7 D6 d/ X/ y
{  D2 M, P7 `# U' y  `3 k+ u
      if(p->adjVex1==head && p->adjVex2!=pre)1 n: z" E9 ]6 b) D! U! x9 N" R
         p=p->nextarc1;
6 p5 C8 V& U, C6 Z) N" v       else if(p->adjVex2==head && p->adjVex1!=pre)5 x$ {( p( c/ ^2 A
         p=p->nextarc2;7 t1 c' R& H! ?
      else if(p->adjVex1==head && p->adjVex2==pre)
3 b& G1 N3 w: H( s  U/ E8 y0 \! P% r       {
  L1 O# v# [% u- r3 v          p=p->nextarc1;
: `' r# M  X0 a4 G; Z0 s" @          break;: e6 \: {/ K! ~2 d; f
      }) ^/ y1 n- q4 V( `3 c% l( s* b
      else if(p->adjVex2==head && p->adjVex1==pre)
! S$ B& r4 r3 t& M/ ]       {2 Z) `. F8 Q0 ~' @! s- F
         p=p->nextarc2;
* A$ w$ _# @6 p4 u' I/ `8 D          break;2 c6 T  F/ H: w
      }
# V8 E- l4 K# G }9 K, M* }9 y" e3 q" Y, i- H2 d
if(p!=NULL)" n7 k, e0 o3 r7 M7 U- r$ t
{
( u. v& w4 c+ k       return p->adjVex1==head?p->adjVex2:p->adjVex1;- D/ K1 D" o4 D3 q& S) f& C0 ^; R
}0 f, y' E* h/ j3 x
else5 M4 y9 G. u8 p2 v
      return -1;
4 v3 {+ G( T- K# y5 H}
" P' ?' C' s; B" Z6 M; w  t! @% V- @5 M2 J  u: i5 G% ^( S

- S( h1 n, P# M0 t% d0 `template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
2 @3 E0 w7 X, J1 _+ f{. Q$ T& Y2 X2 T8 V% y$ |% C
stack<int> s;( A4 f$ i  \' P
int p,cur,pre;: u% C* M; o% r6 o
//MultiAdjListNetworkArc<WeightType> *p,*q;, e8 Z. |* b2 U1 {, A- {
for(int i=0; i<vexNum; i++) tag=0;//初始化
& T7 n1 A* @! z. Z1 K
7 p% I; u) R3 \8 B5 ~ for(int i=0; i<vexNum; i++)
: T& N/ x' r& k" | {+ l/ \# N9 q" q0 Q: n" p
      cur=i;pre=-1;, b0 ]3 n- t. J7 w
      while(tag[cur]==0||!s.empty())* F( U! B. W# E, Y# ?9 m
      {
# G' H, ]! T7 N% Z1 W' l8 ^2 w          while(tag[cur]==0)0 ]* Z3 w  u7 |+ Z4 ]8 V
         {$ m2 s, k3 A$ Y3 f
            cout<<vexTable[cur].data<<"  ";
% B) |8 q- X5 L( f' Z             s.push(cur);
; O2 m8 I1 Y( A7 |6 ~+ v             tag[cur]=1;7 D. J4 f% G, L0 _4 B; C- I
            //初次访问，标记入栈
9 h# v4 `1 G/ f0 n5 c2 U% J& \( ~9 x2 N
, s- C% a* |& N) a7 t( b             p=GetAdjVex(cur,pre);//p是cur的连通顶点
8 K! z: M) N8 f% r6 ]1 ]# @: S/ [             if(p==-1)" g+ J- F, U) R
            {
: ?* r$ H+ V: g* x/ ~- O! o+ _! _                pre=cur;s.pop();
# f! c8 h  p& d2 o" w7 p                break;7 y/ e* `* Z9 u
            }
' L% r: W7 q7 c8 v: }; [- [# y             else0 C6 `& Q5 ^5 `6 l" }# x5 W
            {9 L$ l. h/ z0 }
               pre=cur;
) d+ m$ Z2 K# n; @0 ]6 S                cur=p;' t/ d! z# b/ c# U9 `6 y' W
            }" }. E8 [" y; J3 \

4 y( ?8 w: i* G% \: e% u          }% x, t" d/ Y2 i) y# h
         while(!s.empty()): X, {# W+ g$ w4 B7 q, _) @5 T
         {
/ ~' h" u1 {& Q  t             cur=s.top();
$ n/ ^) O# u# a: B             p=GetAdjVex(cur,pre);4 W; \7 e) C. ?, I$ f
            if(tag[p]==0)
5 [4 z9 [" D; F2 `5 \             {1 {5 P: x0 z" B5 A+ p7 d" U5 g. i8 G1 u
                  pre=cur;
( B4 e1 K3 J, K9 ]                   cur=p;
1 |' v- Q- v3 W/ E                   break;4 ~; G' m2 f3 F$ h  l
            }
7 }# X: D4 F: x7 |! X- s) S! L) u             else
/ g" P  W5 J& e) `% G. q9 h$ M             {
& d$ o: ^) @9 o2 @                   pre=s.top();
" z  S3 s% c$ {- x* `. ^                   s.pop();5 _# Q. ?6 J7 G
            }9 [- K) t  \) q3 \, |, G

3 B7 u5 e( J6 o          }
# E2 o$ U3 Z. C9 W& o% s
5 x5 i7 ?$ V; c8 {* U" G       }' c- Y6 w2 |3 c7 ?9 P7 u
}7 m% K: @' S) H% N* x. U
}' }- U- `' v8 U7 f0 E
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()% X0 Y# M: }6 ~4 ]6 K; M' `2 b
{
* P6 F3 X. n7 L2 v. D for(int i=0; i<vexNum; i++)
: T5 F' n% i4 x/ x) l1 M8 T       tag=0;
. r$ C* n! C7 D4 G0 o  o queue<int> q;
4 s7 I% l; k7 Q: K int tmp,t;
5 U8 y! b. C4 ?3 ^  A MultiAdjListNetworkArc<WeightType> *p;
$ v' }& {) h, L4 D1 ~+ k2 ?2 t2 `, v for(int i=0; i<vexNum; i++)
" u2 i! D# c8 F {" O& u6 M5 B8 b7 r
      if(tag==0); p7 `5 p5 B, a6 R9 y& b+ h
      {
7 d/ I9 I! ^: @/ Q) ^: c  w8 p          tag=1;8 }) a5 F: G: H; U  v$ p
         q.push(i);1 o3 Z: Y. r3 m# \" b3 D6 f
         cout<<setw(3)<<vexTable.data;& {) Q% ~  G6 z* g6 j
      }9 a, h5 X* p1 c4 v7 n
      while(!q.empty())
, d" Y- o3 p' N% x! }+ [6 ?; g       {
) A# n9 b$ V5 g2 Y4 H/ [. J          tmp=q.front();
  B9 y: l0 ]5 e1 N          q.pop();, {" k! e5 B( V- ?
         p=vexTable[tmp].firstarc;
* G8 W0 s! G) ?$ l          while(p!=NULL)
, `; Y; C4 ]: n* R: _& `& @, F          {
0 @. e0 I! E5 i3 H. G             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 ~: }, P1 R( h3 h; |9 Z             if(tag[t]==0)" Q/ e- V; Y3 K0 q$ D3 p
            {" s+ [( Y; l- x2 `! a/ c
                  cout<<setw(3)<<vexTable[t].data;
) k8 i6 X; Z: g4 L( s+ p. y                   tag[t]=1;
0 B4 i% @2 |- ?/ Z. s                   q.push(t);$ z% s0 d- n/ ^9 x" w
            }
0 [- D5 O1 T# i             p=NextArc(tmp,p);
+ F; @" @( [+ H! e9 A; o. }# [- c          }
6 H! k) T- i: a* x: L       }! x& Z7 ]4 I( {5 p2 E
}  T3 b! B  K. w" ]- r
}
3 n' ^# R+ f& W4 I. mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()" z9 m' Q& A2 k/ N7 @
{$ g# b' s$ f8 _1 B" F6 F# F( `9 c
MultiAdjListNetworkArc<WeightType> *p;, g- @8 i$ ~) \! w) H
cout << "无向图有" << vexNum << "个点，分别为:";: {( D. k* G5 Q# \, U; B6 Z3 [
for (int i = 0; i < vexNum; i++)( Y# ~- P/ g  r5 ~
      cout << vexTable.data << " ";
5 G* }/ w3 V/ i. z cout << endl;
/ s% g4 X2 l, i# h# g8 r cout << "无向图有" << arcNum << "条边"<<endl;
" O  M. z6 Y$ {2 V for (int i = 0; i < vexNum; i++)0 Y" \8 [! J7 D" p9 Z% b0 L3 X/ E; B
{+ o9 f5 E* h; N0 B
      cout<<"和" << vexTable.data << "有关的边:";
1 T* U6 J; H( T* x       p = vexTable.firstarc;; j4 H$ T& \1 u" x9 I" B
      while (p != NULL)
& {1 k% T7 C' T+ I! l       {$ a# ~& D& D# o' l, [8 X2 f4 W
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";; X# r% S' s3 G% m: m
         p=NextArc(i,p);/ y. m; G1 @- V( I
      }
* @' _+ c7 E+ N" ~$ ]; N( `       cout << endl;
. v0 Y) e3 G9 p* O. C# {) W) S }
6 `* q- o# Z. T& h}
" Y3 w5 P4 w. r) b
8 z7 d/ M$ c' j7 S  }
! t$ W; j1 b5 F9 V邻接多重表与邻接表的对比" ?% w, t7 _7 P9 l! I( V" c
/ X) y! y: V$ v/ |) E* {! R0 j
邻接表链接! t) D/ n8 B' s: n) }! R0 A
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。' M7 r' S! y9 ^
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
4 V( s% N' s& s# T为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。# K; @1 ^5 \/ V/ |( b$ {7 s  j) ]
————————————————
6 _4 {/ w$ N& x- H: O版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; c- u7 L5 m9 Y: u$ V5 ^
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
6 \3 ]. L  a- @( K) H) h# y
/ K" U7 b1 m+ o2 C
0 P/ h. O! Z6 V  T( ]- r* q8 p# @3 `5 _5 b- S/ y

8 Q9 R1 s4 u/ {- ]. z4 J: Q8 w4 L————————————————- P9 g% y! k  i9 w
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 @* O3 j! G8 @; H原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
0 W& Y3 |1 |. F& W4 J4 I" y" O5 R' u+ T
% `# j0 Z6 V0 Y. V  T