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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：4 {% `( J0 H; j$ ?4 `! ]
data域存储有关顶点的信息；
* j& c j& W, V5 H2 w, Z: b2 Afirstarc域是链接指针，指向第一条依附于该顶点的边。. l$ w+ e8 |2 X3 m" u& N$ C6 I
所有的顶点结点组成一个顺序表。

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;/ F* w6 I, @7 e% Y( v( d
for(int v=0; v<vexNum; v++)5 C  l& \( O7 I- L. g5 J: d
{
/ D8 K9 t% C9 F' d. Q* Z" m' _5 H- @0 S       if(tag[v]==0)3 F7 H  r: G- i! L& K
         DFS1(v);
, E$ {$ g2 h! r& P }/ e" Z; k. _! V2 C+ S- `  E, S1 V5 F- d
}$ j; ]# T5 Q2 ?/ v
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2(); ?6 Z6 E: @  ^2 m9 P$ ?
{& J4 I, d' @& R  w! U1 ^: W# x
stack<int> s;# ^1 T' `9 p  @1 {
int tmp;; a& Z7 x. E  |! v# p& R  T
MultiAdjListNetworkArc<WeightType> *p,*q;$ G8 F0 _& S$ y. x/ A
for(int i=0; i<vexNum; i++)
9 T4 J* z  V8 I8 ^+ H       tag=0;" K. i% F* T; T
for(int i=0; i<vexNum; i++)7 p. U9 m) V0 E
{
, R8 Z7 A6 c. N- p: `       tmp=i;9 h* c, N0 ~! o$ o
      while(tag[tmp]==0||!s.empty())/ a" i7 h* d/ N- N
      {! Y  O1 p9 l, }" N) J3 |
         p=vexTable[tmp].firstarc;/ ]. t$ g1 q" D/ [: e; I
         while(tag[tmp]==0)! @+ {& r' Y" c# N% D
         {
' n; z& {& u7 Y: E             s.push(tmp);" r# V, d3 q3 T4 m$ V% A: m8 f
            cout<<setw(3)<<vexTable[tmp].data;, Y9 a2 z: {$ U8 e
            tag[tmp]=1;
7 T' b3 M8 g5 b$ x, M             p=vexTable[tmp].firstarc;
# U6 O: ?0 V) M: Y9 w+ `             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for6 S- F; L; R+ i& I5 o* v
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
' p# o( X! C9 _3 a6 \/ F3 ]. x             //cout<<" 1st    tmp="<<tmp<<endl;
+ S# C4 d/ {6 V6 P          }& [' M& C, I! E  g7 j' N5 Q  i
         if(!s.empty())
6 u+ A! m9 c" E. d          {
+ z( S& {; X& r/ V             tmp=s.top();/ J$ T& c' I# f6 s  y5 h! w- t
            s.pop();
+ O9 Q5 C/ I% o& G             q=vexTable[tmp].firstarc;/ N" i% a6 C" k* b/ w3 c) E4 A
            int t=tmp;
: W' [$ b5 `8 }' H; T             while(q&&tag[tmp]!=0)
$ v. ?5 g- p- w             {
0 X  l1 O) D8 O                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
. |- a, D" s8 O( S. C& I                   //cout<<" 2nd    tmp="<<tmp<<endl;
0 L5 w* q! E# {1 ^& t/ v                   q=NextArc(t,q);
$ V4 ]' X- Y" G3 j/ |6 X             }& @9 Q) j1 k# e9 }, m: y( L
            if(tag[tmp]==0)$ F( y( ]- Q7 d9 u6 ], v5 C8 ?. x
                  s.push(t);
. r* s2 ~) F! k: E4 O             ///1、对应上面连通分支只有1个点的情况7 \* ]: @9 @$ j8 p: Z1 y9 F
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈' N7 c+ t1 o0 _* \" Q* q  l
            ///tmp要么等于找到的第一个未访问节点，
4 `% {/ F' K. K  f9 ]( w. q+ m" Q             ///要么等于与t相连最后一个点（已被访问过）2 p# ?3 q7 r8 B9 v( L
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点* O9 B! S* y- x$ S2 A2 T
         }5 I1 I( t# w- _* j# l, U( w. R
      }1 b* {: Z9 C6 |* Z' K  M
}7 Y8 a1 H5 P' L$ C; _% s) w( @
}
. w( c5 e+ J- ]6 ]8 e- u: e//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1+ r6 i8 U# P3 G2 f
template<class ElemType, class WeightType> int- Z2 s/ e$ q% R+ e0 @
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
( q6 `. e" y% n1 U& O" i{
if(head==pre)
/ t" t) Q4 a1 i  d+ t       return -1;% Q, K, V1 j7 \2 _# L
' c' H, m" K% b2 y+ v& ?  _
MultiAdjListNetworkArc<WeightType> *p;- n; P) Z3 F- i/ g3 p4 `+ P1 P! w6 Y
p=vexTable[head].firstarc;
' v& o+ c! s  g8 r) w% a4 o% ^ if(pre==-1&&p!=NULL)
4 K6 c5 P$ L* C( v2 K       return p->adjVex1==head?p->adjVex2:p->adjVex1;* A4 h7 B: @6 c1 D
//pre!=-1&&p!=NULL9 D) x5 y% [9 }( [7 C; ~# u
while(p!=NULL)
+ o- F: E' W: k3 X, ]; ]; { {5 Z5 A9 w( r& z" k
      if(p->adjVex1==head && p->adjVex2!=pre)6 k1 b8 H: E9 x5 p8 R
         p=p->nextarc1;
3 [! X! \: Q: F% B) |       else if(p->adjVex2==head && p->adjVex1!=pre)) n2 F" p4 o: ?( u$ w/ k
         p=p->nextarc2;
8 _5 {4 k, M; ]0 H       else if(p->adjVex1==head && p->adjVex2==pre)4 b3 F/ X7 h( H- @( [( D
      {
, J; F: l6 E1 Z# t- f2 L# w          p=p->nextarc1;
3 C' k& h) ]3 t+ D" f% ?' }          break;
: g! f7 S2 T! h' S6 `$ C       }' h# B; a5 {" B1 ?
      else if(p->adjVex2==head && p->adjVex1==pre)% Q" S0 U/ L- Z% U% ?) R: T# o2 ~
      {
9 [% U  i; C' W! P6 I- H          p=p->nextarc2;# A! o5 t! \7 K$ t
         break;
/ N+ a( o* \. [0 c       }- X! @* p" k# ?! f  M
}3 Y& \* ~4 }9 M5 }. m1 ^- z4 M
if(p!=NULL)
; j5 j% T) \9 s* F3 a! f; f& f3 ] {
3 z  c: E* T; U8 Q  v       return p->adjVex1==head?p->adjVex2:p->adjVex1;
: v, O6 s4 ^2 I: @0 q  c9 ]( { }
* R, J5 B- \" J1 x( ^' a else
' t7 M' a; h4 I" `5 E       return -1;2 [, k) T/ L$ `( w2 U) E. @& w
}% y$ Y# n5 k9 @$ Z5 u2 m* m7 M

