数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：! q' N* z @- W3 d m
data域存储有关顶点的信息；: l/ o) c; U" K } w- v) e
firstarc域是链接指针，指向第一条依附于该顶点的边。
) v& i5 d) p: V7 u1 X% @$ g所有的顶点结点组成一个顺序表。

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;
% V& h6 `: _6 X4 _, U for(int v=0; v<vexNum; v++)
9 r8 O% `( @: x7 I4 n, F) i* H {
" J1 N, G+ I" ^4 R) {: {9 `       if(tag[v]==0)" A7 E$ p8 Q5 P7 A# b( G# ^! U$ X
         DFS1(v);5 t0 ^  G( S$ ^5 g, ~7 N: t
}/ k2 s4 v' d: a" v* ^7 d2 p
}5 L( Z9 @8 J: N
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()4 G4 c& _/ O( G- ]7 k
{: @0 j+ a% Q/ S( _
stack<int> s;
5 P! x% ?8 o/ F0 [ int tmp;
! y& @2 q9 ^( s MultiAdjListNetworkArc<WeightType> *p,*q;6 f0 q8 W0 X+ }% x: U) Q! q0 ~0 A% ?
for(int i=0; i<vexNum; i++)
# n9 b( ]! N) c/ Z# W5 ]       tag=0;% _$ J- D: m. j# Q
for(int i=0; i<vexNum; i++)
* j* s4 l& P0 E& Y7 J# k {
$ G+ R! U9 @; ?" r8 O       tmp=i;
+ F( K" ?# m5 W3 d) v       while(tag[tmp]==0||!s.empty())! Q2 [8 q7 b  {; C3 c8 H- ~
      {  }( q4 n1 K2 l. C4 j) p0 T
         p=vexTable[tmp].firstarc;
7 }3 ], x+ ?% h7 W0 o$ r          while(tag[tmp]==0)
; o1 E8 @% |2 s% L' `5 ^9 w( B8 P          {" f9 l' M. [( {, C
            s.push(tmp);' M2 O4 ^2 u9 [& W3 ]
            cout<<setw(3)<<vexTable[tmp].data;
) K- |# i$ |$ w$ ?9 s             tag[tmp]=1;, W: R8 n2 L2 K0 K  o
            p=vexTable[tmp].firstarc;
# p$ j: }8 K$ G! M& p             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for: @! U& `& {- ]( C9 N
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);3 V4 x! g, X8 G1 O. g
            //cout<<" 1st    tmp="<<tmp<<endl;+ t& K+ H9 n" A# W1 _
         }4 O: t: O# m& {& i
         if(!s.empty())5 r& M0 k: x* Y$ b2 C, s2 s/ q
         {
- R) Y6 J* J3 M             tmp=s.top();4 q5 I$ Q6 m4 c+ m
            s.pop();6 T0 P1 f" O" }% [0 J, o' |( @0 @
            q=vexTable[tmp].firstarc;* y) \! T% Y' D/ W8 h
            int t=tmp;) A6 o4 B+ D( Q, V  v* x
            while(q&&tag[tmp]!=0)# q, [- [9 {* _' Y. H
            {* c2 B+ T8 f1 t5 L) s, N' T
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
; E4 l7 d+ @- }, T& S6 u% \+ k                   //cout<<" 2nd    tmp="<<tmp<<endl;4 `0 ?& f) f1 q& [1 G% M
                  q=NextArc(t,q);4 d5 B8 y$ e$ m
            }5 D. W+ ~3 [- E- Y9 J& L* B7 h! K; b
            if(tag[tmp]==0)
4 W" q! V0 r3 h                   s.push(t);
* i1 t* T! B5 H! C             ///1、对应上面连通分支只有1个点的情况) K; {+ P/ ~" E# a9 D" ^
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈1 s- g$ T* i- @- H
            ///tmp要么等于找到的第一个未访问节点，
9 G. Z/ v/ L7 Z             ///要么等于与t相连最后一个点（已被访问过）
( l5 j. {& J% h             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点' g/ p0 `4 Z- \/ f
         }
+ x  K$ f* ?! V9 T+ H5 i       }
0 ~5 B6 T6 {' a* O }
; m% B) p: x  S) Q0 O% ?}
& T/ E" r* J6 x# W4 v; M//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
- R  o3 c3 l9 R: V9 O8 A, stemplate<class ElemType, class WeightType> int
- e3 \1 }" v, \, S0 pMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)' m" n; d& T* g' `8 y! G# h3 C# N& ]
{& J6 O- Z# T/ I+ o; i; U* g3 L
if(head==pre)
' O& ~: k5 K) L0 q       return -1;
' y$ }2 {( y+ w+ ^" X# K' g' c3 {0 I3 @' n% P2 w
MultiAdjListNetworkArc<WeightType> *p;+ b1 R1 W- o9 j7 l, K1 p$ B4 L- S
p=vexTable[head].firstarc;1 M: v0 v% g) b- s
if(pre==-1&&p!=NULL)
; E1 y' i- q1 s       return p->adjVex1==head?p->adjVex2:p->adjVex1;
. e. [# f/ |! D6 w //pre!=-1&&p!=NULL& r% m" `8 I- C1 J0 x1 Q' Y
while(p!=NULL)
/ P& z" d) U$ s' b, ~! Z. u {# W, |' z! `1 z0 z2 z; J4 H  a
      if(p->adjVex1==head && p->adjVex2!=pre)  k9 \# j$ o3 S' q
         p=p->nextarc1;6 X5 r5 |8 l- L5 z, y) Q
      else if(p->adjVex2==head && p->adjVex1!=pre)# T& @, q- b8 o( N8 g8 a
         p=p->nextarc2;- _! m' p2 a2 t0 T7 B
      else if(p->adjVex1==head && p->adjVex2==pre)
