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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：% U4 f6 u# O2 f& Q* ?
data域存储有关顶点的信息；; B0 E' M- e" y
firstarc域是链接指针，指向第一条依附于该顶点的边。& i: Q% |! Y: r+ [
所有的顶点结点组成一个顺序表。

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;
$ T" f* A1 I- H/ g for(int v=0; v<vexNum; v++)
: c* S) N) ?, d. C8 e0 [ {
5 s4 C" e# |- Z# B       if(tag[v]==0)1 m" H% R) e& s- ?8 G$ y5 D
         DFS1(v);
) ~. c, C- M9 }# U+ n8 z }  |: m8 [/ }0 Q; x4 R+ X% Y+ y7 h% @
}
  }4 E* n2 a' mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
8 N2 A" X6 J6 b% h& C' K{: L2 L) e/ S8 E8 _2 _: u; ^
stack<int> s;: ^/ y! ]4 }/ `
int tmp;& u( D2 F% W% b# E; |! N# U1 _
MultiAdjListNetworkArc<WeightType> *p,*q;" d0 l8 }- D9 u9 B  o8 M, w
for(int i=0; i<vexNum; i++)
& V( Y! v; [0 y" T  A       tag=0;
3 T' O) E0 R+ G, Y3 [* r3 y for(int i=0; i<vexNum; i++)
' K1 m0 H8 V% Y" {) r {% O( [+ F: b8 p3 t2 R
      tmp=i;
) X0 G9 ^6 I' f( E+ D$ ^" \, ?  M% [       while(tag[tmp]==0||!s.empty())5 i: j- V7 b5 j, F1 n
      {
. R) a6 A4 W4 _3 T! ^: l1 s" E          p=vexTable[tmp].firstarc;4 R: d4 ^; h! i% Y+ V8 e3 B. T
         while(tag[tmp]==0)1 d, Y% g" n  Z1 ]0 o' U: s7 `
         {$ N4 Q4 f8 ^' ?! u
            s.push(tmp);) k) ]1 c( T! h$ a+ Y8 A- Z" c8 X
            cout<<setw(3)<<vexTable[tmp].data;6 K: S0 L  V& q: I+ Y  |5 B9 z7 q0 V) l
            tag[tmp]=1;
" y+ U/ M! K, e# r             p=vexTable[tmp].firstarc;
0 g/ E; W0 ~0 j) N: F/ v. Y             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for! f4 ?; o# v2 ]" _/ n
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);  U0 U: \5 ?, P+ f
            //cout<<" 1st    tmp="<<tmp<<endl;
0 k$ E4 R# e7 V+ z5 Z2 w          }
) B" W5 z/ F( t- l" S) r; ]          if(!s.empty())6 H, I: O% H! F) E2 b9 K' @
         {
$ G5 i) N0 _5 Y, _$ K8 y  R             tmp=s.top();
& O  ~7 k8 o& K% `             s.pop();
8 `& @0 Z6 K4 L- @: S2 i             q=vexTable[tmp].firstarc;
8 G) p- @& l9 {! z7 d             int t=tmp;3 ]/ _1 A& C" z' p, f1 h
            while(q&&tag[tmp]!=0)
+ y) R# ?9 M* O: ~             {9 {$ @) f$ }3 W. J" H" S
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);# d1 v4 Q  E, Q5 F8 L
                  //cout<<" 2nd    tmp="<<tmp<<endl;" ^; }; a, E! w) }. e$ M" r5 r
                  q=NextArc(t,q);, q" V3 L" _  e: u/ u
            }
' ^+ }; z( D, G             if(tag[tmp]==0)1 P+ c2 y( }; m1 i6 n" i8 |
                  s.push(t);  t) T: n0 u4 w6 a8 ^) v. \# R
            ///1、对应上面连通分支只有1个点的情况! t5 C$ `( K5 k
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈8 }) v$ \- L" i0 ~+ G3 F* o' _/ P
            ///tmp要么等于找到的第一个未访问节点，, G5 C& r9 ]% R1 K; j/ _* R3 ~3 j
            ///要么等于与t相连最后一个点（已被访问过）% Y2 e- S, j( W1 c% h* P) U  F
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
* q6 Y. h2 y1 X6 I* r$ w          }- I8 R' @: M  f5 N6 @( {
      }
