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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：+ r+ E6 A. ]5 M/ j
data域存储有关顶点的信息；
b" J' _% H, A" s8 xfirstarc域是链接指针，指向第一条依附于该顶点的边。: {% [/ j8 N7 u
所有的顶点结点组成一个顺序表。

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;
4 R* M$ A+ N* L$ U+ A" `6 z4 B for(int v=0; v<vexNum; v++)
2 o7 Z) o! n+ }9 P- v2 l0 o7 B {
# X3 p0 H2 `  H$ R       if(tag[v]==0)1 ]2 M1 }! l! |0 [
         DFS1(v);9 }) z  n0 }* x& Q; H4 k$ v
}
0 s3 F* k/ z8 I$ ?% M  M, K}
4 S3 _: ?8 o7 o1 K8 p9 Ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2(), m) a- g( @0 e3 ]! b) g
{* w& h! Z9 j+ i, A3 v: `
stack<int> s;, [% y( j; r* U5 [: F. z& ]
int tmp;
# _0 h- {. p- f3 A MultiAdjListNetworkArc<WeightType> *p,*q;
1 p3 B; u6 U% D& M0 B/ X( J! q- `8 { for(int i=0; i<vexNum; i++)
; x  m5 s% _8 Q& h3 v% I* ^5 k       tag=0;
2 R7 i" A8 C# E: H for(int i=0; i<vexNum; i++)
  R! m6 b' C' t$ Y; x {" l. z# V, ~$ T. ^' F8 g: Q7 _0 t
      tmp=i;
9 z; H0 $ L+ ?/ `( ~       while(tag[tmp]==0||!s.empty())# x: F3 N- e2 b! Q/ t2 d
      {
' Q# M3 h5 X7 [' `0 b2 x; $ s          p=vexTable[tmp].firstarc;
1 }9 o$ v0 \! |/ O          while(tag[tmp]==0)
/ n- Y7 J7 s; }4 I8 s- i3 u          {6 P4 e/ C: M$ [$ z) Z* K
            s.push(tmp);: i5 |" ~# G; p- T
            cout<<setw(3)<<vexTable[tmp].data;8 F* c# i0 a- T6 Y9 M2 e1 O
            tag[tmp]=1;& g2 V( t" R' h1 m3 d, _$ \
            p=vexTable[tmp].firstarc;
. W2 i: A: _, W2 ]# A) J# K             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for( v$ p: z4 i2 G# i$ C' N+ b4 L
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);1 ?6 h+ P& z( k5 s
            //cout<<" 1st    tmp="<<tmp<<endl;7 o4 J1 K# n/ J8 E5 u) y
         }
, A% L3 E# q8 F          if(!s.empty())7 |2 o; A$ H: o5 {$ h
         {
; r# h. p$ W0 W- ^5 c: E9 q( C             tmp=s.top();/ z3 |0 h0 E0 J; s# \
            s.pop();( o3 H0 U  \) h  c
            q=vexTable[tmp].firstarc;" B' J9 ]8 L- m: n4 O$ f$ J
            int t=tmp;; v( i) k! s; [( c0 z8 ^
            while(q&&tag[tmp]!=0)! t0 r8 b/ A* Q; N4 ^8 z) S, e
            {
4 Y) b- U' m0 }. V9 Z                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
  p1 t2 u/ R6 U" Z3 n* m8 q% F                   //cout<<" 2nd    tmp="<<tmp<<endl;
; Y# v3 ~& u4 f                   q=NextArc(t,q);; t2 P% h4 G) e  z1 G. d! ~( Z
            }1 F' \' e8 M. k
            if(tag[tmp]==0)% @/ ?. E. k; q. P
                  s.push(t);3 v$ n% S1 E/ m4 f3 R
            ///1、对应上面连通分支只有1个点的情况
! C* {; j# x5 T+ o5 C  e             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
% v6 m* Z1 \6 z& @; m  n             ///tmp要么等于找到的第一个未访问节点，- H* F  T# }- D) c8 V
            ///要么等于与t相连最后一个点（已被访问过）
, E' `. l5 Y$ T) M  ?& v: g: o! C             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
$ B2 }& H' V/ P8 k0 X* F          }5 u, K2 {  O: K; W( J3 f1 N5 P
      }
/ l: e2 ^; t' \: q }" o' H4 E& q% C5 z0 j( B) S
}
  y7 v$ P- L. T6 }  M$ ?" p//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-13 M9 g) ~0 m: G2 s2 |
