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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：+ E& K; G) Y' X0 Q4 L$ ^; I
data域存储有关顶点的信息；; z. z) H' E1 s% I# U% E
firstarc域是链接指针，指向第一条依附于该顶点的边。
; o; d! J* f' R8 g- h3 m" e5 ?所有的顶点结点组成一个顺序表。

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;/ I9 ^" C$ t) i- h
for(int v=0; v<vexNum; v++)
5 F( i; W5 p) J5 o6 {( ] {
6 X/ j9 y. P* f9 v       if(tag[v]==0)
+ t9 i/ L/ v- o; ], q          DFS1(v);) x: G4 Q) n( s# I
}0 m6 g, C! ]1 h4 e( A* G$ Z+ K
}& L; V9 n4 }% }. T3 K
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()3 g* U4 E& }3 }6 ~- X, f- R- p
{
+ C2 ]' w$ P' k4 P( b+ \ stack<int> s;7 M3 T# n4 M- `' X: X
int tmp;
4 W7 H. Y( Q: C6 C, P6 { MultiAdjListNetworkArc<WeightType> *p,*q;" Y; x% j3 L* Y+ L% }
for(int i=0; i<vexNum; i++)
# l* c2 x( W  f- o7 z- i+ r0 R       tag=0;. d  T* {: U% B* S) ~/ V
for(int i=0; i<vexNum; i++)! K( [1 s' i) X) b+ `4 o
{# t* S3 l7 X0 {1 {* u% j% K$ L
      tmp=i;- C+ p0 h! u, ]: Z
      while(tag[tmp]==0||!s.empty())
  }& o) R" @; X) A4 a5 `9 a       {3 g) P6 o5 q/ Z9 w7 {
         p=vexTable[tmp].firstarc;
5 H2 I! v7 }9 B0 }& T. B          while(tag[tmp]==0)
         {
, a6 B, ^( J1 U$ k) T/ g- I             s.push(tmp);- K( e5 B* k6 q" h0 d  }" u
            cout<<setw(3)<<vexTable[tmp].data;8 c, }. Y1 U( i' W6 W
            tag[tmp]=1;$ F$ d- ~- Q4 f1 S! R
            p=vexTable[tmp].firstarc;2 U7 f  I! g8 J9 ~  ^
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
- q* }' b; h  E/ ^; S  m/ ]             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);7 {* E: k+ k) Z, y6 e, k& F
            //cout<<" 1st    tmp="<<tmp<<endl;- ~) b# e! D2 m- O; s5 c
         }+ H; u& q' E2 D8 v, E8 k+ ]
         if(!s.empty())
( b  z& ]7 Q# O& Y          {
* O( ]0 w" g. I/ {, Y% C% E8 \% c             tmp=s.top();
) x3 V- z0 o0 Q4 |% ?. g             s.pop();% Z( b  m9 U0 k+ N- B' ~
            q=vexTable[tmp].firstarc;+ A  m/ O1 L, d! S+ p( s* j- q
            int t=tmp;8 r1 [* p' V- {
            while(q&&tag[tmp]!=0)
4 I% W1 L0 ]* {( d+ L5 J# B             {4 M: u0 X7 G. s
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);/ ?) \9 E* t9 |
                  //cout<<" 2nd    tmp="<<tmp<<endl;* d4 b+ n- p* j8 P3 N
                  q=NextArc(t,q);" }1 y5 s* N* F/ {' \  g$ E' l4 H) }
            }
4 l8 V  h* L+ a0 Z5 x- i2 r8 F' ^4 W             if(tag[tmp]==0)# A; H8 M6 d$ ?0 H  b- P( h
                  s.push(t);1 D5 ]$ a4 C+ c) k
            ///1、对应上面连通分支只有1个点的情况9 {; t1 e4 G/ w7 z
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈" b, C8 V1 R$ F" L
            ///tmp要么等于找到的第一个未访问节点，