1 h& X% `# S+ K' C7 a# Y+ a; Q }; W# K0 c9 F# ]: j
}# K1 U, L- M3 m# v4 h. s
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-16 w: f6 a/ a# P, ?
template<class ElemType, class WeightType> int6 b1 A& I& e, h, R' _3 ~
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
- v6 ~5 f" \: O; i+ u! W0 \{
* p" |# C* x) s if(head==pre)8 X, T4 i/ ?: `$ w( A$ e
      return -1;  j+ k+ `/ k4 G4 `

# H  Z2 v6 Z/ F6 U) U5 x MultiAdjListNetworkArc<WeightType> *p;* a$ l9 X" k% s2 h7 u' e$ l' i
p=vexTable[head].firstarc;8 f. `( e7 G  k5 k6 L9 Q
if(pre==-1&&p!=NULL)1 k) i8 b. T/ E! H: {
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
# ?+ i  i4 Z8 J3 U7 V //pre!=-1&&p!=NULL- I* [7 ~) G. H7 I3 G
while(p!=NULL): O! `% X+ h; F  H
{
# R( m( b+ G/ r8 b       if(p->adjVex1==head && p->adjVex2!=pre), ~8 A" _7 B8 [: {( W) @
         p=p->nextarc1;7 O3 e" {4 [; K& i9 g
      else if(p->adjVex2==head && p->adjVex1!=pre)
! s- [  t7 L) Q/ `4 ^: c          p=p->nextarc2;$ V. I$ F/ k1 G4 f$ |! A2 {2 d2 B
      else if(p->adjVex1==head && p->adjVex2==pre)
% {/ T  D- |+ f: W' o& @2 A. }+ G9 n       {
6 F- o6 {4 K4 q          p=p->nextarc1;; l/ d% \; Z" V) ?; C' m- x3 P
         break;
9 @# h. j! ^6 k; C+ @       }6 J9 x: G9 S/ ]3 P8 |9 u* {
      else if(p->adjVex2==head && p->adjVex1==pre)
' s3 W9 v# f: |, `  [       {& K, _4 |4 s, L2 p
         p=p->nextarc2;
) w: h& b, N% |; t, I! A          break;. X$ g, Z1 `. z# f4 u4 D# o: R
      }9 T+ n; f4 \* h, }! n( J
}
: G0 |4 z: ?  a/ u$ \ if(p!=NULL)
9 x' r  b. {2 W5 ~* T {
3 a: @' c. A# ]9 {7 H/ X$ K       return p->adjVex1==head?p->adjVex2:p->adjVex1;
! h- y6 p* \0 S- C! S+ C' n }
" |; B& s( j& ^6 R+ [/ R  k$ C1 t else% H5 e  g' f. l
      return -1;
+ @- n4 P; g7 n6 Y}
; ~( |: ~& J, a0 n- e: M# \
0 Z# |- @8 M9 S+ y" X/ r/ }% f& \, }, M; Q
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
( p7 q# G  a) l5 @5 s{
% H! w: A7 O$ \: ]1 D! j  U7 X stack<int> s;1 d0 A" H. c* C5 {* Y8 {% N
int p,cur,pre;
/ v& S+ O; x% c% ^! F( Q6 R+ A- v //MultiAdjListNetworkArc<WeightType> *p,*q;
7 ]/ l, J. }, g$ n; J5 N6 }- R for(int i=0; i<vexNum; i++) tag=0;//初始化
1 m7 M! z( o$ c, ^
5 ~9 e* f  Y' ] for(int i=0; i<vexNum; i++)
% C. n3 h1 d5 @" s {
: b2 l! {( T! t9 ], k& |- ^5 Z! B* r( j       cur=i;pre=-1;0 }- j5 X! f$ @: F' @: I  j
      while(tag[cur]==0||!s.empty())# d" }4 |! i+ s( Q6 \
      {
  h- c# T/ \' b          while(tag[cur]==0), A& z# |7 [8 \) T
         {
3 a! F. o$ k  l3 J3 ~2 a             cout<<vexTable[cur].data<<"  ";
/ }5 W- w7 O2 d4 n- g' J# A             s.push(cur);
# G5 d; L2 S6 }1 z5 M9 n1 g             tag[cur]=1;
7 z8 ]+ M7 P% V" S/ S& f             //初次访问，标记入栈
9 O5 t: z4 `' J2 H; L: X: Q) ~* ^( x
: O( ]) u7 d* t* }, r: w* m             p=GetAdjVex(cur,pre);//p是cur的连通顶点
0 ^; j; J$ e) x, ~  @: l- t+ N             if(p==-1)# h4 F2 u$ [/ o0 F4 ]2 \
            {. D, V, v# r" M( o
               pre=cur;s.pop();
7 U9 P1 b1 C+ L                break;
- F7 u0 g. b! w7 V9 T- k+ R             }" T7 D* ?3 ^* J, ^) S7 q
            else# y- h" }+ n" d8 L
            {. d$ s: M1 B6 E
               pre=cur;' C2 N. k  w; H: T
               cur=p;* s' a( O1 f: n9 V& u2 f. [. [
            }
) n8 [) }+ O" Y, s- ^. j! s) `- f) A' U6 p
         }
) }9 c8 G4 M; i% a' ]          while(!s.empty())8 N- L  P. F& I/ p
         {
' }* @& [7 H+ h3 A% a' U             cur=s.top();/ U# f( _4 c% H9 }
            p=GetAdjVex(cur,pre);7 Y5 t5 o1 `  B2 c* S9 i5 P* {
            if(tag[p]==0)
5 |! e+ y# h( I" t4 ~             {* d9 ]8 W9 n, `
                  pre=cur;7 R, }4 E/ W7 g/ x
                  cur=p;