template<class ElemType, class WeightType> int1 O4 q; b3 |- Y* V
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
+ ^( G/ J+ }: ?$ D( {{
+ U, u- V  @9 @' B if(head==pre)8 n$ G7 [8 o3 E) r9 y
      return -1;
% V+ n, _7 D1 {4 E9 O& D4 _; a7 U
/ O5 t0 g2 ]$ B8 r5 U: |# J MultiAdjListNetworkArc<WeightType> *p;
$ E1 c  Y! ?. G) X9 y  K p=vexTable[head].firstarc;
8 I* A% h2 N5 M- V8 p6 |+ @ if(pre==-1&&p!=NULL)
- U/ e* B! ?& O       return p->adjVex1==head?p->adjVex2:p->adjVex1;
5 ~4 Q: D; ^( y4 {% B //pre!=-1&&p!=NULL
: ~8 q) N6 g8 h6 h/ E' z0 B while(p!=NULL)
0 m' X. Y+ {" ~" w" Q, Q) P {/ i  g/ O- e/ ]' {9 H
      if(p->adjVex1==head && p->adjVex2!=pre)/ R4 Y5 }1 C. ~; n4 j
         p=p->nextarc1;
3 [6 e9 a" r  m       else if(p->adjVex2==head && p->adjVex1!=pre)
0 s% [# V9 V- F, k          p=p->nextarc2;
1 k8 ?. Q7 d' v4 d$ z" i       else if(p->adjVex1==head && p->adjVex2==pre)
% w. g! Q1 ]+ c* @9 G1 b       {
4 Y8 Z, J8 n% a: }0 `! {( A  O          p=p->nextarc1;9 V* r  J) a* ~
         break;
+ h/ P5 \1 U  t, R6 O& D- y       }
$ A4 Q* v5 @3 B% H# m       else if(p->adjVex2==head && p->adjVex1==pre)
% ]" R3 X5 y7 b* g       {* N) M$ ^" n+ e5 r% _$ K; d
         p=p->nextarc2;
% _; i. p- t% |' F          break;
9 u# K& y# r4 ]. Z& H& F$ g0 Y       }5 c9 ?) S! h* J0 Y
}; p/ S+ m) p4 q. P' @; `" W
if(p!=NULL), @" u- N+ m( a. U( d
{2 C, t4 F2 F  U. A
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
! n. v8 y5 \5 C" ]5 Q3 O* R }$ |" Q! e$ r. ^0 b; i- }9 {) J
else
2 |) i8 v, d, p' \; e1 [% i       return -1;& W3 w8 ^2 R0 F/ ^- N, X5 l
}$ i7 A9 g& |9 O" O
' c) D& t) g1 o% V
2 h0 W# L# ~- {1 A, h# _
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
' w- D' E! a# w! S( Y{5 R' X8 L! B3 r* l* x5 X2 @4 g; k: O/ j
stack<int> s;. p+ p1 h' R  ~1 ~! T
int p,cur,pre;
1 h$ t' b& _4 s# h //MultiAdjListNetworkArc<WeightType> *p,*q;
& ]" `$ V) R7 z% a) [' `0 X for(int i=0; i<vexNum; i++) tag=0;//初始化! J. E: l+ z. G
! d3 n5 L0 r; @- i
for(int i=0; i<vexNum; i++)8 Y) G& t% u; q. ^' R+ q: H
{
( r' W1 r. {3 Z6 k. I8 d       cur=i;pre=-1;" G5 f: Q! @+ x. O! G
      while(tag[cur]==0||!s.empty())
2 Y3 E/ P: b% k* y+ ]       {3 G3 P8 h0 `2 O
         while(tag[cur]==0)
4 W# J- H; c- I          {
6 W# y8 g) j. M1 D, h( c9 J8 [             cout<<vexTable[cur].data<<"  ";! H% y* x$ e, k  j/ H- Q- o0 V; u
            s.push(cur);
, d1 ~/ N) a+ _             tag[cur]=1;
5 s7 }7 }4 {* U; P) O             //初次访问，标记入栈
) {% Y+ F, P8 A- I$ T# |# \  M
0 U8 @) r6 N# F+ s! w             p=GetAdjVex(cur,pre);//p是cur的连通顶点- o% f, d, J# R# h" c% Z
            if(p==-1)
, E  Y3 b# ?' I' ^$ A8 y             {
% E2 w& v: L$ m2 ~, M" z6 T                pre=cur;s.pop();
/ q$ v/ v' Z# z% T2 S: V8 ]                break;, M( N, K0 ~* |- ^1 o4 `! J
            }( B* w0 p7 w& S1 X! |3 N6 |
            else/ C7 }- ]8 b0 K+ F
            {/ p3 i& c; a8 T  j
               pre=cur;
0 H7 C3 k$ _1 h2 Y; _9 Q5 x# L. k                cur=p;+ f4 Q' b5 F: Z
            }
