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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：. \) o# ^% y: N! M# N; X9 |
data域存储有关顶点的信息；
8 G/ b3 } L$ g2 B$ Sfirstarc域是链接指针，指向第一条依附于该顶点的边。
& o% R6 I/ e) n8 k2 p; U( V所有的顶点结点组成一个顺序表。

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;% \1 g+ [& h1 Y3 ~, E1 h1 _1 z
for(int v=0; v<vexNum; v++)/ D# E+ Z9 D1 ?8 ^) f% h, a
{' M: X, {9 j. p% [6 \
      if(tag[v]==0)
* _5 \* D+ X/ q4 V0 J          DFS1(v);  B7 v2 s6 _  D! L4 G, o6 S# r
}
, v& ?  V- j0 U: K) Y}
2 Y8 h8 s! x3 A3 u3 Ttemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
; @  x& t) e$ [# K{
0 V) W+ V9 d2 | stack<int> s;
% [. W9 m% y# R) L" k9 {3 k int tmp;
4 Z+ H/ N7 p  ^4 h; N( e( n MultiAdjListNetworkArc<WeightType> *p,*q;
. w/ z  W2 {0 F for(int i=0; i<vexNum; i++)" I, e/ w; W7 o9 @
      tag=0;
7 g; q; B0 {* x for(int i=0; i<vexNum; i++)
+ B' y7 A9 X- e$ | {) Z! Z1 \6 ?  P* e7 \4 [2 V
      tmp=i;
" w' P5 [$ O7 b, e       while(tag[tmp]==0||!s.empty())
( b( D" ]. [: o) t4 Y6 D- X       {
3 J  Q. Q; g( l4 d  q          p=vexTable[tmp].firstarc;8 k9 L$ K6 |# e5 h( a! d: V
         while(tag[tmp]==0)) Y% `( Z6 I; C& q$ h) |. J
         {* h7 ?* C0 i- C% p* [- ~
            s.push(tmp);
% L' u: h; E" C4 |3 |# J# B) g  r             cout<<setw(3)<<vexTable[tmp].data;8 A+ Y. ?0 Y* L+ E) b. f
            tag[tmp]=1;9 @. F$ A) g3 v0 n% y
            p=vexTable[tmp].firstarc;4 n' X% v  v7 f) W
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
/ [9 u( F/ ~( Y, P* o             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
- x9 @! z: m& c- a; t  d. W             //cout<<" 1st    tmp="<<tmp<<endl;
0 ^& Q' @  g& W' l# o4 z; q          }
8 b' K) `7 R8 f/ \          if(!s.empty())
+ b5 |  z3 ?- g) n3 ~- t) U          {- A" j/ X! O% K/ R8 |0 q: ^) c
            tmp=s.top();( x) P/ i8 j3 f# L1 K" g
            s.pop();
' r, s( [' W. @& O; R             q=vexTable[tmp].firstarc;
/ X( j, E! {# z9 ~+ F0 C             int t=tmp;
" ?1 W' M* r$ ^             while(q&&tag[tmp]!=0)
7 ]; |* ~9 O6 w+ O8 t- F" h             {( [. E! c+ S4 [! _3 ~
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
2 B) G4 p7 f  y. g" E; s  w8 `                   //cout<<" 2nd    tmp="<<tmp<<endl;, l. R; R8 \) Y( ]
                  q=NextArc(t,q);
+ h1 c! o! ]2 c  n7 p& I             }
) @+ r6 |* k( b4 `; S) {3 e             if(tag[tmp]==0)
' W6 E) v3 g0 g7 i# `                   s.push(t);% P# m8 \+ _( q8 Y- Y+ S
            ///1、对应上面连通分支只有1个点的情况
* H3 h% W- Z2 y4 ~9 O             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈* O- A. G) E) B' Z; Q
            ///tmp要么等于找到的第一个未访问节点，# f/ H  q8 K1 |; `- d- F4 S( C
            ///要么等于与t相连最后一个点（已被访问过）; u0 S4 ~% y& \2 l& @' \! y% I
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
1 C) I' P" ?- p$ _/ k9 A          }
% A. t) V" h+ \+ G4 T3 R: g# e5 G       }4 [9 ^* X" Z4 ~( j9 K
}
+ F# T  Z7 f1 n. F}
; p( Q, k0 q/ \# X, l) e: U+ M: ]//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
# q' N( i9 a2 V( Ytemplate<class ElemType, class WeightType> int1 g( G! x1 P% B8 o! S1 I. ?# \) t
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre): I, W+ x( f. U0 ?' j1 j
{) @7 J1 I# k% @% B2 x
if(head==pre)
4 z' _' r2 \+ m" r5 z       return -1;- b' d0 Z$ A" E& u% [$ R7 n- k

3 }# ]/ l! e3 x/ |: d" E MultiAdjListNetworkArc<WeightType> *p;
; ?1 o; @7 d, m# _7 O p=vexTable[head].firstarc;2 s/ }. u- L5 H1 [# V) t4 c. H
if(pre==-1&&p!=NULL)( I& b: M. Q8 \/ }: x0 |
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
2 X  H" X4 M" W' C# W: T //pre!=-1&&p!=NULL
; j6 m6 z# y5 ~9 w* L" I* Z while(p!=NULL)
' _! E4 `# b6 o5 q; C {- f5 o% r) ]- V. R1 L  R7 S
      if(p->adjVex1==head && p->adjVex2!=pre)+ j2 N# k# i& n0 b8 X. w- ]
         p=p->nextarc1;
+ ^/ b: p( ?9 o; s       else if(p->adjVex2==head && p->adjVex1!=pre)
* F( x7 Q* p* \9 V          p=p->nextarc2;6 B1 W8 b, K; n! d1 u9 S' p/ [$ M  c
      else if(p->adjVex1==head && p->adjVex2==pre)
9 b+ c5 W% C. ~+ X' k       {7 X, B8 z7 Z) B9 o
         p=p->nextarc1;
7 a0 r5 {0 O+ @9 a* Y% [          break;) R) g3 G  c2 @( r
      }
% x4 E( b7 q4 b9 m( `) o6 a/ e! B* U) ]       else if(p->adjVex2==head && p->adjVex1==pre)9 a2 t6 D  W8 e+ \% o
      {
* s0 V9 f4 H9 c9 A, D& `( s          p=p->nextarc2;0 g; d4 l2 O# C8 R- `
         break;& Q* j4 c7 \! ?8 V" T
      }$ I4 s% _) }  ]5 k
}" V/ j8 Z1 ?& W! ]- I; v
if(p!=NULL)
, k$ B( _) B9 Y {
7 v$ ]% m; v. b       return p->adjVex1==head?p->adjVex2:p->adjVex1;
& j) Z) y% i% w9 r/ U7 }5 [: C6 g2 f }* {& c# C/ y- Y' A
else
) O% F4 S3 [- O0 q; \! U' g       return -1;
' W! y- I9 y7 t& p7 [}
& ~4 n, u. f2 l1 a2 `, d
' J: h6 H# D5 e4 k  V9 q
8 N% S4 G1 X! @2 Otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()) G. v! b6 o9 e% [: U6 P! _
{
/ e0 ?' h) A, p# f) b stack<int> s;
' t" y: b+ Y7 F2 I; E% [! I1 B. C int p,cur,pre;) \, L' n" L* C3 U$ s1 X
//MultiAdjListNetworkArc<WeightType> *p,*q;. N* W$ S5 H' L- @* r5 Q" u
for(int i=0; i<vexNum; i++) tag=0;//初始化; U" A6 E4 b8 T, L+ [
% Z( Z1 h! a7 K1 J# O' w
for(int i=0; i<vexNum; i++)- ^! Q! q' B. g
{- ]; [& X7 ^% Q. q8 J+ j
      cur=i;pre=-1;' O0 s% Q) K& U
      while(tag[cur]==0||!s.empty())
% {" Q7 o4 v" f       {- S* ^. _; m& N$ d5 g' c
         while(tag[cur]==0)8 i- a4 }& q; R6 O# L- V+ [
         {
$ I" n7 \5 N' Q- k             cout<<vexTable[cur].data<<"  ";% a/ N" ]/ Y' O; E, m, S* g
            s.push(cur);  [; ?' Y  c& P& J
            tag[cur]=1;1 E0 _, ]3 X* s/ X/ z
            //初次访问，标记入栈- M2 p9 I* t# F+ Z

' M' \! Q3 C* [             p=GetAdjVex(cur,pre);//p是cur的连通顶点5 Z7 V9 d& _  _0 `  o' V' Z
            if(p==-1)8 y4 E3 x, f% t8 ~2 @& m2 {4 R
            {4 t$ y; I  z0 Q$ Q; _
               pre=cur;s.pop();
( X8 `# S  N( }# W3 y                break;
$ A( q2 `! T/ j/ t( {             }
. u0 a. d9 z# |; g! n8 R             else$ S; P% m/ ?& Y! R) `) ^
            {
! u$ l$ J% D7 ]% S7 h; E4 @                pre=cur;
1 s' \$ c7 k  V; I; w8 F                cur=p;
0 R1 K( K1 Y7 N+ h) y1 c) V2 r4 d             }
; k" C/ N8 s) j
( ]) Q: S- \: n. C2 w          }4 p" A: C8 G5 c/ \! ]: ?- P5 j
         while(!s.empty())9 E' D" l, X/ o
         {
# H8 i9 p3 m: y             cur=s.top();! u( Z( M8 o7 }) M8 J
            p=GetAdjVex(cur,pre);) E/ a( ^9 T% g5 K3 ^" z# m
            if(tag[p]==0)
' I5 \1 r" a" x' N; T             {3 ~9 p% P4 v# y3 v1 T
                  pre=cur;
( ]5 W# ~' W6 ]- u                   cur=p;
9 H9 ^! j) b2 h* ]                   break;
0 d7 a/ A. \( s9 S. G             }
* j8 @  v: d  Y* D; g3 w7 D             else
* T2 v$ K7 f0 {* e" Z0 z             {
" [" Q: n- U& k8 Y* h3 X                   pre=s.top();9 ^( X  u+ X6 u8 K4 w3 u! z" T. l
                  s.pop();
9 L. w3 L3 }* H; \' Z3 L             }, M7 O) e+ T7 K: \0 m) Z- s

3 q1 q4 y4 ^& F& t, y% i: e. j& P          }
! O& Q# D  e. O2 d! C7 u) l: `
1 [* u6 C; S! q       }& g% n: X* |" [$ f9 X  ]( U$ B
}
! ?- ~" D! W- ^/ H3 ~}
7 C" z+ q% y* ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
2 _  t1 e1 M* t{8 _: N. g1 U3 A/ k
for(int i=0; i<vexNum; i++)$ [- ?+ |0 e: B) @2 z
      tag=0;. O+ d, p5 _: J/ R6 `9 E
queue<int> q;1 |" r; q$ L, F: f
int tmp,t;( o" k: q4 b& `" B8 D6 G
MultiAdjListNetworkArc<WeightType> *p;
  y( f* C3 Y3 d( w# [4 ~ for(int i=0; i<vexNum; i++)! |& a7 Q! k1 U+ j* H
{. w: `3 h6 r  B- v
      if(tag==0)
+ K& m, Q0 N2 H9 E( C       {
' Y3 L" K0 b+ W/ v# t9 l          tag=1;  q" H+ a2 N$ r( s/ B  J
         q.push(i);: P" a6 Q/ [9 k8 k) Y$ f
         cout<<setw(3)<<vexTable.data;: S) c5 }' A8 @1 q
      }6 v+ R- y* r8 O: w, r
      while(!q.empty())
7 N1 k7 C& [1 b  |8 r" l+ r       {- P/ W8 `: j; Q! |0 V5 X# u2 V
         tmp=q.front();
; ^6 u3 r6 ]% Q5 c& `5 R1 {          q.pop();9 I7 D# }) N% Q) y. C
         p=vexTable[tmp].firstarc;
1 c9 K6 N* M6 q% |+ g+ }& Y          while(p!=NULL)9 v/ m# i1 N% z& N
         {
6 R- B. ]  q- K7 k3 |4 M             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 g  R1 g7 v; f# i5 h             if(tag[t]==0)
: A! D7 _" c/ [$ s; {' M             {. H2 I3 `- m. }7 ~. A
                  cout<<setw(3)<<vexTable[t].data;
7 s1 e6 c1 g5 X1 J! }* ]                   tag[t]=1;
' x& A7 Q/ B3 K5 i9 ~( b" J0 b5 Z                   q.push(t);* V- o! I7 \  _3 }) N. I8 j* |
            }& j% ]  _1 P  d+ z# g6 @6 y$ \$ d
            p=NextArc(tmp,p);