# I  }  i+ u8 J" c6 i; `                   break;
+ G8 b8 i; {. L" g1 ~1 ~             }
# i& D# ?: t( E1 r$ f, S             else
! |2 c- m4 f3 y2 i1 a: H             {
0 \5 B2 h) o( g                   pre=s.top();
8 E! N7 e* F' [& s6 F                   s.pop();
- G- s( {, @0 F             }8 m% h, [' T% f5 F* R+ K
( s) E. E$ [; f9 a, K( {; i& p
         }
; p6 Z' q" X  @) @( I! J. t
5 D* z" |, t! k; m. G       }
$ c9 X- Q2 ^) h+ _9 S }- \% I5 }4 Q/ D7 @4 B
}
# ]9 c& I  P( X2 L9 m. g+ }template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
& Z" i. ~# q+ J8 [0 ?2 K8 I{
  K8 D' C  A" C. X& C/ J0 a for(int i=0; i<vexNum; i++)# T5 U: m2 @, j/ F! D+ @9 g
      tag=0;
7 Z2 d% m) p& K: g queue<int> q;; J, Z2 N- H% q: e" h( F8 f! |
int tmp,t;
1 Z2 f2 y8 h! V! \  i  u5 {$ x1 C MultiAdjListNetworkArc<WeightType> *p;  G# k3 b$ f0 a' q6 G. V/ t$ g7 U
for(int i=0; i<vexNum; i++)
7 E, U: r6 d5 i1 L1 e4 a" W {1 t# i$ [; Z/ R1 e1 B1 c
      if(tag==0); V4 x& }3 f- G4 p/ c: T7 z
      {7 `* Q7 `9 f! J- {5 S2 M; v( r
         tag=1;
1 Z9 b- Z$ x  p# B5 g$ r4 ?# ~          q.push(i);
; \8 w- ~  _9 \/ W$ L          cout<<setw(3)<<vexTable.data;
& L6 J$ Q8 ~. E- Q       }
, R. H8 \2 V- a% O) D. W       while(!q.empty())
( C" _/ e) ]/ `6 v8 _6 k. U       {  t. m8 J# a/ R, F- G% ]% K
         tmp=q.front();
+ A7 d8 e  E; X: y8 [& B+ K          q.pop();
- f" n+ ?* m, p3 k6 F  S          p=vexTable[tmp].firstarc;; x1 Y+ T" L: t( h  \
         while(p!=NULL)  p4 F5 A, n& S1 a5 E3 M# W" c
         {
0 w# s6 a; m0 L8 H4 L             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
8 C  K3 y0 a9 E+ F, v5 b             if(tag[t]==0)
5 D7 M' J8 t2 i; p9 k             {
3 J3 X9 W% X( G) {: R5 q0 s+ A! U                   cout<<setw(3)<<vexTable[t].data;
' m* n8 D6 I3 i% {# k/ B6 f2 U                   tag[t]=1;
% A+ y$ a+ Q1 M1 R) Q                   q.push(t);
, E& S$ O* X3 s, l. L             }" ]0 }( w  i1 C' K
            p=NextArc(tmp,p);( v  [2 P: ~. }7 r
         }
: j* f5 `) p1 {3 M- S2 |0 y/ C       }
% m6 i8 M* t# Y& A }# ~8 d' Q' Q6 {
}
$ J# `2 z! u( W8 i% Ptemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
* n- y' O$ p" Z6 @& t2 M* O{3 R" }, _; i' y$ |
MultiAdjListNetworkArc<WeightType> *p;
  Y6 B$ A% ^: Q' q9 ?; n0 J cout << "无向图有" << vexNum << "个点，分别为:";
9 B% p, k1 V0 c for (int i = 0; i < vexNum; i++)
7 a' e" I( E" ^8 q: m/ e; C       cout << vexTable.data << " ";' S3 ~9 A0 l: S! K! q3 M* ~: h
cout << endl;! u% _/ o1 Z& K7 ]' y3 a/ _# c
cout << "无向图有" << arcNum << "条边"<<endl;
. e! B' \$ e% ? for (int i = 0; i < vexNum; i++)
) H# ?3 q8 z6 ] {
3 ^) V1 Q" U6 ~8 k1 Y4 W       cout<<"和" << vexTable.data << "有关的边:";
) U. C% Z4 E* M" V# C' V# g  Z7 K       p = vexTable.firstarc;
' O$ @2 i% W& X& v$ x       while (p != NULL)# y4 {. ?6 h# T4 h$ |: r4 N# k
      {
6 @  p' g) q2 J3 D6 a          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";  |; a! q& o2 n+ u
         p=NextArc(i,p);
+ p1 B+ q" Y$ _8 ~* ?       }! K3 g* K: b3 ^5 Z" q3 j
      cout << endl;; M$ I- }) d4 Z2 P3 \
}" P( P4 O  C( _
}
% R8 Z: e% Y7 u) e& F; n
& }9 {( Y2 W; X  b1 n; d" A- o& _
0 W8 X# p& @! X) j( K. I# l% v邻接多重表与邻接表的对比
  b( o& D# b9 f/ K5 j4 Y  o' \- {& A; B( [7 B+ q
邻接表链接
1 f6 X, B) ^* z( p6 P在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
- _$ P, W! a8 Y0 `; o! K1 v在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
/ l' x! `0 a; J' R9 c; [9 M9 @为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
9 ?# z9 {% u! |, L# U————————————————
( Y* L- d/ a* ^; Q) l% D% }版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。% O* D6 y3 |2 J3 N
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
7 v2 K# `' u" \$ G
- N1 d9 H7 N2 D& ^, H/ `3 H4 ]7 l, C

6 Z8 v  K9 ]0 V' F' \/ i/ s7 c4 S* f6 @! c8 Y5 b
————————————————
6 F: z! e' q& f! Y版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。% B) r2 |8 `5 n" _9 h1 t  U- m0 X
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958# X0 g, e. X  U" @) ]

7 k' V8 r9 J# [' @1 c& h, m
: W; j: P$ q! d, ^5 r  v