数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
3 p R/ {7 F0 E- Vdata域存储有关顶点的信息；! i* m3 G( @& a3 F
firstarc域是链接指针，指向第一条依附于该顶点的边。
x9 o4 z3 W/ |& w# z6 ~所有的顶点结点组成一个顺序表。

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;
! X: P; E' G# N- E for(int v=0; v<vexNum; v++)* L! d9 _& j) W) {
{
7 P4 m; A6 U' b       if(tag[v]==0); n& J/ b2 q, [3 T, f6 b
         DFS1(v);
5 G5 Z  c& ~1 j. N9 b/ l4 _$ g& m: o }* Z) b' M; O% S; Q, ~
}. p  l4 q+ k: N' d6 P  ^2 P& @
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
0 Y) ^+ S4 |& j0 `2 G( a" F{: C; P. o$ w" x$ ?; S  D$ N
stack<int> s;- u7 H. }9 k; D, G  U6 q% y8 ?
int tmp;3 @- g% c2 G; Y6 r9 r: P+ }
MultiAdjListNetworkArc<WeightType> *p,*q;, R$ H$ q& Y, ]" n0 I8 h) y
for(int i=0; i<vexNum; i++)! {3 n1 R, C2 n9 V! d
      tag=0;( |1 g( v+ C! ^" p
for(int i=0; i<vexNum; i++)( k3 J, s8 P" @% @0 f* {
{' _9 p3 m+ w% k% |8 M% s6 U& c
      tmp=i;
! m4 C( [) ^3 l% S) J- ~       while(tag[tmp]==0||!s.empty())- v( v1 U9 ^9 K4 p' A9 m
      {) U! Z! V6 [" g1 x% U  m6 t0 A
         p=vexTable[tmp].firstarc;
. Z$ Q- w, W7 o- U          while(tag[tmp]==0)1 ^( \. b8 A; D' U5 {
         {  \# E% u8 |9 V, Z# B/ F
            s.push(tmp);
6 n; @9 `3 |" [             cout<<setw(3)<<vexTable[tmp].data;, v# F- N' P" H1 o' Q+ e
            tag[tmp]=1;
