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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
3 g! d C1 A1 ^2 W+ Vdata域存储有关顶点的信息；
3 P5 Z9 F! ?, l& T% efirstarc域是链接指针，指向第一条依附于该顶点的边。7 U. u' z5 |: h
所有的顶点结点组成一个顺序表。

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;
# l7 F+ _4 n* X: t, c for(int v=0; v<vexNum; v++)
8 q; E) E, n+ e9 ^ {
  a9 [& t; |% h2 ?: Y- x       if(tag[v]==0)" Y4 m) O7 W$ @/ M5 N
         DFS1(v);6 x% V- i% ^% F1 [+ s/ n
}
! T7 K) `$ m) M8 s( ?}* j9 ~9 m; F! K* }; d' [) f
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
1 [7 a* e2 R7 c4 W{
. }3 L0 _+ g2 M+ N. \ stack<int> s;0 D4 p3 ]( c; ?5 l9 u
int tmp;
& v! E0 o9 l( k6 Z1 y( I; S MultiAdjListNetworkArc<WeightType> *p,*q;
/ `8 M0 Y; A* s; X for(int i=0; i<vexNum; i++)
) D- L! E( J; \       tag=0;
) L4 ?9 S* u6 T( a3 t3 j1 X3 M" E for(int i=0; i<vexNum; i++). F% f/ V% ?' _2 ^- J; t
{
2 R# I3 v/ A6 j7 C" e2 C2 w       tmp=i;( a0 W, a, W3 |( w
      while(tag[tmp]==0||!s.empty())
8 ]0 Z$ x1 @) z3 m  `# |       {
$ I6 o' c9 x5 x0 J4 }* Q9 `          p=vexTable[tmp].firstarc;
+ V- l5 \4 Z" z          while(tag[tmp]==0)0 P$ O1 ]; B0 T
         {* A% O5 @, \+ d. t9 r
            s.push(tmp);
5 y7 F6 |& ~, ^& }. A+ f             cout<<setw(3)<<vexTable[tmp].data;7 l6 E# ?- c! R, e: R  V% f
            tag[tmp]=1;
9 a2 ^- i& q9 P, _# I  I: \7 r             p=vexTable[tmp].firstarc;
- B* ^* m% N' M5 q6 H3 K5 o. V             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for  L! b' L8 a7 M* R
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);% U3 H- O& C( ~7 N: w7 V% f
            //cout<<" 1st    tmp="<<tmp<<endl;. k3 [* w+ B: R0 v# F$ h( ^4 p1 n
         }
