数学建模社区-数学中国

标题: 图的存储结构——邻接多重表（多重邻接表）的实现 [打印本页]

作者: 杨利霞 时间: 2020-4-26 15:26
标题: 图的存储结构——邻接多重表（多重邻接表）的实现

图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：( p2 s& \' ]5 f4 x0 v1 N
data域存储有关顶点的信息；! w$ {+ W ?) Y$ V
firstarc域是链接指针，指向第一条依附于该顶点的边。! z1 C" m H% i: A
所有的顶点结点组成一个顺序表。

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;+ b+ d" J" d' e- L
for(int v=0; v<vexNum; v++)% O7 g* G" r  u, D' S
{/ K+ R1 D2 {, H5 K
      if(tag[v]==0)4 k6 i0 `+ D5 t5 C$ f1 k& h
         DFS1(v);( |5 h" q/ ?( Q3 Y! a1 g
}/ u* E% |2 Y5 b3 x6 @
}
7 `3 d9 e8 @: B/ ~7 E. ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
/ m. h# a3 P- x' q, E{* M8 b2 h- f/ d2 ]
stack<int> s;5 b5 i. W) ]5 F" g8 g' T- r% Y
int tmp;% O  M& ?+ h/ j2 f$ u4 H& c
MultiAdjListNetworkArc<WeightType> *p,*q;
% r  y' \- d% g# G7 k3 Y for(int i=0; i<vexNum; i++)
; Y9 h# e" B: R% L/ R; H       tag=0;' L& F: m1 s9 \6 e1 K' O% ~$ b
for(int i=0; i<vexNum; i++)% Z6 J# [, X! o8 Y2 G" P) \0 g( A
{. R' @- M* V& g7 k, X0 J2 c0 n* b
      tmp=i;
7 n! U- j3 C) M& \- _       while(tag[tmp]==0||!s.empty())
. y- \4 t, u$ V       {1 e1 m9 ~4 `- ]1 c
         p=vexTable[tmp].firstarc;
! v! T* H& }2 p& a$ y          while(tag[tmp]==0)
+ L2 W' f, X4 C& {! J, @# G' ^          {
; n% V, k- }# p. C. t             s.push(tmp);9 R7 Q) e( d* R1 v
            cout<<setw(3)<<vexTable[tmp].data;3 M4 U9 R: y1 X: a; X) D
            tag[tmp]=1;/ s3 O- G5 ^+ J# _$ d; @
            p=vexTable[tmp].firstarc;
1 y8 U# H3 t% K             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
( b5 o6 X7 r4 n- G# I             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
1 t3 o9 _( V7 n  `/ Q& ^             //cout<<" 1st    tmp="<<tmp<<endl;
( C9 [. Y2 V; ^5 I. C5 r$ ?" q          }3 R$ a3 V; Y7 d& O2 U+ y6 t
         if(!s.empty())+ t1 `1 B* b0 i, ~) X  W- F, \
         {
* {' o* U$ |5 z: Y. I& H             tmp=s.top();
* H1 m$ F* v2 y4 b; d# @             s.pop();
; B, }/ x3 r0 d& ~& M             q=vexTable[tmp].firstarc;
; I4 C) @- h; A: }9 s             int t=tmp;
: K' V. G% u% M4 l/ [             while(q&&tag[tmp]!=0)
! u, J0 i3 v7 [$ T3 W" [             {
3 H3 g  O- N6 T9 H% A                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);) R7 @8 b9 I* b! r& c; ^( I0 l
                  //cout<<" 2nd    tmp="<<tmp<<endl;5 o6 r  g; A2 r, H. C5 t# ?# ]
                  q=NextArc(t,q);# }( X1 [# o) r' O
            }
1 O  F6 E. |7 D$ |1 u' R6 W             if(tag[tmp]==0)
8 @  @4 n- r  G                   s.push(t);
3 r9 s( C# ~6 `$ x             ///1、对应上面连通分支只有1个点的情况
- h6 g7 c9 z( N) y) `! Z* V& u             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
: Q! G3 [! E. F& p  U! g             ///tmp要么等于找到的第一个未访问节点，
  r. _# k$ G4 E! E7 w; ?" w             ///要么等于与t相连最后一个点（已被访问过）
0 l7 p3 Z4 s0 k' V. N2 T% D             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
2 c% D$ K0 B+ P1 R1 m          }1 {( U2 a" X8 A7 c6 `! W, G
      }' K+ O4 a, a+ l0 P
}
+ L" G" u+ u* _1 w0 ^: k& `}
( X0 a$ {0 F' ?- R+ F" d  d//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1( |% l6 C! o# J% ^( d
template<class ElemType, class WeightType> int. M" ]/ S, @3 q5 e8 U
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)6 k- h* `4 m& A7 ^) O( Z
{
; E  j2 I) t0 p3 J* P if(head==pre)
6 z% n* Y! S* H' D7 z) |& L1 x1 P       return -1;' ?+ M9 x8 G! N' z! x

3 G. e; p& ]! [. l/ d  O- ` MultiAdjListNetworkArc<WeightType> *p;+ W% G; {7 Q7 s8 R& U
p=vexTable[head].firstarc;6 p" G* _, j! z7 r) b
if(pre==-1&&p!=NULL)& {! e6 ]- A* z, g) y  \
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
% u8 _+ G; l  }& t9 N1 S! }/ B //pre!=-1&&p!=NULL7 t  ^2 [! t: B. Y( ~1 F+ b
while(p!=NULL)$ @9 ~) l# T# c7 i
{
& A* M2 N8 K/ j* e; h2 p9 f       if(p->adjVex1==head && p->adjVex2!=pre)
8 j& t9 B0 h$ _  y5 [          p=p->nextarc1;2 R- N; j; e0 ?
      else if(p->adjVex2==head && p->adjVex1!=pre). Y$ `9 M/ f2 Y( z
         p=p->nextarc2;
! L* M9 ^/ |4 c; j* @2 I/ s       else if(p->adjVex1==head && p->adjVex2==pre)+ b9 d7 |& k: J  }9 }5 \9 {
      {
( _: ^( `6 f& [% D! Z          p=p->nextarc1;
6 H/ E4 W( @# t% w' h2 j) t! T& |# b          break;
+ Q0 W/ a8 M$ Q' a% H  Z0 ~1 ?       }$ ?6 [5 B  [, v% n0 z: ^  e% j/ B* u
      else if(p->adjVex2==head && p->adjVex1==pre)
8 `) v$ {1 Z. c       {
% I$ n/ s. J5 h# K6 L/ Q" H/ s          p=p->nextarc2;& e' x; j) {- @6 G# h
         break;6 u7 D# S8 M3 g4 d! O. m8 n. f
      }. R& a9 q# t+ E( v- o% w; S
}* V8 v0 }% {' j% @  }& E
if(p!=NULL)
, U4 c: S3 t/ d+ v {/ M9 L- |% t' A2 w2 w2 M1 f4 Z+ p
      return p->adjVex1==head?p->adjVex2:p->adjVex1;+ v( `8 y+ `9 \( ]' {
}: H4 a+ o2 w: P' z4 |: Z
else
1 V. z. V0 Q6 s0 n6 N3 n       return -1;
; I0 Z7 I$ w4 E) }  y# E}
: n8 u- ~, k+ T( y4 D4 e* i/ q- }7 u! d  M0 C
9 E* s6 I. M% {1 Y7 a# i* Z) A- s
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
- W% `4 ]4 A: r: y{
1 Q. q( P5 D  [; ^* |7 R0 G stack<int> s;+ q" n1 }, c& e: i: o2 g$ N
int p,cur,pre;& M) o/ X; n6 k' p( \" ~+ Q* S) D
//MultiAdjListNetworkArc<WeightType> *p,*q;
7 V4 j! A# Y+ |# p for(int i=0; i<vexNum; i++) tag=0;//初始化
: g* C$ N% S1 g) |9 [9 }, b" C' T6 s- o8 M# r% ]6 M  `2 Y
for(int i=0; i<vexNum; i++); u  [/ C# T, m* E
{$ }* M8 t, @$ k' T3 l( {1 A, e4 ?
      cur=i;pre=-1;$ u% B1 j! j, s7 m
      while(tag[cur]==0||!s.empty())/ q' C. _$ V! ?' e3 x
      {8 W* _$ w5 U& y8 x
         while(tag[cur]==0); \% J4 l/ H- y( h* F- R3 T& q, Q
         {
; [& r2 S2 t) L  c             cout<<vexTable[cur].data<<"  ";2 t2 e: e' }: ]5 T
            s.push(cur);& m# Z  x; @, K* e5 F; u
            tag[cur]=1;2 {* c6 u1 c" |: ]+ K
            //初次访问，标记入栈6 `- q* q' P$ X$ Z/ j, |

; m" p5 K) ^6 u# F3 @5 l! V% v             p=GetAdjVex(cur,pre);//p是cur的连通顶点7 ]: s$ _7 i' o- `+ s
            if(p==-1)( Y1 R8 J3 p& R- q
            {- T; g$ c  }2 [- W% x: O7 @# k
               pre=cur;s.pop();2 I' M: E( W4 _9 c
               break;
            }
3 Q- X: E5 _% O! S             else
' G  F- n% o( @1 ^1 t2 @( }             {! T4 ^3 p$ Q) z
               pre=cur;
: Z0 }3 f+ ~7 u2 E0 g1 i                cur=p;" D) E/ z0 f/ k, L0 E0 P
            }
" t# k7 B7 Y% E- w
8 F/ c% q. Q7 D7 @1 J) t          }
/ m2 A. T' {  y. R6 e          while(!s.empty())9 a/ n" K! B- n4 V4 w  o/ T) Z9 n" X
         {
! `" }) C3 t. G5 a* [7 R9 ?             cur=s.top();9 M* B* X) T3 S. i9 O4 b" k+ b: w
            p=GetAdjVex(cur,pre);
% |* r& m4 b9 e; E             if(tag[p]==0)& \5 l2 i/ q5 Y6 u( L8 ^; Z
            {) t  [) F( k: M4 B4 V0 l
                  pre=cur;
2 ?5 n8 k0 |1 C1 o4 d                   cur=p;! C7 T$ g+ P. L' \
                  break;
3 X+ H$ [. |" W7 \+ c4 X1 X             }: H2 C$ t; [8 Y! F2 d3 _$ [
            else* t1 x' U: l( y3 X* {, Y
            {* a& k) n* S. F
                  pre=s.top();' {0 o- _: r7 y
                  s.pop();
. F, z' d& F+ e1 L             }; G6 R- i  u+ H! [- M* z

- K$ S4 _1 |9 M, S# h' @          }
* _) `9 W% s- S( k/ s
* y1 Z5 o- v0 }' k& q       }
: ?7 L0 S+ w0 y& w }9 z- I  W, x& h5 h
}) v$ X$ X6 @/ y
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS(). _4 P) f* ^. L! h
{
8 C; H( S$ @" ~+ y for(int i=0; i<vexNum; i++)3 S; k: E7 h8 T/ p+ p5 g# N7 d
      tag=0;
+ E: d* i, h! x' l: k queue<int> q;7 w( `; Z' A3 `* p3 Q& o
int tmp,t;
- {; @9 N$ j, ^% r- `" i. D MultiAdjListNetworkArc<WeightType> *p;
. }8 N8 i! a3 A' V) ]' ? for(int i=0; i<vexNum; i++)  r1 ^5 ~  S4 n
{
. U7 A5 n/ G% @5 U' s       if(tag==0)6 @4 R! d8 j2 e- l" N# H+ y6 _
      {
: ?" }$ ?: l6 p, P5 z          tag=1;& u5 U" u6 y+ N& E
         q.push(i);
$ e1 W0 ]7 @. O# P; y          cout<<setw(3)<<vexTable.data;9 E; _  j) f% `: n" _! C0 Z
      }
$ s. F- h* D# n* O6 @2 Z       while(!q.empty())2 m" V3 w* w# `4 N9 x9 G; l. ]
      {
+ M/ K. ]; P7 L0 X$ V, j          tmp=q.front();
1 t2 e- H( i& y: y$ n7 q* L. X8 w          q.pop();+ z7 q6 o+ O& _$ F5 Y5 J
         p=vexTable[tmp].firstarc;8 M5 v. y+ U; m! ?' v6 J$ C
         while(p!=NULL)
! i' e4 r% h% [- ?" U3 |          {6 {4 W4 S7 O0 ?3 Z2 w
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);# T* k1 V, C7 a4 _! k3 t
            if(tag[t]==0)8 J+ E+ i, z: k* @; z. h3 P. P- u+ u
            {
% G. z& m& C0 L                   cout<<setw(3)<<vexTable[t].data;! r4 @" ]* O0 @) U/ r
                  tag[t]=1;4 W$ j* K4 g. k% h& W% b9 `5 A) n
                  q.push(t);. O& n% J* p$ ~! o
            }
7 P( N+ ?7 f. v2 }             p=NextArc(tmp,p);: [" [* B9 H4 \# Y& N  n
         }$ @1 X9 ~' J7 E/ T) q
      }- ]$ O7 j+ L, D; U1 O  Y- g
}0 ?6 P5 u0 }8 G: Y4 d) U6 Z
}
* ?2 m: ]% y* z, x; G; |$ stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
$ `0 k& C% p7 h2 A) R, Y5 n& V{6 N- r* z4 ]0 ~2 s
MultiAdjListNetworkArc<WeightType> *p;! ~9 B) V; ]# l
cout << "无向图有" << vexNum << "个点，分别为:";
! S( @- e# I7 j, G+ C7 w for (int i = 0; i < vexNum; i++)
1 _# t- E' Z" u/ p" S       cout << vexTable.data << " ";
' s$ @; o5 S( Y cout << endl;  ^/ F: s! O- p9 L& R' k
cout << "无向图有" << arcNum << "条边"<<endl;
4 R, L' F. ]/ j0 J# |, g/ A for (int i = 0; i < vexNum; i++)& O7 W) a, Q- d; |
{
9 P$ P8 s1 ^( s# ^4 }! N       cout<<"和" << vexTable.data << "有关的边:";* ^. a1 G5 |6 c( `! ?+ P2 q
      p = vexTable.firstarc;, k) [6 X+ e/ j. {4 U
      while (p != NULL)& s! `' T  f: K
      {
% C& z* u+ k; h' t6 ?& D# _          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";. g- g: m- p' C" g6 b! w
         p=NextArc(i,p);
9 Z2 H/ S8 ^. ~9 x       }
9 d0 y8 S6 M' L6 X" p; v% [       cout << endl;1 n) p: C2 w+ F
}
  E! M% @8 m: l1 M7 j* c' P4 o}% B$ S. Q. F( r; ?# X" U

8 F  w4 J9 d  v1 {2 V
3 U4 y2 l  l/ w3 u: x; ?( J3 Z邻接多重表与邻接表的对比
0 X9 e+ d5 H& n# t! {# s- d
1 O0 l9 V: D% J/ ^  c4 v6 l- f邻接表链接: f  s- e1 R  b. n5 N7 T2 O4 M
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
3 \2 x8 g) O3 X5 A0 M& F- m在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
5 D% ^9 \" w  V5 c* T为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
% P! S6 F/ o  h. A( s————————————————
! h: K, a$ @' `% B8 W, F版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。. N! p6 v# e: ~7 U1 y- G
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
9 M4 P3 ~/ w! p
; Q0 f5 m0 h" k1 m( _5 p  t, {/ T' c/ v( Q- ~3 p: h
0 J3 M- R( o" C7 V- }6 d
) Z1 E; l1 v: H3 b8 o" O
————————————————* u! c% J% Y( I3 K6 D  a2 J
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。0 q/ _/ J- E& N
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669582 A6 u8 B3 [) E. j$ V
' x# H! c. d7 p5 X; P6 h

: ~6 l1 X/ L8 M3 i0 j& u

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5