1 Z& j" |4 j' K% }! y# S4 I          }, j# f6 C/ [  B9 L7 r
      }
( X' @8 x' ?$ {( W: W7 n }! V' ]% d8 B7 _/ ~; l
}9 P, z3 \  E" X0 y- q- P
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()4 Y2 U& z, ~5 O! |$ T  u6 l
{3 ]( C# h2 O6 y
MultiAdjListNetworkArc<WeightType> *p;
# d/ P! L& S% x& g0 D/ a cout << "无向图有" << vexNum << "个点，分别为:";
8 Q7 Z+ n$ Y( _( K: X# ?8 _% Q for (int i = 0; i < vexNum; i++)& c0 \( {% E2 Y- p" _
      cout << vexTable.data << " ";
" U! [- m  L9 ]& G* \% @# ]1 F" A cout << endl;
  d5 ~/ G& R5 j. `4 R; t cout << "无向图有" << arcNum << "条边"<<endl;
: U; S" B% s% m3 G for (int i = 0; i < vexNum; i++)
2 @' x7 k2 ^* d/ P. A% q/ ^ {
! H$ N! q) x& R1 d+ M       cout<<"和" << vexTable.data << "有关的边:";" M; q* s6 O% b
      p = vexTable.firstarc;' c1 {4 X( S8 `; n/ W% v1 E  g" e
      while (p != NULL)
% ]* Q, b3 S2 t1 ]! Q- f* l: S       {7 j1 c! x- r5 ~0 t
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
) N; H1 w3 z" p4 W" c          p=NextArc(i,p);6 j4 u/ f0 C8 F& d" m
      }2 \+ ]; ?" k  }
      cout << endl;6 p5 t$ q1 t0 q2 \
}
9 B' r0 |( u- k# `0 F4 ]}* c$ }+ d. G* e) n* j$ \2 M$ ^

( J" ^$ Q, N* x* b! L# d9 U& r8 e0 p' }8 s+ m0 K* T" Y4 f; l
邻接多重表与邻接表的对比
! o  Z2 n8 C5 Z/ K/ }
2 V# `( p# h6 c6 O邻接表链接
5 S* T" ^; z( S. \7 w7 {% |在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。1 ^4 d) }, O: x6 z- C( p" Y
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
3 w$ H3 `0 R9 J7 T/ d7 I6 X4 }. y# O为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
/ C$ B9 A! H! b) l————————————————; P1 Z1 O) Z2 ]
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。* f  b1 g* Q4 p
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
" x4 q  x" v! d) m1 I7 J5 L2 n% q) }" y8 d. g
/ F  M: C% k% l: C; A) c

" ~: X; I% G( V9 _7 Y# Q* J4 O6 Q# u$ m3 T0 T0 D
————————————————
' a. b2 \3 U: j版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- b) C- ?& J" @8 U原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958  Y# x8 I1 A! ]! A( e0 j

6 K% |$ Q9 G1 a  T. S8 u% K
- C+ ?3 D/ b1 M6 z2 K0 \