9 [" D, W4 I* p4 C* q" |% X( `/ ~
& p; |2 _5 K: S, Y( Z( {  ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
2 \: f0 o8 Z( V{
' F+ p" N" C% G$ b2 D$ m# [ stack<int> s;% Z$ z/ \! C8 @. T. I
int p,cur,pre;
7 G, n9 y% H$ ~4 G7 ]7 l1 c //MultiAdjListNetworkArc<WeightType> *p,*q;; ~$ j  u2 `2 n; `7 c8 S
for(int i=0; i<vexNum; i++) tag=0;//初始化( z# q; l" U8 X  X7 L" a& x

5 H4 w; G0 z) P for(int i=0; i<vexNum; i++)
0 p; v$ B( B& g; p/ \' l {7 r+ H' N6 l: g+ _/ w+ g# C) t8 J
      cur=i;pre=-1;* G" R/ ?5 K$ p% R0 i
      while(tag[cur]==0||!s.empty()), t, E7 O/ P* z/ X0 q& I- V
      {
9 z/ s3 V1 c* y7 M$ N4 j4 |          while(tag[cur]==0)2 B# }2 s/ I/ p
         {1 }7 Q: O& H4 _! F/ w
            cout<<vexTable[cur].data<<"  ";9 H( G, |( p. m/ X! j8 @2 Y
            s.push(cur);
4 @' s4 q$ h7 T             tag[cur]=1;
* a' `# {0 O4 n' \+ M             //初次访问，标记入栈
, F8 M9 g, O# T9 M' h1 W) r' m5 |) |# e( @
            p=GetAdjVex(cur,pre);//p是cur的连通顶点4 c4 F& _4 t/ w: J, A% x
            if(p==-1)
4 R' Y) b2 B" f; g' }             {
  T& Q4 e( M2 Q6 m! R0 i5 r+ _! k) }                pre=cur;s.pop();# z5 N! ?% x/ ^
               break;% y9 A: x* B5 z
            }/ u; o( T: i$ {1 `$ u  A5 J: H( O9 m6 B
            else
7 h3 u& X! N& D' F* B             {
' j9 t" D6 G6 U                pre=cur;. T+ \$ }) |( `$ E& d! X) U( M* \
               cur=p;5 P: u1 B" g$ ~* {
            }
" Z) ^% ?% \! z* L, s! D/ P' I3 A# s  Y" \7 k
         }2 `1 o( K! j- ?1 e/ I
         while(!s.empty())
! ^: I2 g/ t7 v          {
( S* |& [4 ?5 M; @) h- T$ d             cur=s.top();
, L/ Y9 O: V1 X- R! u( H             p=GetAdjVex(cur,pre);. u- j* K3 R, d5 A0 e6 I2 D
            if(tag[p]==0)% z# E" a+ D* o9 y( o0 e! a7 o
            {
, ?$ C& H# E' G                   pre=cur;
0 V# x- x8 G+ ~" A" G: f" U                   cur=p;
7 [. d( t- {8 d  j6 u# _                   break;
4 H" |, c) A( Z& U9 A2 A             }& s# Q7 m: I1 X) Q: k
            else
5 I3 O, J! |) b1 O8 L: C             {* _3 q0 W6 T5 z! F( s% \  X7 k
                  pre=s.top();4 s9 C5 L- U/ C( o
                  s.pop();1 b: x4 x6 e+ ?
            }
5 s2 B, p  Y! m# a# L) b3 Q+ x! K1 i/ E' ~$ y6 D) R
         }% n/ F( L1 K' `4 l
