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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：5 w; U" S* D% _; Q# t7 Q
data域存储有关顶点的信息；
; r9 ~& e3 E, t3 ?9 afirstarc域是链接指针，指向第一条依附于该顶点的边。: r; e0 c* M# I6 e& C1 t4 p, }
所有的顶点结点组成一个顺序表。

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;' T5 V* \- y1 C  U, d
for(int v=0; v<vexNum; v++)+ r- A- b0 c' Z; a
{
% V3 {/ A+ v4 J8 W$ _       if(tag[v]==0)
( v* o$ j: x  r5 w5 w: F  w          DFS1(v);6 r& ~' B* K- i
}
) O2 g3 O( j: f7 d}
0 R% Q5 J6 {+ q7 u4 x+ ptemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
8 Y" L7 R9 n$ Z/ s+ _! M5 U8 F% l{; z) B2 c& W1 }6 V) \) v% x& w
stack<int> s;
! L9 X4 S7 u6 c4 K& H int tmp;: j1 c' p# {9 v3 v
MultiAdjListNetworkArc<WeightType> *p,*q;+ z& N9 J7 z3 X; K
for(int i=0; i<vexNum; i++)
: b( z/ M- m8 x       tag=0;( W1 L/ z$ v0 K3 y  ~( J
for(int i=0; i<vexNum; i++)
" K$ `* w  h% ?0 @, t. P {; j; H# ?! P2 X+ b
      tmp=i;; P6 B$ K0 }. _9 I  k$ }7 W+ D3 C
      while(tag[tmp]==0||!s.empty())
9 P/ m$ w7 h# k. J+ V: O  b       {1 O8 w! l/ G/ r# C3 p& s- _
         p=vexTable[tmp].firstarc;
: o% p( e" G# ]; ?& }: V          while(tag[tmp]==0)
- l% m% L: Y% x" T          {4 ^! x+ T/ [. V& E6 f' ]" M2 \" T
            s.push(tmp);: d% N( l+ n6 R& ^
            cout<<setw(3)<<vexTable[tmp].data;
: ~, l6 @. a1 O8 c  W( e9 V5 p  N             tag[tmp]=1;
& t3 T5 z2 O- H; G: J             p=vexTable[tmp].firstarc;
5 \* Y3 ^, \$ n$ z# y             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for3 `0 k3 p; I' ?& U$ g
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
6 A; V3 C' w: A3 I             //cout<<" 1st    tmp="<<tmp<<endl;
+ }6 u7 T/ L% A$ z# S3 N          }7 R. {4 X" Z* M* Y% D% W. x
         if(!s.empty())' v2 s8 B  ]7 L- g; }1 `$ o, P
         {" n$ h  v+ P* d' U2 B* J8 d
            tmp=s.top();- W! }: u" j) `' l. Q6 B' R
            s.pop();
; `8 X/ Z- @1 g# z             q=vexTable[tmp].firstarc;. O( w- T' T% A! t( Q8 K
            int t=tmp;
5 G0 m, O$ J0 J, ^) ^8 \             while(q&&tag[tmp]!=0)
3 U. A9 |6 P2 y$ r% K( c6 F0 z# X             {
& J3 L% w4 l/ i4 L( J; i                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
  C) O2 F1 A5 n) N' [) u                   //cout<<" 2nd    tmp="<<tmp<<endl;3 A, d  u8 p  f  S' ]
                  q=NextArc(t,q);& N" I, V: T% a$ R/ c  u  ^6 V
            }+ c, h+ R+ m  [3 y8 g
            if(tag[tmp]==0)
1 K8 Z1 v) [4 k. g. X* @                   s.push(t);: w9 y3 R6 R0 a6 I
            ///1、对应上面连通分支只有1个点的情况  c% y9 N. F+ i; _; h3 A% W) m
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈2 c2 w  F& |' H$ t! o, b
            ///tmp要么等于找到的第一个未访问节点，
2 _; a. g$ E0 `$ [5 r* H/ m) N, m             ///要么等于与t相连最后一个点（已被访问过）
0 ]( k& b& N1 e- C# a             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
) W. Z& v6 ^1 n, X          }
8 h+ E  D( F: \       }
1 a. v2 G! }2 C' r9 n }0 R1 F; Q. |. m2 A
}
  d% m! U$ P% m5 o6 J5 i6 }//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
