数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
2 |: d/ r8 ~/ v& X* qdata域存储有关顶点的信息；
/ a$ b! e" {9 L( p" D. ^firstarc域是链接指针，指向第一条依附于该顶点的边。& r$ i( b a z* I( o: [8 _% r
所有的顶点结点组成一个顺序表。

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;% B1 b! ?2 B" s- ~/ W
for(int v=0; v<vexNum; v++)
5 y3 R7 w  N. B. H% k8 v6 {) ~ {2 T/ S6 `3 N% U
      if(tag[v]==0)
! y' x# D  x% [2 b          DFS1(v);
; w: A1 n1 l* X9 d! o }
' `1 k/ a9 M# _5 c}
5 ^4 j2 r* h$ g! R6 {! ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2(); ~) P6 N# j" T, U: j  x0 e! S
{  l2 c7 f# @, R. @2 \8 v, m
stack<int> s;
) H5 @  e' ^' C  l int tmp;
, w" f# Z4 X& j3 W; c, [# V MultiAdjListNetworkArc<WeightType> *p,*q;1 C! e0 r$ l# U. }, n5 e
for(int i=0; i<vexNum; i++)
/ }7 i- J1 u$ d8 B       tag=0;, m* Q  s! {/ w; F! i8 R
for(int i=0; i<vexNum; i++)% D' a7 x' l- b  F7 E3 _5 w0 b* J
{
! A9 R! x5 y+ b8 K       tmp=i;
9 k- H' P  B$ a       while(tag[tmp]==0||!s.empty())( P. i7 x* W% n( }' {9 X% q) \
      {
8 g/ ?8 c9 e" t! s3 N& _* k          p=vexTable[tmp].firstarc;1 w' {' q4 g& m7 `) J) L7 d
         while(tag[tmp]==0)8 P1 _1 J# ^! Y
         {
7 O" S5 o3 c+ D$ Q9 c6 l) g& b             s.push(tmp);
( v/ s* u5 q' G2 p$ l$ `/ I) \             cout<<setw(3)<<vexTable[tmp].data;# y0 w7 c% l5 m2 \+ @# z0 z
            tag[tmp]=1;2 W, Z( _! v- u9 @
            p=vexTable[tmp].firstarc;
' {" S, k6 c: e             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
8 y, O$ o; c1 T2 e) q+ n             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
$ t& w/ H: H  b5 s5 z9 k             //cout<<" 1st    tmp="<<tmp<<endl;
5 l2 P7 p0 ]: z7 c" s          }
6 S( Y. X; T5 t% `: m$ g* m          if(!s.empty())
( N* m, S! t6 H5 O/ v# w7 }2 \          {
6 K; H5 R$ a8 E) _& z# o, t+ T1 f, m3 \             tmp=s.top();) f) ~3 ^  l' h( z
            s.pop();2 I' {4 z- Q, [" J5 b1 H
            q=vexTable[tmp].firstarc;
, {% r* v( D; [$ T6 v             int t=tmp;; J4 p* _, G5 ^3 _; M+ |
            while(q&&tag[tmp]!=0), |7 C. _3 ?1 L+ ?
            {
1 u' S& L4 Z+ u* F                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);0 m& [+ t# `/ j- {( |
                  //cout<<" 2nd    tmp="<<tmp<<endl;
* ^' V4 d  L- R/ N                   q=NextArc(t,q);5 i' }8 l* U: }/ @  O" m% t: f
            }
5 K! k2 K) Q$ h- t# P* g             if(tag[tmp]==0)
) @( ^# n% U5 ^2 q                   s.push(t);2 S1 u$ u2 S$ x  ^$ A$ j
            ///1、对应上面连通分支只有1个点的情况
) v, }& K* ^6 R& H1 s/ q3 ]  j             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
6 r) i# o) q  F; D. Z             ///tmp要么等于找到的第一个未访问节点，- _2 D7 n5 z6 K; s3 W
            ///要么等于与t相连最后一个点（已被访问过）1 p, {/ p$ A* g
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
1 g% I# y+ m* `* d" A# a( {8 g          }
9 G# J& ]4 ]$ O0 B1 G0 r* e       }! z4 {. l+ k! N; w0 J
}$ e! b8 i1 @0 X+ e6 I7 R. R; x
}9 }7 b& v0 s" L3 s4 {' D
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-17 I. F# S; \, J, @' f/ t/ a( W5 H: t$ ?
template<class ElemType, class WeightType> int1 `8 W# {" @, n2 S7 K
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
: k# `' v; o: ]{
, N) o6 T8 x: x8 N2 j6 ^' j if(head==pre)
' U. w1 `; g; B* P) c. K       return -1;
' }  F: x; l0 l& f& V/ ]; ?4 g/ R- D( C/ ^
MultiAdjListNetworkArc<WeightType> *p;  l0 u/ ~4 H$ O( f
p=vexTable[head].firstarc;
, s* Q' \$ F! F. u6 Q if(pre==-1&&p!=NULL)
+ [  z/ D# e3 j# B8 L  h       return p->adjVex1==head?p->adjVex2:p->adjVex1;3 G/ x: {7 ?7 F! j9 e. Y
//pre!=-1&&p!=NULL
# T) P. J' O0 }, k* W5 b while(p!=NULL)
) B3 D8 G+ k7 R! M {2 C1 `) j; ~: M. V, O+ O
      if(p->adjVex1==head && p->adjVex2!=pre)4 b0 O& ~3 `, m1 y: p+ Z
         p=p->nextarc1;
$ f' k: J4 g3 I8 V. W0 G       else if(p->adjVex2==head && p->adjVex1!=pre)4 Z- Q1 v- J6 _
         p=p->nextarc2;! N4 N5 [  M3 X$ R# r1 I
      else if(p->adjVex1==head && p->adjVex2==pre)
5 d: X! s7 U! d5 c% [, s       {
+ h4 s% t: w9 x4 C2 r5 h          p=p->nextarc1;
- s1 K" {& J" t( e          break;
: Z9 v* T4 e- w; E" i- a+ _       }
0 L4 w, E: M! Y6 C' U       else if(p->adjVex2==head && p->adjVex1==pre)  h5 R! W* E  y
      {
$ m6 e! \6 `# E  Z$ C# y+ w          p=p->nextarc2;, S: F4 {7 W7 a! a
         break;
, j7 n/ X, w* B7 i! U* R/ F       }/ H" o* y+ t$ v4 r9 }$ G$ H
}, o7 B4 e* h2 W
if(p!=NULL)
- S' J& U1 g8 E9 C {
, x2 h9 N% u6 o1 n+ C       return p->adjVex1==head?p->adjVex2:p->adjVex1;
! i2 Y( U! o+ Z5 [7 _" p, O }
: G/ ]2 a# h( L% f else9 g' f) \/ b  K* {- N
      return -1;
0 M5 L( A, N5 `, F9 g}+ w) L5 l8 v7 O' c$ F- ~

% W4 S6 s7 s3 z
# L, b$ s/ F# ~4 _template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
, Y3 H  G7 t7 u5 @; I/ v; Z( j3 Q6 b{  K" O' ^- S7 y% U  v
stack<int> s;: n+ t' g) b7 P4 @4 o* ~8 @9 W. E
int p,cur,pre;
# s; y7 {+ C& Q0 h; J$ s //MultiAdjListNetworkArc<WeightType> *p,*q;
4 W; O! v3 h  Y8 o for(int i=0; i<vexNum; i++) tag=0;//初始化
( o9 U$ L9 d# N1 H9 u; [
3 ^% C0 Q: o2 c8 e for(int i=0; i<vexNum; i++)
% p; x( S( Q- b {
7 Z* v) c  V& A! Y       cur=i;pre=-1;" G, s8 ?, F6 H2 C5 E1 N4 G* }
      while(tag[cur]==0||!s.empty())  S! H2 i4 n" w% [% }! c
      {8 ?, N$ }# Q# M9 d  A& h5 ~
         while(tag[cur]==0)
; A; @! m; V/ R1 l6 r          {
4 |. M2 |, F& q  F             cout<<vexTable[cur].data<<"  ";
& k8 G6 m( T2 a; b5 j4 _             s.push(cur);0 {3 t9 w9 g, a; o
            tag[cur]=1;& U! v8 v! O6 M! J
            //初次访问，标记入栈6 k2 k( Q% q( u- |
2 u7 x+ q0 R$ ?, t
            p=GetAdjVex(cur,pre);//p是cur的连通顶点( R7 T: q" d# e
            if(p==-1)
% L; n  }' I- I. x/ {             {
# `2 m% t$ p2 C6 Z, t, \                pre=cur;s.pop();
9 R+ e( X4 J0 Z6 [                break;- g* O+ x! [4 _7 K
            }
$ {' p# [# X3 I             else2 r' s& {# \- \" u7 A" G7 V
            {/ \! z: N* G' n2 B/ [
               pre=cur;/ V7 u+ g, Z+ [* t
               cur=p;9 e! ]) L: M' S
            }
, b. s4 a$ ]$ p/ G& Q9 ]2 ^2 }1 z  ^/ r" o9 y5 p8 R
         }
) `1 t; i1 I# d. O1 h8 d6 L0 J          while(!s.empty())) i, H* K7 ~, b6 v+ p6 `
         {
9 p- n) a+ P. M7 w0 V/ ^             cur=s.top();
; G8 P& @! S8 I; g5 C  _             p=GetAdjVex(cur,pre);3 |9 M: `3 K: q' I; i+ i
            if(tag[p]==0)! [+ b( b$ Q* Q0 s" s$ ^1 B8 z: D
            {
- e$ h. u: N  u  N; U                   pre=cur;- W- Q- t: i; w" P4 y/ @% `6 n0 Q
                  cur=p;8 a8 k! S. ?. C: u4 E  X9 W9 m
                  break;
* {- w$ K) J  _# y& t4 |" ^             }
8 J& q$ Y! y+ N! o  X+ `             else! J$ M" z3 i% U
            {
9 Z% t+ n/ @' W0 t3 v6 H% _                   pre=s.top();
1 i& \. \- M) v. W  L                   s.pop();& F% k( Q* ~! T% l! h
            }
' W/ o& z2 B+ @, g$ n+ b! P$ J8 Y0 X  [* T
         }0 ~) v8 `/ u0 T* _$ w, I# U$ `
  \7 ^6 \, i9 }, z3 s
      }" U. f& @1 m7 V6 r  S. F- B9 Z
}
$ B4 X$ m+ y* k8 A) `$ M}+ u% B* C( j) }0 K; B. O5 y  u# u) c  |
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
. r. U8 }% v; |2 _0 M{
) M: A" \. o$ w2 F- v% k# N/ K for(int i=0; i<vexNum; i++)
1 `- W. O, e# Z/ J$ K+ l       tag=0;
& H4 I4 \& U( z9 H5 e queue<int> q;
, i% O9 |& [" s4 ~ int tmp,t;
8 t! f/ c- X/ Y& R1 r MultiAdjListNetworkArc<WeightType> *p;3 u( x# }! ~: J2 `4 J9 z
for(int i=0; i<vexNum; i++)
2 O+ M- ^5 n. I3 `& Z2 ? {0 b/ Y/ A4 r7 ]/ W  _5 g9 l* K
      if(tag==0)1 E* b5 Z5 {3 G1 [0 ]9 M
      {
( q" r; h5 {9 U* c6 q" d          tag=1;
, ?, ?2 A+ h; p! J          q.push(i);
# N) o0 j# z( B+ ~8 J          cout<<setw(3)<<vexTable.data;
7 X2 B6 V7 m/ v7 ~9 N0 o       }0 A# W; ]4 f/ u# d
      while(!q.empty())
& U- H( ?$ a2 j- `+ X; z6 }9 w) c       {- k4 Q5 n; K' ]9 d2 S  L( Y
         tmp=q.front();1 r& @: J& x: c* E2 L
         q.pop();/ j% u+ e" e" S2 d& Y5 M. O
         p=vexTable[tmp].firstarc;
4 g( [$ g2 f+ h3 k3 K+ `9 k          while(p!=NULL)
9 ^' j* Q# s: p+ O' T; ?          {& j; b/ x( m/ C: r  F
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
5 Z1 R/ K% S+ e. u             if(tag[t]==0)
& N9 }) i! M/ B  s             {
' m" k, }/ H. k* `  T% Q4 o( d                   cout<<setw(3)<<vexTable[t].data;. v+ d5 a* I" p& Z  j+ p- g
                  tag[t]=1;
  B2 N4 K! i$ g- T" X                   q.push(t);. k  y: Z1 w0 K6 ]7 W
            }
7 e7 b5 i% L3 l+ C; v( m0 J. m             p=NextArc(tmp,p);+ c% M2 |7 [5 c8 o- B' t* |
         }
3 N; r0 K$ q: n( O7 T       }  \/ t0 m4 L# G( z8 C. c( g& d# \
}  G% d, P1 E) j4 R8 \
}
2 j2 L! W( e* R" R' Ztemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()1 h0 O& H( R  B9 O& T
{% D4 k. `. H' C- u( e9 t2 p
MultiAdjListNetworkArc<WeightType> *p;3 B6 t. ?) L$ Q, I
cout << "无向图有" << vexNum << "个点，分别为:";
/ D0 G; T. b6 d4 L for (int i = 0; i < vexNum; i++)
- l* t- X& j! \6 T9 R       cout << vexTable.data << " ";: S7 J+ O4 z; j' X
cout << endl;% l2 V+ T' c  H3 L6 k  s* z
cout << "无向图有" << arcNum << "条边"<<endl;
5 L, v# u4 W, R. i/ y' C for (int i = 0; i < vexNum; i++)
* w8 Y, K- G% @) H {
4 ^1 f) S3 H; F5 [0 U5 u; y       cout<<"和" << vexTable.data << "有关的边:";
7 `6 j5 K6 Z2 ^3 |+ [. o3 j' z       p = vexTable.firstarc;
+ b) }- R* K% |& z! m       while (p != NULL)# j7 ]* s* i' z/ `
      {5 T- l7 m- F8 \" @  N' f- a
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
* r2 u& i( ?+ ]; E8 B/ L: `          p=NextArc(i,p);
% d: A, z/ h" i! r# Z* m       }9 {  S: F/ @" ?+ O; r- {7 K
      cout << endl;
6 ~* V3 N( x( N  o }& |0 M2 Y3 [* ^  K- m3 q
}& S+ E3 D8 b1 b1 K7 |" x5 a
, h8 t. I( l: E/ v3 Q

0 n0 |8 e! h( t( ~) Z邻接多重表与邻接表的对比
( b4 t9 G9 b6 G% w9 _$ O) b. l0 h
7 p1 q+ q! Q& Z: V邻接表链接
, f) J" Y4 d0 k# b& O% x  w1 q) T在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
% i% |7 c$ L. \* M. I7 |& n在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
: g; f& ?5 Q% K8 G8 G; b9 i为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。) V/ e7 g" v9 G
————————————————
7 b+ Z# z2 V( r6 n' r版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  k$ s9 w5 [. M& S原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958* O( Z* ^& R0 ~6 h# a$ I. M8 S
# b0 I! ]. k+ g7 I& d8 M8 ^

' v& ^: r( J2 s5 \) X( E4 l* ^  u& a
0 G& \3 e* c" v' r6 s2 ^
————————————————5 M3 z1 h! k5 b6 _) b, p+ X
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 e0 g/ p' A2 y* i( {& q原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
8 ^1 J; D! ~: K* @+ ~' v8 g2 U2 [4 ~! ?3 K; L3 L, w5 B$ H
0 Z3 X  S, S6 P- i

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