9 C, [; f* [( ^/ w' _       {: m: w2 F9 Q+ j! X
         p=p->nextarc1;
9 T$ u: ]+ Q) P( J( d! q" W          break;! v. z7 Y+ P( K' [8 N1 s
      }& o' p: U% N' s. U. i( l& E! K
      else if(p->adjVex2==head && p->adjVex1==pre)
6 F6 O6 y0 w; O: \3 q4 }       {
$ w3 R; Z/ m& t; m6 q: ?$ t1 \          p=p->nextarc2;( u! b3 ]# M; Y+ B9 m/ p
         break;! M6 `1 N2 F" v3 V( W; ^) t
      }
; n, G- i2 }6 ], N! b; g/ B* \ }! ?9 ~9 B/ z, ]+ d0 e
if(p!=NULL)2 $ ~6 W1 U# X1 W
{  e' }# f+ B/ y& y4 }$ \% n
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
7 G, w  |, P# U* A7 h# I1 T% u }
" {0 D; N2 k# P7 K! N else. ^. T2 P6 L' ]
      return -1;
; I4 A$ [8 X3 b7 L; x1 ]}2 k- {+ ?: ]! E" O' g9 V
, s' A# y0 $ K0 A7 o& \

3 h/ A) C9 ^1 i% f; y% Mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()4 {9 K1 y5 {* a
{2 |/ l' N1 W" x+ ^/ F* y) `# }# \
stack<int> s;. i% j2 ~: X( N8 U+ X) E
int p,cur,pre;5 M( M2 Y8 t9 [4 u, P: L  L
//MultiAdjListNetworkArc<WeightType> *p,*q;
" s7 V" b+ d/ }9 s1 W/ Y for(int i=0; i<vexNum; i++) tag=0;//初始化+ t. D- R3 f8 ]4 n! _! M5 W$ U; e! F2 w

$ ~! O  N4 p+ t2 O. | for(int i=0; i<vexNum; i++)
' o* m9 o; z9 `1 I0 a- }4 h. l9 C {, c& v! l" |/ F9 B/ d
      cur=i;pre=-1;
' |. C: P3 G' F* P. n       while(tag[cur]==0||!s.empty())# T/ A1 d; t0 N3 d( |1 K
      {
( Z# a" A, V0 z8 i" p7 ~          while(tag[cur]==0)6 N  S5 H' k+ R
         {
0 B( U# b6 k+ a! t/ n, g             cout<<vexTable[cur].data<<"  ";
; w7 U# s9 ^. r" I- h2 y             s.push(cur);
+ N! N9 X! Z3 p$ I# w0 q& w- X             tag[cur]=1;
8 z3 k& r7 K1 G/ {" J; v( q8 V. [$ F             //初次访问，标记入栈( I. L9 L% H6 q4 [

9 p' y8 k4 ?1 t/ g$ E             p=GetAdjVex(cur,pre);//p是cur的连通顶点
( K0 s* u9 Y6 T' k5 {0 G             if(p==-1)
2 f8 v. n4 n* u             {
, e* h0 {: g& Z                pre=cur;s.pop();
4 S( t1 ^, \* T3 ~% \- U                break;
. R! B+ u1 h9 Y" @             }( [6 H0 s3 w9 a$ m
            else
2 w  }- P* d( F8 G" E9 ~             {4 r4 t0 q/ M9 f/ U; }
               pre=cur;
+ }( E5 X1 I9 w( L! N- O. a8 T                cur=p;
+ q. ~. C* u( e7 O& ~             }
6 O7 p/ I# O4 Y9 L! X& _/ y' Z/ J, ?
         }
& C3 E0 S1 M8 M          while(!s.empty())4 w! O3 y. c$ `8 Y
         {* Q) P. f4 e6 Z) p: J
            cur=s.top();* D+ _6 x8 Y" ~% |' N
            p=GetAdjVex(cur,pre);
8 {9 F/ q) C7 O# d! ~- M             if(tag[p]==0)' H  i& d0 Z2 q( u+ K( G3 t
            {; f$ m. B* Z4 n- h5 u. m2 {
                  pre=cur;
- |5 N/ x% y7 ]: ^5 D                   cur=p;/ j: o, P7 ]6 P* l' n
                  break;; w* Q) ?! L5 L7 h! y4 [) }
            }+ x7 M, @9 V2 W4 \( N, E/ D
            else. J: |/ n1 c  q1 \$ E
            {
0 B! z4 w0 ^7 W                   pre=s.top();
8 Q" |3 ]; h- v. Y2 ]3 B                   s.pop();
* ]' Y6 V* z9 f) p( s) t! h             }
2 H: f2 S2 u; i* a+ ~8 B6 v7 F: @% R- Q  B3 s
         }& ^4 h  p" ^% T

+ m% j& c/ R2 p4 J$ ]: p+ A3 P       }
' h! g9 k6 i  _: W0 w" O: \ }: t( e7 ]' L& z5 I, ~. ]- U% e, h
}! c* M% U6 T% T2 N6 W/ u+ U# g' _
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
- z2 v* T5 J; V. x# @9 z$ i for(int i=0; i<vexNum; i++), i" r8 S# c$ N' H: `
      tag=0;! Y! U6 Y3 o, c$ C: _2 N% J, v
queue<int> q;* V& A5 k1 D) r, }. v
int tmp,t;
4 M7 V: h! z6 r- f0 k  c1 a, B MultiAdjListNetworkArc<WeightType> *p;6 G5 `" U( h) H2 z
for(int i=0; i<vexNum; i++)
( r* I6 s- ^9 _: c) D. N! Q8 W {
' d* L! @* o. [' p, M! P' z) {       if(tag==0); w# S+ T, C. e% S: P0 t
      {2 R$ M1 P4 P4 G# W2 Y* Z: r
         tag=1;
0 `1 I" B' u1 v' h4 f  I$ e: v; w0 A          q.push(i);
2 C0 Y" S4 ~! E. `5 X" t5 f! v- G4 |7 v          cout<<setw(3)<<vexTable.data;
1 i4 L" G; R) y/ M/ B       }4 E1 }" \( h5 v1 L/ S: B" M. T7 J
      while(!q.empty())0 C9 c* g, Z+ F4 N  k3 Z! w( ?
      {$ ?" @, ^$ r. ?* z# V& K
         tmp=q.front();
& \- z+ \4 C& U. `' a5 Y) [4 F          q.pop();+ A# f% w$ \. e& ]% {: [
         p=vexTable[tmp].firstarc;4 A& @2 ~& r8 c/ z. k3 i2 {
         while(p!=NULL)' c' ^4 l! m: s/ K1 r* Y  Z$ E/ d
         {- e, f; |; |8 R2 V& l- V
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);$ {! i0 d7 m5 ~  j" u" |: P
            if(tag[t]==0)  O9 A2 q: v; |, u
            {
7 d  C% J+ \& B9 c* @* q. g( z                   cout<<setw(3)<<vexTable[t].data;! I  M* Q6 @' G5 H8 R  h( O
                  tag[t]=1;: h% w" A) o8 R% I) s# [
                  q.push(t);
7 H% l* o0 Y5 E& I7 q) @; Y3 v- E             }( M; J, y+ V) C) j! h0 X
            p=NextArc(tmp,p);  I9 w. x! B  o- f4 }9 k
         }9 D5 i7 B+ w, z( ^/ d) G2 _) r8 a- R
      }2 D8 s; ~# e  |! R
}) l; `6 G% c3 h' r
}* Y4 x& l) _$ m/ ^+ {9 a
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
8 o; b8 F. `4 a. l{
# I- f6 `( [/ D/ _- t MultiAdjListNetworkArc<WeightType> *p;/ o* G4 X% e2 j2 l
cout << "无向图有" << vexNum << "个点，分别为:";
, z% c' T3 r) w8 Z+ V$ u for (int i = 0; i < vexNum; i++)
& G/ c4 K7 i6 y, z       cout << vexTable.data << " ";  V1 K5 Q9 O+ @& x1 t/ @9 J
cout << endl;
; B6 L7 r% q' g0 a* l# N! R- R cout << "无向图有" << arcNum << "条边"<<endl;
2 \& R- V- U4 F1 n- t for (int i = 0; i < vexNum; i++)
' U5 C) Q  o" }1 b {
( m0 s! x& c' W; u" V# T! T       cout<<"和" << vexTable.data << "有关的边:";/ ~5 H8 R2 ]4 ^1 T
      p = vexTable.firstarc;
; c; f/ i4 [6 w; ?9 M( @& }% R       while (p != NULL)
) ~4 g. A) i) ~) B; y5 V7 I       {  ?1 x4 [5 H0 k, p% I$ u
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
9 @" \$ p. V0 ?$ Y3 u- d$ j          p=NextArc(i,p);
& _3 q8 Y9 K2 H* L  m! u8 H       }
& O4 @4 F! y) n2 x+ f       cout << endl;6 H% j/ J( Z3 U
}
) C/ {6 {8 t8 d! ]5 I, R}
! B& y2 U1 D: `+ }& {' s
' P+ ^& ]' `1 \7 d) b$ P) R* h( O4 M- l, }* r
邻接多重表与邻接表的对比: L$ V( l( N% G3 a) y) a
! r- J+ L8 X1 T
邻接表链接
# n/ S+ }/ l% l在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
1 E  R9 }& O( d0 H) P在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
' c7 B! r, \3 Y  \% D' I为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
4 T) z9 e+ z1 o% A& a5 h————————————————( l" e! o" y" f
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。- C* T6 m+ p! r0 j2 I
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958% B% \; \* E" u5 W& q! p
& M- w6 L0 J8 d5 |" D, n5 `
9 |! @5 I! U  t

: U8 y) Y- k7 G. r7 f2 A3 D0 p
) \0 }7 ]8 k' e+ C3 q————————————————
( [; `7 M* y( F- K$ y; y  P版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。% R) y$ x- N* d+ W7 m
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
0 ]0 N9 U9 [7 L- h- R* `8 Y3 Y+ ]; _2 z, j0 }  R7 h; e+ z- A

: B4 o& b4 a  i  o; E

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