. ^  U" O2 g0 V) D& ~* k' |7 ]          if(!s.empty())' x" A1 e7 O. \* q
         {
2 i4 f# L! h3 {2 h, o: _             tmp=s.top();/ a7 t2 \- B& d4 k' m+ j4 e
            s.pop();/ j: [) P# b. p
            q=vexTable[tmp].firstarc;$ w6 B9 c4 X& u: w
            int t=tmp;
1 v4 l8 N: n8 n2 v             while(q&&tag[tmp]!=0)/ d8 [$ n; {3 \
            {" d; s' J; a  d2 x. M
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
: J( k! o& i2 ]5 }                   //cout<<" 2nd    tmp="<<tmp<<endl;
0 I3 v1 h& Q. G+ ]                   q=NextArc(t,q);# y7 Z+ `! d/ c  r
            }
5 O- t. N- P! p$ \5 p8 g             if(tag[tmp]==0)
% e, `6 w( o) S1 H" l1 y                   s.push(t);0 {- A1 c- t: ^, L+ ?
            ///1、对应上面连通分支只有1个点的情况
! \( a) ]$ J4 z' F0 u2 N             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
: A$ q2 C2 {0 R9 `2 u1 t* o8 n0 X! t             ///tmp要么等于找到的第一个未访问节点，! K3 P" t) e! _$ `
            ///要么等于与t相连最后一个点（已被访问过）
. F8 o  z+ E  Z( z             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点2 b  w$ c; a- @, Z* K: h9 v# Z
         }
9 o( y- l2 f! p3 }       }
* h0 Z; Q9 o8 D, b/ S8 c! N }
0 o/ P. D* D2 ?# v! H" v$ U}
* F* R1 k0 u  Z2 S/ [//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
" k7 o) s+ M3 c' ]1 f0 V3 e; Vtemplate<class ElemType, class WeightType> int
: o5 r) w$ M3 c6 MMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)2 v9 s: v& ^& Z; V! C! ^# }
{
( O: I4 B+ b: J$ Y# L! ~+ C if(head==pre)3 G9 h' G8 a1 {- t' ^2 ?% C
      return -1;  ^7 _, P; g' T; ?

# L' _: `5 s5 `( h$ R MultiAdjListNetworkArc<WeightType> *p;
  b, @. h( ~8 C9 ]6 T& L3 k% I p=vexTable[head].firstarc;
  U9 t) s* W/ ^3 q4 v if(pre==-1&&p!=NULL)5 T' c; p$ V4 N* |8 t
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
9 v8 ?. V, n( A1 A+ J; l0 C9 n //pre!=-1&&p!=NULL
- g, O. Y9 }' f8 u4 H* W! M7 Q while(p!=NULL)7 o, X6 m+ L) Q
{
# y  O$ ~- Z! Y3 A* E* u       if(p->adjVex1==head && p->adjVex2!=pre)' @: Y( A' E. U5 E" l2 j
         p=p->nextarc1;
: c% m# {1 j; y* K8 v       else if(p->adjVex2==head && p->adjVex1!=pre)
, K* B" X2 u: c: |5 ~4 f          p=p->nextarc2;+ C* D0 U. `8 w
      else if(p->adjVex1==head && p->adjVex2==pre)/ U  y3 e2 t) z1 Y! i- W7 t
      {
; D8 F3 Q5 K1 K/ {          p=p->nextarc1;
6 l4 d# V* w% s9 o          break;+ @  N1 D5 X  f! K
      }
+ V9 }# F1 r3 ]; n6 y& O, B       else if(p->adjVex2==head && p->adjVex1==pre)
4 `1 C6 u  \1 |0 c/ e       {: m+ Y4 V. j6 @* A
         p=p->nextarc2;
/ m. x% U# H- l  ?- f          break;3 H2 \% k" K; L1 Y3 x$ t
      }% z7 \. V2 g" s. ^( a$ ^
}0 F1 L3 v- t: F* ~; `* z
if(p!=NULL)3 R2 c8 h: A/ I+ S0 |! o/ l2 i
{) y  @, a  z; f7 w1 ~: s1 K. B
      return p->adjVex1==head?p->adjVex2:p->adjVex1;4 T) ~+ ^1 f/ D0 V6 O
}
$ H, u$ y0 ~+ s else
- o0 z0 J+ ~' @1 J       return -1;% Y/ @$ l$ f$ v: u4 C' L! }4 U- v. t' c
}" f5 _) L( M9 z$ W- f8 j4 k
/ h. Z! d1 b8 l/ V5 {/ |7 G
% v& N( E1 W. l1 ?( U, H
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()* a% M$ A0 `9 A5 S, @2 D# R/ y# K
{
* q3 z( m% M/ e. K2 G5 U1 s! ~ stack<int> s;6 F& G. k  b+ |$ I
int p,cur,pre;3 c. m' p: P- A! B/ `
//MultiAdjListNetworkArc<WeightType> *p,*q;
4 _0 o) {3 K( [6 P6 n( _ for(int i=0; i<vexNum; i++) tag=0;//初始化9 d  \$ E7 w$ \4 U3 U) x
" H& j- a/ u2 G6 q
for(int i=0; i<vexNum; i++)
4 a7 }5 S- o! X' l# p {
* r4 l9 G. ~; {4 c  K! u7 V       cur=i;pre=-1;
" d0 a( F! X  \& u1 e+ ]       while(tag[cur]==0||!s.empty())- g( @4 m0 x) o; e2 q: {
      {
1 T+ R$ y; d0 Q6 f- `          while(tag[cur]==0)
! c1 E4 r: L. b# q& s: n6 z$ t          {# A; }6 i1 o% X" H
            cout<<vexTable[cur].data<<"  ";$ J7 o) J. q2 |9 g* }
            s.push(cur);! d6 B2 l% [2 a7 l5 Y+ K
            tag[cur]=1;
' [5 ?; f* N% v$ g2 U& M             //初次访问，标记入栈
' S  {8 n& ]3 n  O  z3 L% y$ d) `6 d: m8 w! A3 O4 R! O1 p$ `
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
8 i9 o6 ?* O4 x# n* z0 Y             if(p==-1)
. M3 Y6 u: {8 L- M5 z             {
9 c0 O% E+ Y, Y( b                pre=cur;s.pop();
6 B8 y2 Q7 C$ l                break;
, P7 X& w$ U' Z5 P             }
/ C/ u# l7 E+ |/ p6 y             else
( l  A9 _1 N( q3 J. j6 u             {8 U7 e# O- i( }. ^) w9 T2 L
               pre=cur;
4 ~' ?" H. c+ V& ~; t( [% d                cur=p;
7 t. }: U4 w1 m             }' L+ J) C( h- I0 C3 T9 J

; d3 M5 r9 N5 ]- s0 t9 r          }
: m; g6 g3 L' m9 d" r$ S* P          while(!s.empty())
. j7 Z# X  ^8 F! I5 s          {
- F' @1 b; N1 b6 o' A             cur=s.top();
/ d) ^( @7 T( y  x             p=GetAdjVex(cur,pre);
8 f/ n% P0 s  [             if(tag[p]==0)
. p  R. B2 S; E$ h6 w- \7 F( i$ _# d             {' D% b( w0 H% D0 C( Q, U' G
                  pre=cur;9 |1 j, ]' o* \0 w6 E0 a6 o
                  cur=p;8 i; [2 g. o) C4 a0 O  o8 o
                  break;: y! k8 }6 k  m* u3 d. j1 E3 b
            }
8 {" A4 m0 U  Z3 L+ f# t. _% \" J# l             else) E1 x' l$ J3 a: S
            {
! b$ O5 V8 g$ s) u2 u0 \                   pre=s.top();3 c/ J( |+ r7 E5 T9 V8 z" k3 {
                  s.pop();
6 D3 i8 m* q) z: q  Z& f6 {( N             }/ T. Z4 r# F; y
6 [6 \( |  i1 w/ g
         }
, M2 }5 b, _9 f" r- Q' e4 M1 H" L! ], A6 f& g' H4 k# s
      }% l, r8 T5 N& E0 n2 U
}
& K: p9 X, j/ _( u}; F3 ]+ s+ E, u* l2 D1 C
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS(), v" V& G/ Q0 X6 J
{
# }) U' w" d* n8 a0 _ for(int i=0; i<vexNum; i++)
5 l  j: K9 K- h4 \       tag=0;
/ F; R' h4 Q& c! t- C; ~/ g queue<int> q;9 o1 X. W) B- t" A) D, {' k
int tmp,t;; A+ m( l0 [% }+ l8 F
MultiAdjListNetworkArc<WeightType> *p;7 f- a: O0 v" ?
for(int i=0; i<vexNum; i++)
2 `# {6 y5 ~) G& V {, P% A; B8 E" G  Y& p  @
      if(tag==0)
      {, w5 X, D3 u, Z% Q! p. x- |
         tag=1;
; a/ o4 f2 q4 H, P2 I$ B* Y  }" M6 {          q.push(i);9 k: z  ]: R) G6 _0 H4 P# [# h* w  y
         cout<<setw(3)<<vexTable.data;# Y; M% n! u* B
      }& S, W* \! }" y" u  o
      while(!q.empty())# b) o+ S! j* y7 _- l9 C
      {% w' ]; k, e; }5 X" t5 T- p- J
         tmp=q.front();
) M% F  Z  T0 B* d$ j5 L          q.pop();1 f" H3 F; R: g/ [* ~
         p=vexTable[tmp].firstarc;
/ K  W; R9 ?' H) P3 l          while(p!=NULL)
- K8 E4 U+ Q7 |" j( h# P. q          {
/ D+ |+ |5 k3 {; u" N             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);$ W2 G. c( ]* o0 }! E! K; `
            if(tag[t]==0)
, I1 _) @! p0 r7 Z; N             {( u! u' I$ W/ V# a0 o
                  cout<<setw(3)<<vexTable[t].data;$ f# J! F' b! V$ P: I+ x; K
                  tag[t]=1;; u# {" w( v. C8 `" X8 Y! J
                  q.push(t);
. z5 Z8 v3 h7 q9 N7 p8 S. q             }1 _* x4 F5 @3 `5 J! ?7 [3 ^9 b% z
            p=NextArc(tmp,p);
* G4 U( C& K; C4 x8 {' n! G          }9 d8 m  y  K- }  ^
      }, \2 j) G$ b, p* C, R
}- |7 i$ w7 W9 @7 W
}0 x& O9 I0 d2 t4 [6 E
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
- q9 s  f1 |% v, u" H  U{& h/ e9 E, _. a- a) s
MultiAdjListNetworkArc<WeightType> *p;
! L+ r# p8 B* l2 k- u" y cout << "无向图有" << vexNum << "个点，分别为:";4 ?3 C8 s6 |3 R& T& b* p4 Z
for (int i = 0; i < vexNum; i++)
6 D4 o% h3 k0 E6 N       cout << vexTable.data << " ";
: V' L& o+ [6 W% V7 S cout << endl;
9 @- G6 J% L6 T  R cout << "无向图有" << arcNum << "条边"<<endl;+ v' u8 f+ Y( k# Q- |
for (int i = 0; i < vexNum; i++)+ s$ Z$ U2 p( _* S; D) _
{
: M4 r' v+ @/ R, _' @       cout<<"和" << vexTable.data << "有关的边:";; k( Q6 Q' q; J- k
      p = vexTable.firstarc;
4 ~  ^8 @/ Q) L       while (p != NULL)
5 B/ f* D: j! C3 @3 D8 `       {* r6 p5 Q, L& g7 a
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
7 }: U0 R" B4 z: Y" i# I. Z          p=NextArc(i,p);4 x) L; v! y" k! p+ H
      }- `% b8 k# U" e8 F9 A
      cout << endl;; u: M$ d1 ~: l3 f8 y9 V9 h
}
& k, i( C. l7 p- X}
5 D. p) T3 A4 W' y2 _8 O- y  s1 T3 k7 s4 s9 q# g8 A1 a

$ \/ _8 K& _. f" H4 T' q0 p邻接多重表与邻接表的对比& _2 ]. z8 L! @& x. }

) I  |+ t4 n  p3 C1 Y1 p  P8 g7 g邻接表链接
5 e5 F! e: G' F8 G% [1 W+ |在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
% o# J1 x7 t! |: k- O3 u" `+ ~在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。, X! V3 j. i6 x/ s. G0 _6 C
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。6 |% m* d! ^$ y
————————————————
+ R7 ?- O9 x% l3 P$ q) _版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* v! @0 M; [; z; r0 S: |8 ]原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958; s3 N/ b4 f: c8 j8 S- Y7 n( _% s

5 K8 K- H1 W; A6 U& A3 Q4 N( V" b7 t" @% U( V; M
# G5 \+ q1 r- _) A! S9 e$ r; @
& r( \$ A9 _7 O1 ?$ |
————————————————. k6 I8 p# T* c. i, k2 ]
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( g. e; @( F) a7 w原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669581 p' X+ q! z& R/ D/ H! p8 s1 W! @& ?
' [' \; ^. C5 q8 z8 {9 E: J/ h) c7 S

& T6 ]& T( \3 P, l. ^) ]* w