' ?% F- P& E& b/ b. m( L8 Y
      }- V9 x6 |1 I' g4 r. }* r
}6 E+ y: i- j9 p7 C
}
6 k& w, d5 m8 B: n+ R" R# L. Otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
% k- O) E# t2 W7 h# v{
* ?! _% D  e+ N  H$ d for(int i=0; i<vexNum; i++)
- X' I! [: o8 Y; Z       tag=0;& |" b3 n  i5 P8 w
queue<int> q;' `! w1 n, _# }# E/ `
int tmp,t;
5 {7 ~+ _. O4 d( w0 W4 q MultiAdjListNetworkArc<WeightType> *p;
2 S4 x. ]; D7 ?' U% r for(int i=0; i<vexNum; i++)
  j5 Z0 M( c# x2 t9 r8 ?9 F! B {" d. v8 Z! }, R  b) R; O/ d
      if(tag==0)7 j  H$ t( M  a% B3 P" f0 h
      {- O# I/ u. K. j) b
         tag=1;
, V( ]( c( ]( X' I6 v          q.push(i);
9 `  K% o0 m* L& d. J          cout<<setw(3)<<vexTable.data;! m% ?) k  M6 M8 l/ |  }
      }- M8 @  r, W& _$ x( y
      while(!q.empty())% }4 k7 E) V/ @7 {
      {
1 U  \3 R, x" v1 S# M% [          tmp=q.front();
& T. S- o5 b$ }% R5 r          q.pop();
0 j% s1 f4 F7 L" g. F$ p          p=vexTable[tmp].firstarc;( m" H) l* @8 q) W# u' c
         while(p!=NULL): c8 y; H! K6 k7 k7 S' D
         {
, ~# }: ?% o% m: Z5 A' _+ J6 l6 f             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);# a0 T  f- j  H/ s/ C! {
            if(tag[t]==0)2 H' U8 c& `! Y" G* A) g9 Z# s
            {: Q# d9 v# s9 I3 j6 {
                  cout<<setw(3)<<vexTable[t].data;
( o, j7 u( h) o5 d  k                   tag[t]=1;
& o  R0 u* ~6 y1 ^% G2 O, k                   q.push(t);% J6 ]% y* `* m+ L6 S, M4 [3 j
            }
" U9 m0 {+ x  Q. P             p=NextArc(tmp,p);9 D2 H- G6 c" w
         }
. x9 X3 k6 f; f% P% v2 t       }; }0 s0 M: q4 p/ I3 X
}
' d! |, s$ w" f7 L6 D}  o, I4 Q6 r8 _" R/ F% [5 u
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()3 q0 k: n7 |6 a# ?0 g, r
{
$ F* b% U7 H1 i. d MultiAdjListNetworkArc<WeightType> *p;. ~; Q% }0 y% k. A
cout << "无向图有" << vexNum << "个点，分别为:";
  Z" ^3 F3 V8 f: h' } for (int i = 0; i < vexNum; i++)& Y6 O! h% S7 T
      cout << vexTable.data << " ";
" q( }4 l- v3 X5 z8 P) D) C3 N1 V# f cout << endl;
$ s3 M* H; r: D% u- z+ `  I cout << "无向图有" << arcNum << "条边"<<endl;# U" v% b/ e" a! ?, c
for (int i = 0; i < vexNum; i++)" g+ x% {8 p, L6 B. u5 `
{
4 L* \4 M1 W0 y9 n4 l& ^2 Y0 O, h8 A       cout<<"和" << vexTable.data << "有关的边:";
7 G; \7 E( |+ Z5 I       p = vexTable.firstarc;
" S1 ~$ F1 v  F0 }1 w4 A+ v       while (p != NULL)- _! h, M! i5 L$ c  @
      {8 g. w) L: {3 E; P" E( w
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";, b6 Q. t% P+ V
         p=NextArc(i,p);
3 a2 G5 j  S; F$ P# I       }
% U; M" @* }% A5 J       cout << endl;% j6 |5 z+ L3 ^8 P3 l1 S' Z
}! ?8 O* f1 Q) R
}
- g' l# a1 I) H) E/ C/ h/ F! D# C, \9 u, d* z& n+ ?

# T& j3 Z% c  [6 U- z. U4 e8 _邻接多重表与邻接表的对比" m! @- M# e9 Z- G  s1 W5 _

邻接表链接5 E3 P( H5 S0 A, J. P
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
) j0 e' L8 k! d* v. @  K0 D在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
) ~: ]0 G4 P3 P% P$ D1 ]1 k$ }; k, h为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
5 `- Y! O% |9 x9 c, w————————————————1 Y" B2 x9 \  N7 A
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( p% p3 F6 p) k) x5 k. ]( H% ^2 C原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
0 [' v/ N, d2 e/ [2 k( u7 T, J! S1 f; e' n+ D

3 j8 Z# g$ u4 _% S" t
: n7 m3 Q3 U! E/ z9 f' V
, ^/ n2 o% ^0 i  X6 e. R————————————————
5 x6 Q; ~/ e1 M0 B2 u版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。+ o) K4 q( Q/ Y+ w6 I" v# F9 [- i  {
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669583 Q& ]1 }% c) u5 p( V2 f

6 @, l' `: r" ^/ |- b5 K
8 W$ ]& P, [. z6 `8 A5 |