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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
( n8 y) x( {! F9 R2 P5 \; V1 sdata域存储有关顶点的信息；
6 U3 Z0 t& [) U( l+ A2 W) Sfirstarc域是链接指针，指向第一条依附于该顶点的边。
( a* ?0 @$ R4 u" \$ L; M所有的顶点结点组成一个顺序表。

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;' Q8 j: o. u' M: |/ N4 Q- y
for(int v=0; v<vexNum; v++)1 a  g; b; a+ I& K/ c) K& r9 |  l
{/ C+ B0 y) X! G2 T1 S$ \
      if(tag[v]==0)
5 \& ^+ E: s, m. I6 X! r" p          DFS1(v);
" x( p! N# J6 n, G) {, } }( s3 E4 ^9 C; c& Y0 Y) {/ ?1 {0 p
}0 T. a$ E/ R+ q
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()  {5 h7 }0 U2 N. |
{6 j3 q* _/ A' ^; _! g* P
stack<int> s;$ |3 V+ m' \+ X+ t+ r% A
int tmp;
- j, {3 P; M6 o' Y3 Q2 q) d, ` MultiAdjListNetworkArc<WeightType> *p,*q;
3 y! L- b" E0 d% ~/ d& m5 e  W for(int i=0; i<vexNum; i++)
2 `/ u( @' }# p       tag=0;
/ ^  q7 n: f8 x/ Z$ Z for(int i=0; i<vexNum; i++)8 t  q* F3 |/ V/ B' [0 B$ F, f
{2 [! J' a( T2 J7 t
      tmp=i;
+ M. k9 }+ f3 R5 X- v7 z6 q       while(tag[tmp]==0||!s.empty())
) Y. A: G( p' T       {
3 d8 a7 Z9 L. p/ u/ h          p=vexTable[tmp].firstarc;9 A5 Y2 Z: a9 e$ A' p
         while(tag[tmp]==0)
: ~; X& b% |+ l; ?  ]0 w          {
1 h! ]: ~. u. {  C             s.push(tmp);) S, c/ }- B* X$ D2 _- `6 g* F1 u
            cout<<setw(3)<<vexTable[tmp].data;
. J; N" P( v/ I0 \, E9 P3 y$ q5 K             tag[tmp]=1;
( P. u7 g5 m9 D/ F- [             p=vexTable[tmp].firstarc;
3 h5 [4 \4 J& D4 |# E  e! ?             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
5 Q2 ?: ]5 K3 z+ G: \2 F             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 v1 U( d4 \( t+ E9 N1 g1 V             //cout<<" 1st    tmp="<<tmp<<endl;1 [' E/ V# \! \7 A: H# r
         }( I6 c$ K; s/ }8 z  x
         if(!s.empty())
7 k7 Q, X# q$ Y6 f: K          {9 W+ D0 \* ]& J' j( V8 Y
            tmp=s.top();
! r6 V) ]7 N2 o8 y' u             s.pop();( i8 V+ w% r" F' M
            q=vexTable[tmp].firstarc;8 e$ g9 j4 o; b1 T; C( v* V* _  m
            int t=tmp;
9 B' M& J+ p; n& X             while(q&&tag[tmp]!=0)6 m- Q. D* l6 A0 ~' n9 f% \9 V( ^5 s
            {
, s) u2 l( |& X                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
- j( W' r) D$ f' H) Y1 L+ N                   //cout<<" 2nd    tmp="<<tmp<<endl;- ?" `+ M/ C; Q+ l8 f5 E
                  q=NextArc(t,q);
8 H$ Q: q6 |2 I5 g3 ]             }  F; z: s: A$ ~+ }, @
            if(tag[tmp]==0)
  X$ u" X; |6 W! ^                   s.push(t);
" F! A$ B# c+ A" _. s: b             ///1、对应上面连通分支只有1个点的情况- Q$ e$ d  R; W% }" D* j/ Z
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
/ p1 x, q" r/ p3 g5 u( E( ?6 i             ///tmp要么等于找到的第一个未访问节点，
/ D  T  C& ^# l/ \. _% d3 e             ///要么等于与t相连最后一个点（已被访问过）
6 s7 r* [0 ?6 @5 s' C8 s+ r' [% L             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点0 d& h6 k( e% M* U
         }# M3 S; k- g0 @6 n( \) Z
      }
4 \) Z) @4 g0 a- I }
& G% w7 o, I" U5 S5 B' N}2 o! p+ O& Q5 R- P2 n6 J+ B7 Z& S
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
. Y+ `! P8 s8 r8 Ktemplate<class ElemType, class WeightType> int
1 h3 u( I! E8 g9 Q; r! k, zMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
" }* |1 a# z4 _6 _{
, m6 X# P, e  i4 n$ Q7 t if(head==pre)
9 E  s- D; L8 l2 t       return -1;0 J1 E9 f& I- R0 F; E) q
7 x, A% F) o/ J6 J
MultiAdjListNetworkArc<WeightType> *p;  t, k& ^5 k, e, s5 V1 `  [& C
p=vexTable[head].firstarc;
: K1 V: q5 }( }7 O8 f4 z% W7 P if(pre==-1&&p!=NULL)
$ F# u2 a% F9 u& q7 q       return p->adjVex1==head?p->adjVex2:p->adjVex1;- @7 f$ w* {) {; T+ V% f/ a
//pre!=-1&&p!=NULL* N0 U+ D! R9 n) \' Q# F: ~
while(p!=NULL)# e2 q: ]$ V- z! K  e, f! b
{' m1 c; s1 r5 e/ `5 s( t% v/ N! `
      if(p->adjVex1==head && p->adjVex2!=pre)
% f6 f& e# p8 @: M6 Q1 A4 `          p=p->nextarc1;
& m% X" `0 e0 q/ ?- J7 x! C' Q2 Y       else if(p->adjVex2==head && p->adjVex1!=pre)2 C* h- M9 L1 a3 x( \" |  E+ k5 m
         p=p->nextarc2;
4 D+ R; w& i" V       else if(p->adjVex1==head && p->adjVex2==pre)
  ~3 i- U8 m# a) w       {
: x% e7 @  e7 l- F' z          p=p->nextarc1;
3 h8 g8 T) r& r- _6 v6 o          break;0 B$ U9 H& i2 K' E; v
      }/ y  e% j: Y: a( R, D7 O
      else if(p->adjVex2==head && p->adjVex1==pre)% D  Z1 C6 b! _; ]2 h' t
      {6 _; \7 p' q3 G+ d" U3 [& T
         p=p->nextarc2;2 }. C$ i2 s! j* m' r
         break;
2 _- G* p6 S! |       }1 e% f, v$ |. b' o+ x5 c( j
}
. p9 G$ `# f! O! k+ l5 ? if(p!=NULL)/ m! r- H, X  U1 V. @4 _  C% r
{! z+ X9 s3 a$ J
      return p->adjVex1==head?p->adjVex2:p->adjVex1;$ X6 V" Y* t6 B; D! D& `
}
1 H$ _8 m* f- q9 ~8 H3 F else7 E" L9 q, n6 a& a$ C
      return -1;