' s8 `+ V& g0 n& E* [: B, q% b8 A4 atemplate<class ElemType, class WeightType> int
# @% x+ ^- A, M/ g: rMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
4 t  X2 _3 l6 w5 {0 K{
% c/ Y) y" W. [& {. q: ?' s3 Z! w$ Z if(head==pre)
# Y& {- Z" n& E* |9 g# ^       return -1;
4 h7 z" {+ d! X' I6 c$ K& F2 K: i; n
MultiAdjListNetworkArc<WeightType> *p;* m: T0 C8 x( W6 a
p=vexTable[head].firstarc;
1 o# {3 R+ c4 j- _2 V if(pre==-1&&p!=NULL)
# i# Y4 s4 B  K$ l( j# d7 T       return p->adjVex1==head?p->adjVex2:p->adjVex1;' Q3 [5 ~% \) c& t; k9 U
//pre!=-1&&p!=NULL5 |5 J. ~$ F, C! t  G7 ~
while(p!=NULL)
( }$ Z$ K7 }$ y9 {* k6 ?1 [: y {* o, e* ?3 l* w% n
      if(p->adjVex1==head && p->adjVex2!=pre)
* V6 {# f  t5 v( W, u          p=p->nextarc1;! O" ~' \2 X! f1 r+ I
      else if(p->adjVex2==head && p->adjVex1!=pre)
' y6 a* W+ A; `% \( |          p=p->nextarc2;
) b1 n* g8 _5 J. K- p       else if(p->adjVex1==head && p->adjVex2==pre)0 @3 V* g- n7 a; H* `$ H& b8 G
      {$ y8 G& ^( ~' i# Y6 C$ I6 Y
         p=p->nextarc1;, |( b/ V6 _/ J
         break;) B, ], C) h: M! a
      }6 Z! _4 h: @5 @
      else if(p->adjVex2==head && p->adjVex1==pre); q! d, o  k' t9 A& `2 b- h7 N8 U
      {, @1 k+ C0 _; o- w  x9 `
         p=p->nextarc2;
' `- W0 Y% s9 X  m5 T- |          break;: Q' o. C5 z( B2 R
      }8 I+ ~/ X/ N0 @+ m' X
}
, u) K7 g2 j' {0 f( I if(p!=NULL)
4 d3 x; a3 c+ g6 |0 P# X+ W/ ` {
/ X+ P4 l+ @8 B# [) b. }/ u0 J       return p->adjVex1==head?p->adjVex2:p->adjVex1;
* u2 m! D! ~3 o$ |$ i }9 F" K2 c& [+ M, P9 C* V1 T3 z
else
' L, _- c* }, E' K/ U       return -1;
8 u1 \6 V1 x7 P+ l}
* E! M! c5 u# W% G# O
; Q" ?% m0 v, `7 o9 x$ A; t) q
: P2 ^' K8 W: `( h) vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()# W% I; I. C& V
{  c5 D* q' R6 y; u3 @5 C
stack<int> s;* t% c) t, c3 M0 m5 R  `
int p,cur,pre;
( F% ]6 g5 h, E. \6 V //MultiAdjListNetworkArc<WeightType> *p,*q;
  ?$ H6 Q2 `: {0 J; v! \- a for(int i=0; i<vexNum; i++) tag=0;//初始化% J- d% ~7 ~8 M) ]8 c8 h# k6 i4 R
: t, z) g: D  l( `* W5 W+ W. B
for(int i=0; i<vexNum; i++)
6 n# N0 }7 J5 y' [+ z8 t {
5 _' D6 @" E1 I% B       cur=i;pre=-1;
8 o. }/ n& x" E+ W, n       while(tag[cur]==0||!s.empty())
" C, T! s& U+ a8 C) u       {8 A( X( I+ y8 w0 R
         while(tag[cur]==0)
8 f& P- L+ c: Q4 d* G. ?" n% G          {' D( R. c$ \, O  M6 S8 r$ V4 Z
            cout<<vexTable[cur].data<<"  ";" ^+ k3 [! B1 `* r
            s.push(cur);
+ s- _' i; o1 d6 A             tag[cur]=1;
! a& r! M1 o8 [# p1 x! f             //初次访问，标记入栈4 G/ V+ F. n, Y5 t# \6 B
. R* v4 [8 c+ ?" g: ^! q3 i; p4 ]
            p=GetAdjVex(cur,pre);//p是cur的连通顶点, E9 l: c% t2 t: p8 i
            if(p==-1)
# L# B) ?: b" M             {
& H8 A  L  I# x9 |$ ?/ H                pre=cur;s.pop();" \8 b- @% {" Z) F5 F2 ~
               break;
/ I9 y. }2 J& ~( ^2 D             }
1 `+ |9 u% y2 m             else1 J. R" k/ U7 j/ e! U8 y7 n0 Z( Q
            {* Z/ _$ G7 Z& F* P
               pre=cur;, \5 x% F- Y5 c; _* ~/ B
               cur=p;0 H  t2 u8 w* {5 v: e6 j5 N9 a
            }
+ p( S5 Y8 u2 o: H! G
+ f/ y1 O; e  b2 X0 J- t          }
" n& G0 U$ ]+ [5 \) h  d          while(!s.empty())
8 O8 J5 i8 ^* ^- j          {- E0 b$ b7 \, [7 }, y9 \* d
            cur=s.top();: R# @8 h, z  ~7 Y' c" Y5 W
            p=GetAdjVex(cur,pre);$ R8 M5 l( z+ ~  E2 g7 t$ c- Q% i
            if(tag[p]==0)
+ W5 N# k5 S. W, n* q! @6 q, d             {
" l8 C# ?  F  v. e3 K, h                   pre=cur;. {# r7 i. l1 |
                  cur=p;
' I+ o& G6 E# N+ B; `1 ], Y* l. a                   break;
& e& V, O" w/ v& e  B# {             }$ L/ u# _, R" Z  i" ?$ D, w
            else
: S. J) E3 [0 N1 k" p) Y& ^5 h             {3 j# T/ B2 P1 T+ E% x, A$ ?. U
                  pre=s.top();
2 b# \6 d4 r7 a! L8 |% p' D. j                   s.pop();$ G+ R2 v- n, e0 A8 G3 H( w
            }