7 o1 a$ C. K3 y, n" A! P
+ T2 ~  D% j  j% A7 L  x$ J- D          }+ Z4 n* |$ w" M* W
         while(!s.empty())* A1 o3 j6 o. B/ H) Z$ u# g
         {! N2 U& c  C5 b- A# V+ m
            cur=s.top();1 z' |% D  b3 }* M, M7 M0 z
            p=GetAdjVex(cur,pre);
" L" n& r2 C9 V: P             if(tag[p]==0)
# J. ?$ j, @0 {$ J; }0 w& k             {
7 v4 @3 L0 M5 e. W8 q2 x+ j0 t: r                   pre=cur;* [- T' I$ p' x# u# I& s
                  cur=p;
+ m& d8 s: m7 X                   break;
$ _4 G0 t0 h# M# N* W             }
1 k7 c# E3 Y- T+ p- F. b' r             else+ M; v" R' `2 L# j3 D
            {+ k0 y9 v. A% X1 Z1 V; A: Y9 Z
                  pre=s.top();$ N4 v) j1 n: E( d8 D: c$ ?
                  s.pop();
& O4 ~8 h' K) }4 V* g             }
  Y, A5 k* O' h, O3 z1 ?4 S( E) M$ Q& W& N7 j
         }
' q1 H  \/ A3 t, p
% L) Y' X% B) g- I# U) j( a       }) x* K5 u- l) V- z0 C3 u8 Q
}
. G' ~0 l) L& p% ~$ }}8 A6 O: v* y* Y: y' S& i
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()1 a* ^# ]) s. ^4 i& L
{
& F" j2 b; N% Y; D7 B3 c for(int i=0; i<vexNum; i++)! d# V6 `: I; ~0 i6 u8 c/ h
      tag=0;: t* D# R2 }% U' n0 M' c* }- s: y
queue<int> q;
1 V9 k' v/ v8 m! p int tmp,t;
9 F: A5 u0 c( s, L6 a MultiAdjListNetworkArc<WeightType> *p;0 N- G# }$ X  z4 e- g2 R
for(int i=0; i<vexNum; i++)* I2 T8 l3 l7 C5 k8 ?
{
7 N1 r7 q' f2 J" r' Q' _+ r! }       if(tag==0): X- g" g1 ?5 G- E7 A8 _
      {/ q; X( T( g) [6 ^+ E1 T- c) }
         tag=1;
/ Z! V# @. C' v" ]; [# g" e7 G) X0 V          q.push(i);' X: V) [/ A$ y. K
         cout<<setw(3)<<vexTable.data;# h2 \" l- V) s
      }
5 v" c: ~1 ?( L+ F* b       while(!q.empty())
7 Q" r2 w; Z% P! l" w/ M; W       {
0 W0 Y) d; J3 R          tmp=q.front();0 g9 N2 T7 b3 w
         q.pop();
. V! d+ |- A- K( i& u          p=vexTable[tmp].firstarc;
3 A) s! W; t1 U! }- D          while(p!=NULL)
! e, m; X; r  y* D          {" W( s: j( _! y  r! M
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
. s5 n- v) x0 X8 P7 [) u             if(tag[t]==0)
! P. h. b! t, p3 K3 l' P- W3 u             {
! X1 {! Q7 S! K" `& f  T                   cout<<setw(3)<<vexTable[t].data;% q9 j  Q- g5 p# C- k8 s. \5 {+ v
                  tag[t]=1;
1 l) i7 R/ z  [. \! |  S' L                   q.push(t);
2 P! w0 n' q; b             }3 H" c/ {7 I- N8 V$ @4 ?
            p=NextArc(tmp,p);
) |1 J5 a9 `& t' K, r% a( \          }
8 t# U9 s5 s% D$ T  n$ ~       }$ i, F* H7 p7 ^9 G' [: n
}( U: x7 W+ I! I0 b# J" t5 c
}, Q& ]2 [3 j% R
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()+ {. m" f, ?0 C- I2 p* t% x" i
{3 x/ @9 ?% v+ p7 e
MultiAdjListNetworkArc<WeightType> *p;
7 l4 E  X; p( @& o cout << "无向图有" << vexNum << "个点，分别为:";; B3 ?6 v* C9 v5 `3 R! G
for (int i = 0; i < vexNum; i++)4 P5 v0 _% B" R
      cout << vexTable.data << " ";
7 g9 _4 o& u' U cout << endl;- T1 U* _& Z' Q- T/ i6 o
cout << "无向图有" << arcNum << "条边"<<endl;
% |2 `# l( p! |: F for (int i = 0; i < vexNum; i++)
% {* y& \7 h  ^& ?# x {
) f, B0 [! ?, _7 \. @       cout<<"和" << vexTable.data << "有关的边:";0 i8 s9 r3 ~' B, g" D
      p = vexTable.firstarc;
! j& P+ n& u2 L' |: H$ ^# X4 |) I6 ~       while (p != NULL)' q* a+ w0 s0 A  V% U
      {+ H5 I3 I. S0 _: i$ N& t8 s( x
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
& C1 V3 Q. Z7 N: s: ]5 p          p=NextArc(i,p);' d; X! f* L# M1 ^4 @5 K
      }$ q3 r2 }( k1 ?1 s0 [* k1 |. \
      cout << endl;
6 ?- ]9 [; |% z; i }
4 N. l( C- D: v1 W}+ `; j8 b: ~9 h) t
  j$ E  ^+ {5 {

9 Z/ e+ O! O6 h* }9 y+ x邻接多重表与邻接表的对比+ w: b4 a4 e$ k: X8 }

( [1 S1 `: E: k9 b) b2 S- J邻接表链接- ]  {0 @, Z% n4 N) q
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
  {3 Q: p; u8 o4 @- L, P在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。8 }9 {+ x/ ?7 f* T4 P. O
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。/ n: |0 }/ l3 g8 p
————————————————
1 K+ K& U: z0 c4 B版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。3 m9 ?+ C: y5 L+ k) s6 T/ n
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
( e/ y0 d! o; f1 P9 n: t! E5 R
2 l, r. g4 t$ W0 c! q4 x, a/ X% y) q; V1 w% ^
9 j7 n8 a, p8 B2 p0 x2 p: e

* Y# N2 I, Z7 V4 t————————————————
. U% z% J* c" m' i) ~  @版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! w3 G0 ]$ d( j: Y. I' p( ?原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958, G. R( p" y& p; m' K

- s+ w! O9 v$ X; ]& c. A: c& l7 h+ ], `* I) I