数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
9 ^9 U0 P% ?4 S! V8 s9 A2 ]data域存储有关顶点的信息；
3 [* ?4 i% h) g1 @. h- C# @! mfirstarc域是链接指针，指向第一条依附于该顶点的边。* Z1 I3 o( O6 j) l v6 r% k/ 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;
) y- {% F$ T8 S" ^% P; g+ `4 L3 K' P for(int v=0; v<vexNum; v++)$ R; j. t# y" h' ^3 P1 H
{
* F4 I) @8 x- a3 O       if(tag[v]==0)! V6 X3 n$ R1 D' q* ^# F# d
         DFS1(v);: U, V  J! a7 y: K9 q6 M
}
' A$ U; s8 a1 M1 b, w8 c}( K5 ]/ L# X" y2 j- b% X
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
' y3 d; u" F4 j6 a2 h7 O# c{
0 W) M, q( q$ ^+ J! i5 v stack<int> s;: L5 p4 V& e3 N" [; K
int tmp;
2 o# Q8 n) M/ H+ K. R5 Q/ ^ MultiAdjListNetworkArc<WeightType> *p,*q;
$ x2 l0 X/ ]* a6 R4 a6 l/ P: ?- E for(int i=0; i<vexNum; i++)
& [7 P2 u! E* d6 ~       tag=0;* O9 w7 p4 B. q0 L
for(int i=0; i<vexNum; i++)
* ]9 ]& X* n/ w3 G" e1 u# ?+ K {0 c/ A) Y+ w+ U1 y$ m9 T- B6 ]
      tmp=i;% l# I4 I/ R( V- D4 b) E
      while(tag[tmp]==0||!s.empty())/ {0 t3 k6 |" Z4 I
      {
. |; D! G1 c: ?/ n0 t          p=vexTable[tmp].firstarc;
1 J! N0 F: f$ T1 a  ^  A          while(tag[tmp]==0)
9 ]  V9 Z4 c! z; j' w! y) g          {6 n9 E' n7 ^# G9 R2 X
            s.push(tmp);
& ~1 Y; O4 h1 q. [5 W  \             cout<<setw(3)<<vexTable[tmp].data;
8 T2 i7 H) `/ S, _9 O             tag[tmp]=1;9 z7 I! e7 a$ G6 U6 J
            p=vexTable[tmp].firstarc;
" ~9 E6 @$ a, i" V) B8 _             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);/ F: s8 w9 L5 i+ b2 L
            //cout<<" 1st    tmp="<<tmp<<endl;
' Y6 `& M! [( t6 p7 X+ T) Z          }
) i$ x1 ~+ B9 Q1 C- c          if(!s.empty()); Q6 I  D" G( W% S1 D* o- h
         {
! K3 ]2 P- I& g# d: z# G* P             tmp=s.top();1 b6 {1 [: q+ h# W5 @& Z
            s.pop();
  m. y2 y; F; d# t& _, w             q=vexTable[tmp].firstarc;
' p2 m# s" Q2 c& m7 p9 C' c             int t=tmp;  X/ e) ]+ z1 R( @9 Q
            while(q&&tag[tmp]!=0)
; M3 m" W7 j7 g             {0 {: [9 \8 I( w4 ~* {( I
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);1 U' T: {( ^4 A1 e; `$ i0 {- B
                  //cout<<" 2nd    tmp="<<tmp<<endl;2 f1 T% l3 O. c4 R# T0 n& _
                  q=NextArc(t,q);" X% ?+ O5 N# y6 ^# I4 B
            }