+ O& E" G! M2 q7 |3 m! o! m% |4 W2 i* O/ {( K' f( u" h$ t" ]
         }
  N! q6 S& f" h4 _: s! P
& w9 D8 f: P) F       }
, D* y6 _. ^) R. e. a }
- G6 ]& u$ h5 M. {9 m( j! E5 A}% v$ y1 j/ S0 `' s
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()( {/ o+ ?7 A6 o# i. H( }& d
{5 F9 j! q( T0 |$ c4 S6 x- Y
for(int i=0; i<vexNum; i++). B" i- H: R6 [  K+ }- h
      tag=0;" E8 k# ^# T& |, P# o/ |
queue<int> q;
" g( Z* L, n  S4 M  B int tmp,t;/ y/ @. s; K( H) _# z0 E/ J" i5 @
MultiAdjListNetworkArc<WeightType> *p;9 q% Q8 _) z. l) `! n7 K2 c
for(int i=0; i<vexNum; i++)( n9 F. |( l! Y( a6 }
{
1 x5 ^4 l; t0 r7 Y* Z. b       if(tag==0)/ j- w/ a0 ]/ H. `& c
      {% Q/ u9 ?1 }3 ~8 h
         tag=1;
$ _' `) u  D' Q# N- R          q.push(i);4 }: a" ]. J) e$ @
         cout<<setw(3)<<vexTable.data;
: y; S* u' F+ B) l9 _       }
! T8 ^1 z1 L1 d1 ~       while(!q.empty())
, x2 T0 U5 L; M       {
5 Q& U  _* w! u, l9 c8 p          tmp=q.front();# a8 \, [7 ~7 p$ o( E6 C9 n
         q.pop();
; E' X& k1 M7 [% e          p=vexTable[tmp].firstarc;9 l3 ?0 i- u8 O) e1 l" k& y
         while(p!=NULL)6 D$ H' F# O1 r* P- k
         {  K5 S9 }" _: j$ Y( f& M# q
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);! Z% U( A: f- f* }5 w
            if(tag[t]==0)5 Z1 \7 Z+ z7 w# e. h2 ~
            {6 S# w$ k. C6 m0 x% w% }* u" V* d
                  cout<<setw(3)<<vexTable[t].data;
, |. @0 _; e" S0 s3 g% Q1 p                   tag[t]=1;: _1 E. c9 {4 `/ \- P
                  q.push(t);# ?; ^* o+ N4 V, F! h6 v
            }+ P# t1 B0 f& m  n4 W7 F
            p=NextArc(tmp,p);! K/ T0 y$ c4 ?/ j" h0 b4 I
         }
: {+ z/ V# C) ~) y8 \       }
% o: {( ]% a& M6 g8 s }6 U- X0 I: P* K# ?: r- g
}
! d8 K+ ?% f8 K" t. utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()5 D% F) a$ i% `9 J5 x; H& D0 `
{8 [& G. b: W" n2 P
MultiAdjListNetworkArc<WeightType> *p;' Z2 w4 K9 g# u# g* C& W, E( a7 Y5 }
cout << "无向图有" << vexNum << "个点，分别为:";
' _# x8 B5 W, A$ I& y( X: c for (int i = 0; i < vexNum; i++)# T+ W2 u5 A$ A, X
      cout << vexTable.data << " ";
/ [* {# x3 ^, f& I# v: W# T% P, T cout << endl;
! e( w0 D6 ~7 U cout << "无向图有" << arcNum << "条边"<<endl;' n( [7 R( R7 G/ A) n
for (int i = 0; i < vexNum; i++)" ^3 \) T2 F; x) ^' n
{
' w6 W4 j. O1 B# }5 _       cout<<"和" << vexTable.data << "有关的边:";6 k0 ^, z4 A, Q% b# L; S1 M4 p& Z
      p = vexTable.firstarc;4 `# p# \) G' E! \8 X* C
      while (p != NULL)/ T- |' X* G. u
      {
( h! g* d1 P' K" e' W/ `) R' O          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";0 C2 t# b6 t! E+ h# g* K$ c
         p=NextArc(i,p);2 u$ F; d( s3 p% N! s
      }
7 Q* p! i: w0 _% s       cout << endl;
6 P* x8 w6 g7 I* v' i- }9 [ }
( ?+ z7 P2 p0 i: ?4 ?% r}
* Q: Y7 |+ j0 T8 I. c. L) P( @( K  i3 m4 u* s/ X1 ^+ [

( M7 a  m. h2 Z5 X0 s! q邻接多重表与邻接表的对比4 k9 m8 @, z9 J% l0 h
( `$ ^% `+ v! q+ t
邻接表链接% Q) O2 J0 \4 M. D3 v3 o
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。9 y: n% M$ a$ j/ b5 d. z& o- _
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。2 p* R2 H. i  k5 N3 k4 R( j
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。9 S2 V9 O9 |+ M
————————————————5 M1 c5 D+ f  u0 @, J" a4 T4 R. j
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ d$ g7 L0 D6 z3 h6 j4 U原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958, C3 ]9 d- m1 ?- {7 K8 l- Z5 K
% r6 A7 J1 s4 q& M) q+ ]- e
  W) W% E& G& Y( F4 Y' L7 A( q

0 u; I- j4 B+ O9 \- V0 M  k0 h' p! c8 y8 D, h
————————————————
4 a0 X6 _# M+ g# q$ Z& L& S( R1 s版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 s* j. y' ^  x9 }4 D2 @" L0 j原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
5 i3 P8 B' Y" X) y9 J2 m! A; T7 b6 |" ]8 u" K7 r
2 q! n  q, K$ |) r