# C  b+ Y- y+ P' f( Z}4 X. @0 Z6 f9 ~9 i- v8 r
4 q5 V4 R% O! l! G

4 F* Q! F1 O( [; j( F: h. K4 p6 \template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()0 \" I0 D$ ?+ o4 p7 T
{
" V. _6 A4 d4 M) ~ stack<int> s;
4 x8 j, \) x3 E int p,cur,pre;% g, Y: N) m+ c3 u1 h, \: {
//MultiAdjListNetworkArc<WeightType> *p,*q;
/ Z" `  G2 ?+ n, d7 B. ?, y2 {: d for(int i=0; i<vexNum; i++) tag=0;//初始化
* C4 H( ?* i1 u* g! {8 \! J" W+ T8 B2 L
for(int i=0; i<vexNum; i++)
! Z, p4 B# v& E/ k3 W5 @# q {
7 e5 T" Q/ S' {: Z" d. G: z/ ~       cur=i;pre=-1;
9 m( x; g4 R( q, U# W       while(tag[cur]==0||!s.empty())! x0 `( f* o- k: F9 ?
      {# W: |# d0 u0 S3 [) }$ D
         while(tag[cur]==0)% g9 O1 W; z) Y* X* s; C! U- Q
         {
$ O$ O! ]1 @6 E) e             cout<<vexTable[cur].data<<"  ";
+ M" N; w% R0 u0 e3 G: g             s.push(cur);) S- ?  F; n  r+ p. V. \7 `
            tag[cur]=1;
1 }! X" I. ^2 A! l2 G( G9 K  v             //初次访问，标记入栈
) j: F, y% U( a' u
' d9 o3 F3 D- N, m# d1 z2 `5 Y4 ?9 _             p=GetAdjVex(cur,pre);//p是cur的连通顶点' b2 B" \4 |5 j3 J( o* Y- N
            if(p==-1), ^3 I7 Z$ F" z* P. r  x
            {5 z) q3 H9 y* U6 @# v
               pre=cur;s.pop();& i7 f; P& l5 f0 W8 j0 R
               break;: e# n4 j3 h% d2 ?0 e8 u& U
            }. N+ ?* z" j/ I6 f1 A* A, `
            else
1 a' r" @% @( n6 a             {
/ ?$ x$ z- ~: g8 t  ^/ K                pre=cur;; H  \, g0 I7 I( {* Z
               cur=p;
4 M# Y; ~2 O. b9 f: O" F7 D             }
6 ?8 T4 y; A* v6 \$ Y$ b' o* z+ o6 I9 i* F
         }5 Z. B3 L  q( Y1 }3 f
         while(!s.empty())
! Z5 z* B( x' V4 k: W: S          {& q- `& K& K! _4 d* o% w  o3 S8 n
            cur=s.top();
. `+ J8 \: ?6 m* L             p=GetAdjVex(cur,pre);' r/ `/ {0 H7 q: Q
            if(tag[p]==0)5 h+ I: _$ X" b& O7 I4 t
            {
% h6 N- W" d/ M  e( n  p                   pre=cur;
9 l+ s' }$ t7 I; h) Z% L                   cur=p;# R* Z# g. x+ D# r
                  break;
( w) b: ^+ @) }9 }' k4 p             }. U: y+ ~3 M" M" ?( M* F. r4 t; e; x
            else
6 H' v" J$ Q! q* [# e* Y             {
; D3 u$ M( j8 V" |, s                   pre=s.top();- }1 l2 l! {* t4 h2 w2 q" x5 T3 R/ v
                  s.pop();$ z  h7 }6 b. h# @& n! l
            }2 m! \4 d$ T9 m" M# G

4 `# p" P% d# q# s4 V          }: c8 W" g3 Y" Z3 Y( d

( b! S) O: n2 w       }
( E" V+ v' c! s! g3 @2 ] }+ @; I- B. Q# V7 Y- `: b
}
4 D& }$ p1 }9 o/ btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()2 Z! G! ^* g' L) d
{
5 R) ]$ V8 q1 ], k/ w( I* @ for(int i=0; i<vexNum; i++)
" X7 o6 ?# \" {5 f       tag=0;* F$ C/ D4 U' f# R9 L
queue<int> q;
' u: g! p+ L, T8 ?+ b+ k! U) h int tmp,t;/ N3 \( Q! @9 M
MultiAdjListNetworkArc<WeightType> *p;' e4 ^$ P' F; y; M6 w  W' X' ?
for(int i=0; i<vexNum; i++)
- E8 o& ]/ G$ u" Z/ }, k {
- w8 Q- N( x3 N( ^       if(tag==0)2 s9 r! B4 l& f. u
      {
1 t* h+ E2 }" b4 B% |7 h4 Q          tag=1;
- i  C: k2 ~; Q8 R" _4 X          q.push(i);! ]5 X+ k. C5 X- X
         cout<<setw(3)<<vexTable.data;) C' T7 z8 Y: Q1 r1 q0 r
      }