/ ]/ M9 O+ Z% `2 \) _. i0 K/ o             if(tag[tmp]==0)
5 d9 P0 W5 N8 ?& t: V                   s.push(t);/ a+ g9 h; F/ o( Q9 g
            ///1、对应上面连通分支只有1个点的情况
8 l# A' ?3 l( s# T6 W             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈  [' \5 L/ }; }* }2 H& p
            ///tmp要么等于找到的第一个未访问节点，( D, R  }" ^  w& L3 ?" s
            ///要么等于与t相连最后一个点（已被访问过）
! ]+ P- Z4 I5 F  Z, [, w             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
# [3 \6 j: k, {1 ?' ?* S          }5 r9 D+ u+ U/ ]1 e, |1 e& f: y8 T
      }
+ q# t: @* o! k1 C* J }
, z+ W, u5 r3 V1 ^2 h/ F}& a3 P# }9 N* N& z" I
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
- u, F; @& _4 n: D( ^template<class ElemType, class WeightType> int
" f! c1 z- e6 n* V( T, A$ UMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)+ ^. m6 G6 n& X: ]6 Y
{
8 E% ^6 s* v, N9 F if(head==pre)
3 p8 I% G8 x3 B. K0 |' F       return -1;  t1 S( @1 p$ \/ x
6 o- ^0 \9 d9 W
MultiAdjListNetworkArc<WeightType> *p;
+ s; u/ s+ w& d4 A1 \3 u+ r4 p p=vexTable[head].firstarc;
3 I- h* e7 y& O9 P if(pre==-1&&p!=NULL)
. e5 l) M7 X( |; m- e2 `2 q4 U! r       return p->adjVex1==head?p->adjVex2:p->adjVex1;9 L" R( j* a$ m7 B, B: T0 n$ r- Z8 i
//pre!=-1&&p!=NULL8 Z% O2 f6 C1 w, }; K! c' O, Q; Q" S% N
while(p!=NULL), Z. p+ s# R6 Y* I
{& `  c6 M0 D8 s: P
      if(p->adjVex1==head && p->adjVex2!=pre)- f3 K0 L2 g, A9 a# M& h
         p=p->nextarc1;; ^& h3 X+ V  Q7 s0 I
      else if(p->adjVex2==head && p->adjVex1!=pre)
5 c. ~9 y1 W( M; m- d' H          p=p->nextarc2;" i  H2 d: @' @3 t; \# _
      else if(p->adjVex1==head && p->adjVex2==pre)( U7 ?  `/ ~/ V/ g0 Z
      {* ^& L3 b- U2 Y" D/ u( R" c- F/ ?
         p=p->nextarc1;
  v  H4 V) `( q& e  J+ s7 k/ Q; f          break;
$ N2 c2 U9 ^/ H" k6 _       }  B" B- P# _4 g! D( e3 Q/ I" Y9 A
      else if(p->adjVex2==head && p->adjVex1==pre)
: ]. s2 ?) ~+ L" j9 Q5 {       {
2 B' K/ o6 P, E2 |8 P3 c          p=p->nextarc2;" @; p) H) H% L- T& `5 ?6 m2 o6 L5 X
         break;
- \% H1 v1 o4 T( F       }# `( j& b! A8 w  c0 f3 X
}
: {3 {* ?5 V7 b/ G9 I" f: L if(p!=NULL)
1 a# Z; D6 D) x& M {
' V' v: j% J" G7 i       return p->adjVex1==head?p->adjVex2:p->adjVex1;
3 g) f  E& N( T! |& c: V4 R }* ?3 L$ J5 P, w$ n5 ?1 [3 N
else3 M) s! v4 {/ P! D
      return -1;, S7 X7 V5 w5 P' B8 E
}
$ _  W+ o5 w5 u+ n0 d
; |% z# y% @9 R7 H
* t9 s4 U9 c+ l- v( ctemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()5 }1 Z3 {: P8 v
{
8 _3 R9 Y, r6 |2 k; q% L stack<int> s;
4 E. V# Q1 V8 a3 R% k' h0 v; u int p,cur,pre;
1 S# A" n4 _* _8 X, N //MultiAdjListNetworkArc<WeightType> *p,*q;/ v2 u: u$ ]2 m5 d( S
for(int i=0; i<vexNum; i++) tag=0;//初始化
3 l7 c9 C# A. l* @$ |, I0 B, r1 R4 q+ ]& ?- e
for(int i=0; i<vexNum; i++)
% [8 _, S, j2 e, I3 N( f* j$ f {# \$ I) X4 h$ P3 @
      cur=i;pre=-1;6 L: @+ Y: L; R4 J! g& A- U. P
      while(tag[cur]==0||!s.empty())
+ t9 C: ~2 u1 X& ]& N6 |2 O       {9 X; s# G0 }# \  b; g7 o* x% @: c
         while(tag[cur]==0)/ D& e/ T4 c/ M9 u2 l
         {, L, P; @" [# X
            cout<<vexTable[cur].data<<"  ";# V% g8 I0 s9 Z" V3 ~# q7 d
            s.push(cur);
: @. a6 E- Z6 p             tag[cur]=1;
1 R; U- u6 g8 p$ U6 [/ b  Z             //初次访问，标记入栈
; d& U$ U) I- w  Z+ q
4 q  H4 w& g4 Q# ?2 E             p=GetAdjVex(cur,pre);//p是cur的连通顶点
  @1 K* e6 n0 W* n             if(p==-1)
$ a* r& h2 l5 h+ r9 ?1 x# O             {
* ^% m9 Y7 c9 v7 q0 u# Z7 C0 d                pre=cur;s.pop();
: K4 f% c2 I; X) O0 o5 h# f# E1 G                break;7 w, w, o. e3 `0 ^% `0 f2 h% e/ N& M
            }
* I2 O+ X0 z7 ?8 }4 \/ `& z- H             else
: \' @3 ]& m9 ]3 f7 O, @# Q             {- I! |7 E: S' j( h+ u4 z
               pre=cur;
' _" D/ b% Z9 R6 H1 }0 G% I4 ^                cur=p;/ b! n% g1 ~4 H
            }  v% X6 C' K& `) M4 B/ t
  M" c$ \! R; }' G
         }
, N' k. }' R8 W9 c1 c* R, X& U( q: ?          while(!s.empty())
+ X( x  M/ u2 E7 h( ^; L          {& n. }" P0 H& u/ T$ {0 {( G- ?9 E
            cur=s.top();
! B& S+ k9 w  }8 w. `) S3 V$ Z5 q             p=GetAdjVex(cur,pre);
3 \: F1 @4 V6 |9 F7 T/ z9 \  `             if(tag[p]==0)
. u5 @. J0 g+ D# i; [" F& H             {
* Y3 T; x8 ?( G                   pre=cur;
8 d9 E- @" m1 T                   cur=p;
* s. B: ^4 b; }: C9 q                   break;
/ Q+ R: N8 ~' U! ~. Y             }4 C7 q# E( j7 `( I' K. j6 @& n5 V
            else
0 k' d# G, l9 ?/ @! \2 x4 z4 \( H             {& I  m7 h  Q* h$ N* T, x
                  pre=s.top();
5 a$ J: h6 A. p, x! s                   s.pop();
) z/ _( S" E" @( B. x+ v             }
0 z) g! o1 b! ]
& O" b4 }! I' e# {          }( P( F2 _9 H# P: ?0 i

0 {0 t8 M1 N, k& T) p. _       }% }7 ~% t1 l" U% U1 r9 |& V! Y/ `% W
}7 s: X0 w, C, i. G' A: ~' Z
}
' f* {; u; M1 ^+ k% b7 I" d2 ?# f8 btemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
% a/ `! f7 W% d{
4 F+ f3 z1 y% h4 k; K for(int i=0; i<vexNum; i++)
' e" G+ h) A' m& g9 |! f  ?0 I       tag=0;  d* g8 X5 j& `) o" y
queue<int> q;
0 S6 g1 ?( j: h$ J+ [$ ? int tmp,t;
* I$ M: j+ Q8 Z$ o9 F MultiAdjListNetworkArc<WeightType> *p;
1 s. z' I+ p* O" \7 R2 z' M3 n" B for(int i=0; i<vexNum; i++)& T- v% a% z8 @! A8 z' N8 f. Q5 }0 ~
{  J3 \0 I0 V0 `+ n7 ]7 J4 Z- ]
      if(tag==0)( {5 @6 D: [8 b0 f  {
      {# A$ V, y$ J+ h) y* q! _
         tag=1;
$ l+ p. L) I4 G6 B          q.push(i);
! j8 w( [" T8 K0 ?$ f" _          cout<<setw(3)<<vexTable.data;- `- }4 C' d3 O, L( ?) @
      }  k! L; W: e2 W2 g0 p
      while(!q.empty())
' I& }  G& l/ W" [. W0 D8 G; ]       {- i$ H2 x$ Y% W9 X
         tmp=q.front();7 O1 r- ?6 X8 k( h
         q.pop();
. |- L: q+ P* v1 W          p=vexTable[tmp].firstarc;
; l( f; @& J& q          while(p!=NULL)' j; `6 T, G" r
         {, a+ \# o5 Q, K# Q
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
; J$ E& S  }5 |; [3 t             if(tag[t]==0)+ o( _) o  r& x- Q7 `3 m
            {+ V' ~1 t7 W' L2 R
                  cout<<setw(3)<<vexTable[t].data;7 m# a8 E$ ~  Z& Y4 i; U
                  tag[t]=1;
0 F! M# y: b8 e- @                   q.push(t);
2 `8 g9 ?, `* z, u: G             }5 q; k( z$ }# ]' m. W. N1 r* a8 q
            p=NextArc(tmp,p);
; ~, C% h/ `& a9 e! b; c, s          }% N  b3 K: R  Q& r: i  M
      }" T) o5 ^, i  Q# t
}
' p% Y" ^" F+ v/ p# k8 n}; Z- r8 z0 H, m
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()0 U0 c& \# F4 i1 i; M
{
3 g% \$ I  e. S MultiAdjListNetworkArc<WeightType> *p;
3 U: v; H4 s0 H! x0 d8 H4 M$ G( m cout << "无向图有" << vexNum << "个点，分别为:";" h- `" V3 G+ |4 F  _9 f0 W  k
for (int i = 0; i < vexNum; i++)
  m, D! v0 t4 D+ Z8 \1 R1 N       cout << vexTable.data << " ";% m% p6 a. q' j8 j9 d
cout << endl;3 Z7 w& ~: n' d: V0 h% ?9 x9 [
cout << "无向图有" << arcNum << "条边"<<endl;
7 H* J( h$ D3 u3 i6 g0 `2 v2 C% g for (int i = 0; i < vexNum; i++)  E# Z7 N  n2 _
{) E7 T" i1 ?+ A  M0 l
      cout<<"和" << vexTable.data << "有关的边:";# D- [$ Z4 `# w. o
      p = vexTable.firstarc;% Z! a7 Y& U4 U( n
      while (p != NULL)5 w6 {7 i2 ]2 z' _7 H
      {) O6 h; j, g0 i/ W' B/ ^( |
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";( ?# N+ w9 c/ l4 N' k8 A( C
         p=NextArc(i,p);
0 w. F* ?3 B  q# f       }! Y! q  T$ j- f& G8 K
      cout << endl;
2 i7 d; N7 I. K }
) f0 m# T" @& D0 i# w. V" ]  q}
' f2 U, I' I' w$ Q: l& Y5 O9 B2 S3 p2 p2 C: a! @
2 R$ s. r/ C( b* d
邻接多重表与邻接表的对比
$ f3 u2 J8 [$ C5 C( E" Y+ T3 s7 |3 A# O; Q5 z8 s; m( \
邻接表链接
$ V: m9 b$ q1 S. Y* s在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。8 X1 V: ~& ~1 w# c; H
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
/ F" K, c2 y# ]: @1 d  u2 P4 [为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。4 ?" }& f+ U! E" A8 M/ f: X
————————————————
. n' t6 B7 A. x7 n版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。9 t& H6 `, ~" x
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
# D$ Y3 j  w; }: h& T/ O4 R: I, |! M5 S& R) p
$ y( @  \! n* Q9 @  W
6 w! C; W9 i8 d* A4 O. w. K
6 l4 i+ c* H* y0 [0 @- M7 K
————————————————
: p. H1 [8 C# K6 J3 n5 J版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。7 t+ q) a! k2 a# b5 R
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
- D: M; t' Y# B6 F
2 m, w: |2 J! g1 G1 R
) {* q2 g  z' h  P  t: W

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