& \: f6 ~% Q$ B: |, t             p=vexTable[tmp].firstarc;: f5 {7 u4 s* V! Z9 T
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
' J6 j5 t( I1 Z0 V+ v2 S2 U/ ~             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
& h  C- B! {5 z8 W" W             //cout<<" 1st    tmp="<<tmp<<endl;7 z3 f$ @# ]0 s& r2 ^5 p3 a
         }. |0 N2 H  O; R" r4 S' Q
         if(!s.empty())1 z5 G5 E' t8 h( ^" W" [: B
         {
9 J6 A4 ]1 u* `             tmp=s.top();1 g& m4 L+ _; T8 W$ y7 j7 }$ i. ?
            s.pop();! [$ J, a5 M6 X) Q3 v
            q=vexTable[tmp].firstarc;6 C% v2 x! J$ ^$ Y* i* A( }7 r
            int t=tmp;( W* G7 R1 ]8 l# l+ {
            while(q&&tag[tmp]!=0)
4 j3 Q+ f7 g/ w             {
4 m7 r) C2 o* \, p1 D                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);  k0 s& f8 |  `9 f4 M
                  //cout<<" 2nd    tmp="<<tmp<<endl;
, s# ?( d+ x0 L# |5 F( P                   q=NextArc(t,q);3 [# R) D& L( o$ M. k/ b
            }+ `& w9 W1 o& I2 ?. S
            if(tag[tmp]==0)
, m2 s' z. H- y6 ^                   s.push(t);
, J0 d0 Y: I6 T6 x2 [- @             ///1、对应上面连通分支只有1个点的情况5 N: l' V1 i& Q& K% C0 N( e& k6 l9 b
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
& Z7 B$ S. p! u) Y& k             ///tmp要么等于找到的第一个未访问节点，; \5 }2 Z) ~% U+ N$ [
            ///要么等于与t相连最后一个点（已被访问过）
5 M8 u) o3 M/ V4 P; [2 H$ @- T             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
3 A1 p7 D& f! D- Z( z$ C( b          }
3 G6 A/ d, I) z$ l: X, `       }) J* l+ |5 \. R
}
6 i2 g1 c+ w1 Y}
3 X5 l) d2 ?4 y1 b/ b3 G//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
+ o( t/ J5 I! {; Atemplate<class ElemType, class WeightType> int
8 m& S' Y6 E5 V0 n; U  iMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
% E: J- G6 C0 n, {& ?; k{
8 g/ ~9 {2 [- }+ M if(head==pre)) o" o" ^1 D* B1 D( N2 M
      return -1;
9 i5 f2 S: r( S1 r% @1 W7 R1 K9 P: m2 u, E' ^
MultiAdjListNetworkArc<WeightType> *p;2 Y! M' `0 K. N! Y8 n
p=vexTable[head].firstarc;
2 \' W) D9 m4 K% Q( { if(pre==-1&&p!=NULL)# ?, p% h  V2 l: M1 ]0 H
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
$ ~1 G0 D- X. `( E7 O4 ?+ i //pre!=-1&&p!=NULL: P8 ]& \- z6 R; Y5 `! M7 V
while(p!=NULL)
9 }' v: d# V2 |/ h) |/ i {2 l! R( `& A# T  s
      if(p->adjVex1==head && p->adjVex2!=pre)
7 B4 Y$ x/ y0 J; Q0 p" E! V0 S! m          p=p->nextarc1;
! N3 m3 k+ v" g, U( A: `       else if(p->adjVex2==head && p->adjVex1!=pre)
. d  Z3 b0 ~$ k# v' G+ c5 u          p=p->nextarc2;
0 J( l1 l9 M  \* T- l  n/ ^       else if(p->adjVex1==head && p->adjVex2==pre)
: X8 A- B- r6 v. {. m1 i) n- x       {8 h$ l% \: Q  O, d1 V
         p=p->nextarc1;
, z4 e+ u( @$ |5 q' X7 I' U: H& X          break;$ K! j! |& p, f: a  a
      }
; B2 O0 m/ \9 j0 u       else if(p->adjVex2==head && p->adjVex1==pre)
/ M& x) E' z' k$ x, z       {6 h: \, A0 @1 {& t/ s9 C" J& K
         p=p->nextarc2;/ v; [& O2 `- ]( U# r/ o6 u
         break;8 A8 a. K2 z# e1 j/ Z/ Y7 y5 y
      }
9 b% V5 z" i; @. f* P$ Z5 V9 w  r' c }0 `  F. I: m3 a" W+ K3 w0 e
if(p!=NULL)6 t6 q" [  v, D' q3 [2 h
{/ ]& ~$ T& a# e
      return p->adjVex1==head?p->adjVex2:p->adjVex1;) H1 I/ u# F' c& a: y3 \
}2 P* p2 f# V( U% `- E
else
7 w0 G9 ?1 k$ t. r) L& |, Q       return -1;
0 _% E7 S; r7 u  o2 c}
. p7 Q# a7 `. |8 `' [: Z3 ^+ A* K% L0 \/ D
' x0 G3 C$ u* M1 Z1 U% Q% q8 Q5 e
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()7 T; d. o4 T! Q2 ~) B
{, }: x1 X# m4 d6 @: i# L* e; R7 s0 e
stack<int> s;  v8 p+ j4 w6 [9 C/ t
int p,cur,pre;
& w/ x5 U; g/ y //MultiAdjListNetworkArc<WeightType> *p,*q;
  w% F. x6 @7 i# S for(int i=0; i<vexNum; i++) tag=0;//初始化; I+ O4 B* K0 Y! E2 O' P
3 T% B/ w% y( b+ L& @" Q
for(int i=0; i<vexNum; i++)
: S! ^4 T9 I) w7 B+ |. b {
2 }1 t9 i0 m( Z       cur=i;pre=-1;3 ~7 V* S5 @* Y6 U/ N0 L; K
      while(tag[cur]==0||!s.empty())
6 @" j' V. ^9 u6 i" V       {
         while(tag[cur]==0)/ B/ W$ V* ~, b6 a( T: V
         {
! h+ {" L% w: L; ~3 ]7 @             cout<<vexTable[cur].data<<"  ";
" h0 o: o9 n9 e! F" F             s.push(cur);! r6 {( r& ?! K; N, w
            tag[cur]=1;
* p. |, e) R- f/ p7 c! r2 o9 M( D  b             //初次访问，标记入栈. t6 x- [0 A1 `- w2 {" Z- X  M

1 N% Z* G7 w# d' \/ V             p=GetAdjVex(cur,pre);//p是cur的连通顶点. Q; E& W* x& N
            if(p==-1)
0 W4 G! B2 U" }! Y& ]) W             {' ?# m0 b) W* o4 B$ `) m1 h
               pre=cur;s.pop();: v( n$ y, E* Z/ [" }4 z. `/ Z( W1 R* i
               break;
# A) y0 p9 H. s- ^, Z( S             }
" k0 L2 a! Q5 z. @9 i  L- A+ M             else' {& j( o0 k" Y8 T) `
            {
0 S7 [8 d2 S! H9 n) c* t8 f0 p+ ^                pre=cur;
8 R8 k- f: Q6 {* J% |                cur=p;' n9 U- z$ W% D1 K! f& W) g* Y
            }
1 u: j+ o, x/ f( P$ R& |/ A" t+ g! M1 T
         }% J* ~1 s5 C! G$ q& q4 ^0 n
         while(!s.empty())
; Y! O+ K6 l1 I; j          {
6 P  |6 V$ I+ D             cur=s.top();
3 f: D# g; O# }. U4 O             p=GetAdjVex(cur,pre);
7 c( U6 z. R- H0 {$ v! t: @             if(tag[p]==0)
& {) Z, z8 T# R6 l4 |7 \             {* |3 I6 K- @2 W, ~3 X( b) S
                  pre=cur;
! k+ _: a6 `: R/ J- m* R2 k  k3 u: t                   cur=p;
( Q& J1 N9 O0 {3 }* C                   break;) A4 d' p' m: m: M7 o" _
            }
3 @3 T' K$ _# x             else+ v; B$ a  d6 {6 y% w0 N
            {6 m; h6 T7 N$ C. y& \
                  pre=s.top();
; t' x( n  d: R( z) d4 h- ~7 ^                   s.pop();( k/ }+ }8 }% L# Z5 w: g' U
            }
9 r/ B& Y# Y4 \, G- F: Y
, t1 X$ _  m+ K; ~* [0 k! N0 N          }
+ B2 `1 l; m4 R8 s& ~( S2 J
+ k3 ]% Y* G$ ]- c: ]1 J       }
( e3 g- G6 Z0 Z, b }& Q" f9 C/ W# r' _
}  ?! l. e) {/ G* |
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
! J4 W  T& P9 X# ^0 T( C; g* \* k{+ u# U! q1 n( a+ H" F
for(int i=0; i<vexNum; i++)
/ y1 O  X6 B7 V1 o. _       tag=0;
3 `4 G! J# d8 M queue<int> q;
+ @7 k4 ]  k; S( G% J int tmp,t;
& j6 z- h/ z9 R0 r$ X9 J MultiAdjListNetworkArc<WeightType> *p;# }: v% Y6 }2 l
for(int i=0; i<vexNum; i++)
& l6 @' B7 R5 I% o$ z. b! m1 e {
  [/ b5 {% S& z4 U* v       if(tag==0)' P9 p# S7 z% K4 W" L( N8 _1 N# d
      {
! r& [0 [* U. |  @6 Q  |          tag=1;
: ?6 t0 e9 |; {  q' l2 P$ L6 d          q.push(i);
( Z6 A* w. J; G/ }          cout<<setw(3)<<vexTable.data;
! h2 \* r: u/ `- R5 U5 [2 h       }% Z$ `$ P" i( b0 J8 y, q- ~3 Y
      while(!q.empty())0 w5 c% e' {; {& X8 f" f
      {4 i$ e8 o/ b2 w$ p$ m# q
         tmp=q.front();
/ m' _8 c& O  C& [          q.pop();
( S* U; q2 Q1 i$ f5 Z          p=vexTable[tmp].firstarc;+ i! ~3 v- |, F1 y2 a% ~/ N# R! P
         while(p!=NULL)8 |* k% F" B0 p$ O8 O
         {1 V3 D0 {/ r4 g
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);% s/ S; [0 K2 h1 E8 {3 w1 c1 O
            if(tag[t]==0)& s8 ~# B1 h6 d6 R2 O4 z- F0 H
            {
% L' ]9 s# f5 i( I6 P                   cout<<setw(3)<<vexTable[t].data;$ w) t1 }; O7 y( W2 d7 V
                  tag[t]=1;
* v$ F& U& S8 x" o) z* m7 w                   q.push(t);
9 _+ C( A' ^* X: p6 G             }
9 M9 B- m: _, U: o, I& F6 d+ Z             p=NextArc(tmp,p);
, b9 @- X' x' \3 ]' i          }
! `) F% V" g4 Y7 R, G6 \       }
8 |" e% j% v' k- Q }2 Z, y$ `- f! @* @/ Q
}# ]  V) N# F( b
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()" e" V# c. n6 ?2 b5 ?' R
{
8 z6 ^5 `5 F5 C, N0 j0 D1 ^  q MultiAdjListNetworkArc<WeightType> *p;
5 k. }9 j/ ?) c: I cout << "无向图有" << vexNum << "个点，分别为:";
4 [: u/ t% F$ G for (int i = 0; i < vexNum; i++)- z) ?7 e$ u! X
      cout << vexTable.data << " ";
0 t; c4 i; Y; U% r& Z; j& H, o cout << endl;
7 n, L, L& p+ B cout << "无向图有" << arcNum << "条边"<<endl;1 G" q/ v/ H# r: [5 q" v
for (int i = 0; i < vexNum; i++), I2 }. r) d7 \9 d" m0 \  ?
{. j/ v5 K. t& v/ e) g
      cout<<"和" << vexTable.data << "有关的边:";
3 q: d6 ~, F+ u3 k1 E! x$ {       p = vexTable.firstarc;
$ M) B  N3 ]$ Q8 c       while (p != NULL)
3 V' F& }0 j# V: ~+ F       {
+ V, c; a* s4 L. B$ x( A/ A( h          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";) A- B6 W# p- ^- n& O' ~
         p=NextArc(i,p);- W8 T1 k. e$ V
      }* R' V2 |: l' a/ h
      cout << endl;/ j4 E3 |0 w+ L$ g- H
}& ]! r' @* X- t- _) j( b
}
$ X3 r4 P" @6 m5 P3 ^6 D, a& K* z5 o0 I# P$ E
6 c& I4 k% F9 R6 D7 ]$ w; ?
邻接多重表与邻接表的对比, @5 f) I/ T4 d

' z: N( ?/ G% E. i, Y邻接表链接
: W( J7 X( G8 G; l0 G0 d: {在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
0 ?1 [8 N9 p9 j* V6 t% h: q7 t8 h, o在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。& e- g0 @9 I1 d, L7 r9 S
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
9 J, R) p# a- C1 S————————————————, }' U7 p3 r* r# ~
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- H+ v! n6 L3 x, t% A+ M原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
) c* T4 z$ B0 h  T1 g6 t( H: D- ?% X8 N" q# U0 {* _

! m* }( O1 Q3 J" @
1 C4 Z" U' U' h' Q! G& f4 k% y4 V  d5 N5 J& S+ D
————————————————
  w' R! a3 P( J, K# w* ~版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: e8 Y# n; j, {- {' _2 I) m原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958; H8 A! ~2 |% j; q
1 N5 R9 J4 _- Q; R% J; [; O
8 k- d  ?; B, c' Y

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