! M2 h8 Z  |9 s% }1 w       while(!q.empty()): T& D" A8 b2 T% r2 _
      {9 f+ y1 O% u, j. _
         tmp=q.front();
' l* M6 A/ X: @1 v# n' S          q.pop();
5 D% V. V, ~. R- I' p          p=vexTable[tmp].firstarc;
, q' ~' Z+ y* a0 [+ w# }          while(p!=NULL)
# \% c0 I6 ?5 S          {3 W! e, h" d& y
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
# a5 w7 I9 y2 f             if(tag[t]==0)7 c3 d+ u! B; S2 x, n. e, B9 j) @
            {
# O4 m/ K) `* y' I                   cout<<setw(3)<<vexTable[t].data;
$ e# [  K# v5 J" p                   tag[t]=1;
, ?2 H  C  k9 l) w                   q.push(t);" U# U9 u' V, @+ C: z) W! Z) z
            }) H9 W5 H& Z( {4 O7 ~4 i
            p=NextArc(tmp,p);& J' o0 Y  W$ N% n2 R" q0 A: r& ~
         }9 ]  W& t7 W# C' {- |
      }/ N0 @9 q! t! m
}9 b4 _: I* q' J# u
}9 B9 C& A8 n1 y6 i" L# `& W; K
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
: j; Q* u9 n5 P{# u1 d3 _  G0 E: j7 w: M; q$ M
MultiAdjListNetworkArc<WeightType> *p;
; q) v! U+ r3 _4 | cout << "无向图有" << vexNum << "个点，分别为:";* F4 B, v, ]2 M, s6 {! d  Q, T8 y
for (int i = 0; i < vexNum; i++)
: n- M9 x3 O$ A$ L- b# W       cout << vexTable.data << " ";: q7 J  }9 }2 N  m2 e- B# A
cout << endl;
% x" q1 d4 }9 [$ M3 I( w cout << "无向图有" << arcNum << "条边"<<endl;
. ]6 l9 u; y- C9 P6 A for (int i = 0; i < vexNum; i++)6 p/ r3 a1 C/ a
{
3 r3 }1 d( {2 l- r. ?6 H       cout<<"和" << vexTable.data << "有关的边:";
0 B7 L/ k2 E! T5 m       p = vexTable.firstarc;1 V# M( I, l+ w" }' P7 K& E
      while (p != NULL)
! Q% R' K! {4 f- t/ |4 P" A% A) p       {
/ V% s8 h# `* ~# }; P          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";* B4 U% F( V7 ^+ A. T
         p=NextArc(i,p);
2 u4 W" k! U4 v. D0 ?       }; G$ ~8 k1 p+ D& S$ Y7 p
      cout << endl;2 v% k$ w0 j9 Q) j
}+ T7 q, I8 Q& ^8 q) k9 ]* }) ?- k
}' ~$ ?0 o8 ?. |
5 L: Z" B2 P( ^; u* F
' O, C, c8 \2 [. `" }# {
邻接多重表与邻接表的对比* x' Z- @/ h: @8 M9 v
4 T0 q: R$ b0 K% {! I; `3 V
邻接表链接
0 U+ j' [8 J; P4 m0 k3 ^# |在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。" l% ~; x# `' Z- p% [
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。# o; V2 r7 j8 ]0 d
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
/ f  W+ W+ g- A) i2 o% ]& N————————————————
+ y- d; x/ L* z+ ?( ]1 g# Z8 M版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ f* Y, @) c8 G% C原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
+ g" A& W. x$ @1 p) g
3 e! w# _! B! z+ E0 e6 O3 B7 D6 M
- ?1 d2 Y: |4 V0 r9 f
4 I0 H% r2 n6 V  R2 I+ G/ F
, d- p, R1 p; h: O* o# ~6 s6 E: V$ c————————————————
! r1 R& c1 p) p- {' [版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。* j8 H: [2 p, Y# L  ^! D
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958- k- O0 V' Q' e( K2 d% y
! o. [5 l- O: L( T. H. O
# p/ H" e0 F; L4 ~( {( w% b$ q