% R6 a) Q1 C, ?& y             ///要么等于与t相连最后一个点（已被访问过）
5 F6 `" t2 p$ N5 [             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
+ X  R1 w: A1 T4 G, y          }
- Y6 [( k4 n6 a0 h6 }) }, V2 D       }
5 |$ Q  V) G8 |1 d; a; E }. y. Z( O1 e% {( W2 e( w
}
* ~( h" E$ \! Z2 H  y( [! h//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-12 s' @: G1 U# ~* V% b, M; t
template<class ElemType, class WeightType> int: ^5 p/ \( X3 M7 }! J5 U& b6 j
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
2 K. S3 o( r2 h8 Q: r{
  y5 m  |4 i5 v if(head==pre), A$ r# O6 R4 e( m& |
      return -1;& f  x, `- W% s

' L: b% @* i, f MultiAdjListNetworkArc<WeightType> *p;
4 H  Y4 ?  L: B. c% ?3 L% V p=vexTable[head].firstarc;
' V. l+ b. Z( S if(pre==-1&&p!=NULL)
  R! t! E+ I9 Q       return p->adjVex1==head?p->adjVex2:p->adjVex1;2 {6 A0 l: F/ c
//pre!=-1&&p!=NULL
/ x! n5 H5 V- N  k" ]5 v while(p!=NULL)3 e' ?" C0 O  N7 ]. o# ^& X
{
3 I4 V7 R+ y3 e, ]  F: J       if(p->adjVex1==head && p->adjVex2!=pre)" X$ K; b8 y; m6 H+ P
         p=p->nextarc1;) H& J1 z7 ~# a* y4 Z& B
      else if(p->adjVex2==head && p->adjVex1!=pre)
, b$ U2 A  R& a. `: u9 i6 Q1 u, s* w          p=p->nextarc2;  s; `2 ]0 w8 ~; X5 g# M2 x
      else if(p->adjVex1==head && p->adjVex2==pre)/ r2 w! E/ K% R2 g
      {2 u: l- m3 @& L5 q$ n3 b- G4 @
         p=p->nextarc1;
6 M' u; Z8 ]2 X) j1 x  f          break;7 e7 C+ u# M3 u7 r3 w: F7 i- N* C
      }
/ w) S4 ^" o- u       else if(p->adjVex2==head && p->adjVex1==pre)
4 O5 R0 B: m' {/ d7 S9 K6 q7 i! ^       {
1 y  R0 }/ A7 t) ]9 ]8 l          p=p->nextarc2;9 P0 b3 N$ ]( {3 i
         break;# `' O. j) x5 P& Q# Z
      }8 n; Q& C7 t% D. T; k
}9 T* h0 ~8 R, q) ~
if(p!=NULL): d/ V4 [" _! `( c* N
{
. r+ e, R+ r2 t& Z       return p->adjVex1==head?p->adjVex2:p->adjVex1;  c+ C3 H4 R5 f/ E  G. f8 O8 e& b7 d2 ]
}+ Q8 u6 |8 J7 t$ p: [2 x1 K
else0 \0 |* n, B9 D3 t' y
      return -1;3 T0 T* Z9 b0 t$ \9 P
}
# X0 i& ]0 s0 C- y+ [( b- V* I: x- A
. F2 I; c: e" c. M( Z8 \7 |0 o9 o! E$ C, z( U
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()! ~$ f4 p1 c+ k! G5 H2 U2 y
{" L: Z& w7 N% P5 x# o# }0 p
stack<int> s;$ M8 l8 U, e% r1 R8 q2 w+ `
int p,cur,pre;
( g% M$ U- M, L8 Q1 }' ?+ T* ~ //MultiAdjListNetworkArc<WeightType> *p,*q;
: y, K' t9 {, F: f9 {( w for(int i=0; i<vexNum; i++) tag=0;//初始化
, {( r! Z+ _) Z4 w: V2 V. p- g: n
for(int i=0; i<vexNum; i++)% [# c6 e  e* i. F$ Q7 p- ~
{
* q" @7 I* `8 T) A2 I6 a0 a- U       cur=i;pre=-1;9 d/ S& R5 r# t. J2 [" P
      while(tag[cur]==0||!s.empty())
