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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
F5 ^ _3 x( K- f6 c3 f/ edata域存储有关顶点的信息；
3 f" S$ y5 q; X6 B1 jfirstarc域是链接指针，指向第一条依附于该顶点的边。# `7 B! S% U( C
所有的顶点结点组成一个顺序表。

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;
9 w5 G. L" ]6 ?6 H9 q3 S9 E/ D% F for(int v=0; v<vexNum; v++)& R1 a) I' u$ _6 S# ?
{. l; g- H, U; T  b, i
      if(tag[v]==0)
+ @9 l$ Y; ^. M8 S# |0 r+ Q& `2 X; S          DFS1(v);- l+ x6 u% x$ [' F, V
}
. x# n  Q3 D6 C& V! R' F}
3 ~8 D3 ~2 w/ Q, z" |4 A8 ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
3 Q8 l2 m/ G2 P3 w{0 U+ `+ f) b: i$ g" P1 r9 h0 ^
stack<int> s;9 Q( x) J4 Q3 P2 k) I
int tmp;! {7 u3 j) \1 R  t2 j/ x: X
MultiAdjListNetworkArc<WeightType> *p,*q;3 X* A& ]6 o5 ?2 X
for(int i=0; i<vexNum; i++)
, Q; b5 Q1 u0 j9 p8 Z       tag=0;
2 I) r; G7 O% N+ p% d. x for(int i=0; i<vexNum; i++)
$ A% p1 u; H/ x9 l4 K4 R5 l {& d& E( O( s4 [! S0 s  [% {
      tmp=i;2 z' y8 B* w+ y( j) S) D" }
      while(tag[tmp]==0||!s.empty())- ]0 U9 d" E  {* _; i0 a8 E
      {. x* \/ a4 n3 O% n( E
         p=vexTable[tmp].firstarc;( P" U) r. ^  V7 v2 Q
         while(tag[tmp]==0)
( U& j4 s5 g7 o$ i6 G: L, v- s          {: Q) y5 Y+ J1 b' U6 W1 x
            s.push(tmp);9 w0 a' e6 {* g) T4 I
            cout<<setw(3)<<vexTable[tmp].data;4 h# j9 r' X. Q8 A* D1 S* Y3 I
            tag[tmp]=1;
9 Y1 ]3 u! H! a' c* K! T' Z) w             p=vexTable[tmp].firstarc;
1 v) I# r* d  \             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for, H8 O" _7 r9 q+ b4 k& v, v4 F
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);4 j8 I; {% z: o0 m6 r, s5 U
            //cout<<" 1st    tmp="<<tmp<<endl;/ O& ^  p6 S* y, n8 q7 z: n7 G! q" N
         }6 L- U8 R! C: A+ U: F" z
         if(!s.empty())  w* `$ S2 `  y% V8 `0 _6 y
         {
4 O* @: z8 A- N: a             tmp=s.top();; G6 a4 H3 t0 U6 F+ X6 m/ J' U
            s.pop();( X/ s8 y% O# |# i8 X7 B
            q=vexTable[tmp].firstarc;
            int t=tmp;  ~+ |3 R+ V' z( ~7 I: j  q
            while(q&&tag[tmp]!=0)
6 q  ^3 w6 a! O& ?             {
/ t5 |0 H+ ?! g9 \5 h                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);1 x9 l0 M7 N0 L+ K$ V
                  //cout<<" 2nd    tmp="<<tmp<<endl;
' g3 h4 Q$ ~# N1 j+ e$ A: ^                   q=NextArc(t,q);
! v0 C& x! ]* Y4 ~0 p             }0 Q! w( ]+ g$ }! D/ w( M( r2 V& F1 G
            if(tag[tmp]==0)
/ Q+ ]3 o+ @, p5 \' T- K                   s.push(t);
' {$ P9 v  q8 ^1 p& j2 ?             ///1、对应上面连通分支只有1个点的情况! v7 `' ^  Z/ f* `9 ^
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈/ N: E8 Q  B+ e  h, |. L+ `5 M
            ///tmp要么等于找到的第一个未访问节点，/ H2 {. @* C& ?8 [
            ///要么等于与t相连最后一个点（已被访问过）
, W3 V" s- }1 ^$ F) \             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
, y, J% `: B; M+ W          }: e2 G. N+ g6 M6 F' c% }- s( Q
      }
3 l+ B. @0 l( F) H }+ ], v4 }, d" _) K2 a/ @
}
% y1 x1 [: X( i$ i6 Z//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
( H% V& M& V! Q6 U% d. z! Wtemplate<class ElemType, class WeightType> int
4 B) {7 o1 f) _MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
- l# x0 r) H* Y9 x( @& G2 S" U( q$ `{+ \0 m3 p- q' R  |
if(head==pre)0 }* g, h3 i2 {
      return -1;
; b# z5 S+ K3 P& O8 [  G
. O( p, r' A6 ~. n, K8 |- ?& s/ K MultiAdjListNetworkArc<WeightType> *p;
6 ~0 v" H6 Y" u8 n  k p=vexTable[head].firstarc;
) Z6 r( u( Y, f" }+ ?2 Y3 L2 a if(pre==-1&&p!=NULL): ]7 s9 Z. {2 C4 ^0 J5 c
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
; M8 e6 k+ }1 H+ @- y/ P1 g. C //pre!=-1&&p!=NULL) ~: E9 P& O, n) X9 X
while(p!=NULL)4 g, a& |4 n9 G3 J# @
{' b, _' @- C: L" `' L
      if(p->adjVex1==head && p->adjVex2!=pre)/ n3 z" z& Z- a/ p
         p=p->nextarc1;8 E1 g/ E8 `$ g/ _) _) @. T" U
      else if(p->adjVex2==head && p->adjVex1!=pre)2 o. l$ W' c% m/ h- f
         p=p->nextarc2;
* E; F8 t2 z7 m0 o  g+ L- Y7 e       else if(p->adjVex1==head && p->adjVex2==pre)
4 \9 a4 x* b; u# u6 S0 \       {
( F7 G) t+ A& o6 i+ F          p=p->nextarc1;
1 r9 T- q" J# ~3 B          break;
9 i; O# y+ x* k  r4 O  Y       }7 k. ]; D/ Q  Y* m' X; Q/ T; E' t
      else if(p->adjVex2==head && p->adjVex1==pre)
: i4 s  ]5 {% Z% Q: q# Y       {
3 V' A9 L- l% Z4 X4 W- G          p=p->nextarc2;$ v+ _1 J) I0 m8 D; x$ r3 O! Z
         break;$ T- e* F, K( A( A! h0 E  u, H7 b
      }5 A6 y6 {, }! s$ M* M& z
}
$ T& C/ i; S! i1 k& R if(p!=NULL)
/ I+ `1 C! K( C7 R7 N {
4 X/ [/ w) h; Q$ ~: |0 X9 ^8 t       return p->adjVex1==head?p->adjVex2:p->adjVex1;+ s3 d/ _$ B# `) {) e
}" J4 o  w6 V3 B( d9 @/ R4 v
else
3 t$ W5 c$ x# S- I5 I1 o2 V       return -1;8 p: d9 S2 ~4 r& L0 ?1 w. ^
}7 j; m* |% P8 z1 o: R
; a! w' n+ b8 t- I# N+ v7 I& q
* ^# e9 R" q  o
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
$ J5 c: u: c+ Z% j6 x{
; Y# `2 W5 R1 w stack<int> s;
  V) f7 Z: q' Q- J4 [ int p,cur,pre;
, E9 X8 g' g5 M/ c$ y4 X+ u //MultiAdjListNetworkArc<WeightType> *p,*q;# i! f% y6 b. F$ p
for(int i=0; i<vexNum; i++) tag=0;//初始化& z8 m: D# F' q8 @: G+ b+ v) h

1 }5 B! D- ~& w8 U for(int i=0; i<vexNum; i++)3 ~) f1 ~. J: D- s0 O
{1 a/ `- G  i5 @
      cur=i;pre=-1;( {" j8 O1 E1 s
      while(tag[cur]==0||!s.empty())4 F# Y" Z* n( F) B& Z" o" z
      {
: a  Y. k+ |4 E, M, U+ s          while(tag[cur]==0)
- Z  K) w; d7 I) O6 c          {0 Z- t) R3 r6 I/ O4 }$ m
            cout<<vexTable[cur].data<<"  ";
" k6 R& o) z8 {( p; _; C& p             s.push(cur);9 n3 _$ F2 w1 r# s0 k# p! ]
            tag[cur]=1;: W' Q1 m5 S( L: ~6 r
            //初次访问，标记入栈3 W& I& u( d/ K0 t% B# l

7 m# F$ D" P+ {# ?, L) Q             p=GetAdjVex(cur,pre);//p是cur的连通顶点+ W2 z, b# W; y, M% K, ?
            if(p==-1)+ G9 N+ q" Q2 f/ R1 H! c* P+ `6 {
            {; w- _0 }* o% K$ Z, n" a" F! D
               pre=cur;s.pop();$ A0 S- R4 G; E7 t& ^$ h. ]  H
               break;% c  b' q- W; j& g: j/ x
            }  J4 z7 S8 s2 \* U0 j' R9 B
            else
& o+ V, V3 E' `) r  b  S             {
+ [% r, E, m4 V' Q& T5 w) l8 [                pre=cur;8 A0 I' ~' S/ K" I$ |+ r5 J
               cur=p;
  l$ P! j2 d: ]; i             }/ v7 K& G1 \1 I) T, g3 X3 X
! O8 f4 t/ P3 e9 [! [8 G
         }
3 o" M) N/ i& p! c+ `          while(!s.empty()); `# p& y; J* p8 y+ t% a
         {
/ c' [9 P( t  @, k7 r2 a2 X             cur=s.top();, {  p# {$ K3 L( \1 X4 n3 U! l: C
            p=GetAdjVex(cur,pre);
4 D0 V+ N" j6 \  J             if(tag[p]==0)
! G8 h' |- O2 ~9 h& k             {" ~' q* A* F( _" C, `, U$ v6 I
                  pre=cur;
; C! i: X/ [( d! e6 r% O                   cur=p;4 V3 U& g& K+ k
                  break;
( B( Y. m$ P- p3 c4 Q3 ~+ G             }
+ V! {: j/ M+ T. T             else
# P0 q) e, K) k& X! K8 i3 c/ j4 W             {
) f2 m( |4 [' P( M+ e* S* K                   pre=s.top();
- p% Q0 }  A, N% P* E2 U! R                   s.pop();
0 Y" r% P+ A1 R# `! S% o# G             }, r* u' ~  M+ M+ ?9 h' p! o% P

, _4 f3 {' |. U, Z9 L- t/ B9 _/ ^; [          }
) O$ i$ c2 _  a
( ^  o2 H4 S7 \$ H$ i# d1 O       }
0 y; Z/ ~, ?3 c }
, u+ m6 {3 u1 P/ F2 b- r) a}
3 {" S/ v2 N; Q. H0 u% O2 t" Ltemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()5 C" _# A! q/ H/ ^* l
{5 S) t. Q( Y' P! t- z  W* U
for(int i=0; i<vexNum; i++)
/ u' r  }, s: ?       tag=0;. \* E9 |2 L% u) X2 Z
queue<int> q;* v& J5 C7 n. O/ z
int tmp,t;) ]: a, F1 O! W) v( _( \( G% i7 o
MultiAdjListNetworkArc<WeightType> *p;
1 V- n. ?: p  ], z4 f8 b' s! ^% a/ k for(int i=0; i<vexNum; i++)
# K+ l( k" q" Q5 D# ^2 t  j4 c {( h  u0 h4 b8 ^, G
      if(tag==0)
+ s4 P+ j2 Q( X       {
8 r8 z# b4 T0 i3 M* N          tag=1;# ]/ `" s3 ~; y0 Z5 o* d: y- s9 H" L! _
         q.push(i);
! V+ G& o0 l( \, ^( l  k4 d4 O          cout<<setw(3)<<vexTable.data;
1 D/ T8 y- j/ T1 n       }
% `# l. D0 Z, ^9 M       while(!q.empty())
9 i- C& X; T1 H! j+ B       {8 `" ]& ~! o  e
         tmp=q.front();6 o# o" T  D* J4 i1 w8 Y1 J
         q.pop();
3 h5 t1 ~7 a# n& p$ H          p=vexTable[tmp].firstarc;
# y9 j( D7 r; l$ M# Z9 c( o1 f0 ^: h          while(p!=NULL)
2 @# D$ K! T4 n: Q4 X          {8 ]9 {% j: F, R' [  j
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);: H& A+ m( v" _3 h4 e
            if(tag[t]==0)
/ R  l* e9 V5 C2 N: ?- Y$ j             {# u2 k+ a$ v5 F+ S- `- ~" O
                  cout<<setw(3)<<vexTable[t].data;& t  r& T7 p# {; X
                  tag[t]=1;
* d1 ]; s1 ~  n& `% M4 R6 F& R                   q.push(t);4 K% q2 l+ R1 O1 E9 L6 x; F0 f! j  g
            }
" `4 T9 N  r; y) s$ C1 g$ ?% c/ m             p=NextArc(tmp,p);7 ~1 O5 |5 Z% ?5 W" I  L& F
         }- Z6 [8 Q( P! I, N9 O5 I
      }2 U) K' Q/ I9 a- Q7 D
}/ H3 I) H& z6 J0 p. Z1 C& {5 i* J
}
9 u6 O1 t" a1 Y9 itemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()$ m! N0 V$ g  |- {! b$ k3 t: S
{% N- P4 T7 ?8 D, S+ k$ l: m1 U
MultiAdjListNetworkArc<WeightType> *p;" ~7 ]  r! ]7 Q  W( r7 T/ m6 P( g; j' p
cout << "无向图有" << vexNum << "个点，分别为:";
  x' f7 |: ~4 E% ], X, ? for (int i = 0; i < vexNum; i++)
6 o- G/ z( U, D# ^4 P4 T* }/ l. l+ b       cout << vexTable.data << " ";
# m6 c" [+ |! I, x/ c* y9 W cout << endl;
0 P4 l/ i: P2 C cout << "无向图有" << arcNum << "条边"<<endl;
: s6 t6 N+ J" a! U) A, A for (int i = 0; i < vexNum; i++)  w. h7 H9 M  N& ]8 D6 |% O' A
{. |1 \* U4 f  Z- F, m% ]
      cout<<"和" << vexTable.data << "有关的边:";
1 p- M# X( @% {& g' b3 p& _       p = vexTable.firstarc;- t5 I* S" {( X  ], G- T
      while (p != NULL)
" n' D9 q3 h2 F* W1 V       {
; }( y3 M" e3 T) Y8 T; i& B          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
" g- C. {1 \7 {& R, ]' I          p=NextArc(i,p);* m) y% W+ b6 n/ ?% b( o8 A8 u- _' I
      }! a% }' M7 j) t" k) X; Y
      cout << endl;/ F7 Z9 A% [" X' d
}/ t% ]4 N  M: B/ K
}7 e; G9 m& O4 R( Z7 e$ X* [

8 R, s4 Z! K/ V% X& u+ N7 j  j
8 a4 W2 L3 P1 h邻接多重表与邻接表的对比2 X: ~' A: A3 v* V6 ]/ i

0 ?" g; M/ Y: i& I( ]( L邻接表链接
) c1 [: X# X3 A) u" W# s在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
6 I4 ?7 Q# ]6 n在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。* G1 i+ C8 g0 E. k4 j
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
7 ^! r: o. Y- r————————————————: Y! T- q" R" z( a/ t
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。% G4 D6 ?: s% `7 b2 d$ q1 k
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669586 D' M/ J5 a- a: m2 i- }

$ v1 ~' u2 Z2 p' s
- U+ F: F/ D, s0 F2 t4 U- l& d( h+ Y! N' D* Y. L

! j3 T7 v" F  s! X: U1 T& d8 W————————————————6 h  V. `8 Y' l! g6 r
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。/ _  k0 k) S+ x0 r6 X5 }
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669588 Z- z- w$ T. r+ t% r

( ?' }" a' u" n
* f3 D8 j9 D. t9 O1 u