9 g- `6 l9 y9 E% Z: e       {: g+ m+ O" [6 r/ O0 e
         while(tag[cur]==0)
         {+ q; i) |7 a: |7 f+ n5 `1 c
            cout<<vexTable[cur].data<<"  ";
* ~! ]9 b  m7 E+ P) s( z' \1 i             s.push(cur);! c1 x2 p  l0 f" U' T: w0 n! r; e5 i
            tag[cur]=1;
. i0 [# x# M2 ?9 R! y( ~             //初次访问，标记入栈# |; K- _8 B& v$ W

! i0 C! T3 R2 Z3 n             p=GetAdjVex(cur,pre);//p是cur的连通顶点/ b" R% X" O) m4 x& d
            if(p==-1)
2 V' y- R' ^1 d             {
3 M: _9 Z, ^& K3 F2 m! f1 O8 a. N6 y                pre=cur;s.pop();& q. o  D' [9 W: H; I
               break;1 a( l$ Z4 g9 T1 X, ~( A0 m1 T
            }
# b$ U$ L- `+ J" [+ y- I$ C             else5 {5 @0 ]* ]- K0 n; t
            {
' v& D# U6 z0 Q; q( \' m                pre=cur;9 K% L) h3 S" Q5 a
               cur=p;
  d% ^4 ~$ }- R9 X2 f6 N             }) g# q9 o7 S) u9 ~1 I. I& \, D
$ O& J! K  p$ Y
         }
7 v! u- O! |; B$ c% E! @          while(!s.empty())+ n7 I3 b4 l1 X3 W1 E
         {
, }2 ?: U: F1 C; G& X: X             cur=s.top();& Q: j( m0 V% J
            p=GetAdjVex(cur,pre);5 u* Z  F* X/ a$ Z
            if(tag[p]==0)
" F4 w: C; X' ?2 ]             {
7 J7 \8 ]; E0 w# x8 G) ]                   pre=cur;
) N3 z9 G6 S& e9 R2 s$ h0 o                   cur=p;9 v) \( L, q2 K8 ]3 s! \" C- g, t
                  break;/ l' ]4 l- Q( e; j3 Q9 S! S
            }
: `& [, c. U: a, c( q: x; B             else
0 U# ?8 s$ C$ j( t. z+ F! S- e             {- }  O5 U1 j) r7 x
                  pre=s.top();
- j6 a% w# L  A* Q* G/ ?                   s.pop();
2 g  y3 C3 s) K6 H' C6 D  ?' o             }9 ?: s/ `2 r7 y/ U
1 ?+ {2 ~# d* I! w& o6 B
         }
: [. s  L3 _! @* e( T8 M; O9 W9 ~9 l1 h7 f5 h5 |' @1 R3 D6 \8 T
      }+ A; N+ S9 U- w/ T: t# |3 W1 _
}
1 `- D1 R( Y8 {, o" W}# p' \: I& `& u
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS(); ?! T+ c; E! ~; o- Y/ f- q+ W
{
2 t; q9 G# E/ c2 P5 R2 [ for(int i=0; i<vexNum; i++)
9 G2 v$ v5 i) E, e       tag=0;( r( a) G4 f' \' N
queue<int> q;
- W9 z8 j# w' E& p int tmp,t;" W0 W8 R- D8 I- F/ A- ^
MultiAdjListNetworkArc<WeightType> *p;/ X7 X2 o  E8 q# d& ?  m  q
for(int i=0; i<vexNum; i++)
: D9 G# C) M1 l: i1 v6 H0 R {2 e! t. s& A1 c
      if(tag==0)' Z% c! E  n+ w# o# o5 ?
      {( V/ N% l/ Z. D5 q1 z6 n0 t
         tag=1;
6 D  W3 O: E& e  M          q.push(i);
' y" q+ r$ F, r- n: u5 I          cout<<setw(3)<<vexTable.data;
2 j) ^* q% P, L8 t       }0 t/ i( H$ g" I& u1 z+ ?" L
      while(!q.empty())
0 j+ n8 n3 z) y       {
" r3 y1 W, I# Y+ N, i          tmp=q.front();
, ~5 w- p( ?- v! g          q.pop();' T) L' \$ O) @, M" R3 t# m
         p=vexTable[tmp].firstarc;
6 \  Z. J( }6 l: A+ @- y* F          while(p!=NULL)' u0 @8 D6 g* v9 J$ ?
         {
7 u$ ^: g) J# E2 t% h+ _2 i7 G9 @/ [6 I             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
+ e7 c( B& b1 i  ]3 r% ]' g, f             if(tag[t]==0)3 Q. i" ~  p* L8 m' `
            {
, t5 k* e8 j% U% t& t                   cout<<setw(3)<<vexTable[t].data;
+ K' D: J, ~3 Y( J& D                   tag[t]=1;
; l& t8 t* v5 Z  @                   q.push(t);  P+ z1 \/ C$ Q, ]
            }
" F! }* s5 E& D8 c1 T$ v) k( v             p=NextArc(tmp,p);2 h+ b- \8 W' h# j. L+ \$ {
         }2 u3 V- |0 i1 k! z8 V5 Q$ S
      }
4 Q) {" c  y# t  c, L }5 D" L! v+ V  e  b! T& I9 z
}
" e. ]) i0 u( y: @# L( G; R0 H4 xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
7 C( t- [/ n% `, Q{
) D1 g0 i2 n/ g4 N MultiAdjListNetworkArc<WeightType> *p;
; e) R! t( n  P7 ]* c8 ^; h4 F% N: n cout << "无向图有" << vexNum << "个点，分别为:";
( v; B* m+ y5 c3 v+ F: F0 @5 ? for (int i = 0; i < vexNum; i++)
# `# B4 U) P0 u  P# d; U* F  z5 x       cout << vexTable.data << " ";  G0 H8 ]4 h3 |3 O' l9 _# Q7 v
cout << endl;) B" n) u+ r9 _% O% m5 D- }
cout << "无向图有" << arcNum << "条边"<<endl;
- q; @: Y' h/ K for (int i = 0; i < vexNum; i++)
0 T" f: v! t& W6 B {
) T3 A8 K8 z! F2 Y       cout<<"和" << vexTable.data << "有关的边:";# i* T5 I9 t& L
      p = vexTable.firstarc;
; q; I% F5 ~( b4 x6 K  `- J; p       while (p != NULL)
4 a0 R7 a" f: M' l- A       {: E; b) i5 w& k8 h
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
0 f1 i4 v8 u4 ~: L( O7 }          p=NextArc(i,p);
; L, M) W" J) w  Q       }$ C2 k/ {$ D# q/ V( k% \' H2 H
      cout << endl;2 C$ P# V; R6 a( D0 l7 g
}, K- R! h* h3 x7 b0 c. D
}  v9 `6 @8 p; N. ^( G" Z
6 G# ?% z: `: N# x+ }; r1 i

6 Y( @6 {3 J  t% ^' @邻接多重表与邻接表的对比
1 Z2 z( l+ [  I) B/ @
5 {9 @" o& G! Z1 o$ l邻接表链接- t( M) X7 F$ }7 q7 s* k) g7 l
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。! E5 R, \/ D* ^" g
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。& m# W8 p: ?* e" R5 p/ f+ I
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
. v2 {0 s  L* e  J3 b( @————————————————6 [8 z% o" E. Z4 q; G$ R& V7 Q
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% C& f, E: G# v- \- B: O原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958& T  {: l9 K5 m% X! s

( j/ ?! c3 o& {
7 g2 X  I3 m" u
$ s# i: [0 N8 M' h& A4 Z: M& e6 d' r  i! _  \3 F6 |& D# t# L. `
————————————————1 m+ N( I2 ~3 j  r) {0 H4 e
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, z) d3 s! @0 g# a  {& F原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958- ]! a: P; d$ u

, n9 r. \& z: E) n6 i! t6 ~0 n8 y  n! k! m+ q# n& ^& z- p