数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：" K0 r' K' _- ^
data域存储有关顶点的信息；
1 r$ E# G3 O- `2 n: f/ Zfirstarc域是链接指针，指向第一条依附于该顶点的边。+ a5 t6 v2 Q- h/ f$ l6 y3 b
所有的顶点结点组成一个顺序表。

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;6 w' B: H: |, N) G& b; z, c/ a6 Z8 Y
for(int v=0; v<vexNum; v++)
8 l# O% [/ J" ^9 p: d7 d: G7 O6 K {3 U# ^9 ?4 {3 t4 Y) p9 K5 b% y
      if(tag[v]==0)
/ j2 c/ a3 c. `: ]          DFS1(v);
2 u9 M% I' R$ E }
$ |6 j- k3 F5 D1 ]4 E}
9 \& }! @2 K( |7 _, etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
' X7 D! c3 w- ~. g1 r0 U* H5 ?" J{. N0 W* O" j$ b8 W5 w: r$ z
stack<int> s;4 o: M' X5 V! ]8 t1 t; S) E
int tmp;; y1 L1 E, }- B
MultiAdjListNetworkArc<WeightType> *p,*q;# c$ z" _) \: M: [+ E! t
for(int i=0; i<vexNum; i++)
8 ]1 e) o% {  Z8 j       tag=0;) X% [& m8 Q, i0 ~9 N; J
for(int i=0; i<vexNum; i++)
2 E$ T: q. R, \" w# i$ i {
. ?# X5 @* a1 J1 t4 Y       tmp=i;2 _# o; Y$ @$ a
      while(tag[tmp]==0||!s.empty()): m. Z  }) R/ }1 [3 X7 l5 A( s
      {
9 k& T: f' s1 b6 j          p=vexTable[tmp].firstarc;
5 a" |7 V7 W: @% R) v& q          while(tag[tmp]==0)6 D% B0 F* Y" D/ S/ ^7 ^: l
         {
7 M9 X4 J0 ^7 w# g# S& {; v7 h( h) i             s.push(tmp);' \: C0 Q& ?' D
            cout<<setw(3)<<vexTable[tmp].data;
+ _* ]9 G3 e2 e' r. E( r             tag[tmp]=1;8 C9 d# A2 f/ _
            p=vexTable[tmp].firstarc;
. b/ ~0 B, e) N, {6 _) d3 H4 B( x2 j             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
5 a. X5 C7 o  Y) j7 i             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
1 U7 C7 n: s, F8 ~; q( Q4 H             //cout<<" 1st    tmp="<<tmp<<endl;) d; B6 S, t6 r8 X/ L. s3 Z
         }
- X1 S4 i2 }7 M4 R+ J          if(!s.empty())8 X$ H# `; ?$ m9 X8 Q# N
         {
1 Y- J) U+ p( L' J$ d3 {             tmp=s.top();
; ~" H# X: i/ }$ `# ~             s.pop();8 ^  e- D. J5 k* x" i0 k5 _
            q=vexTable[tmp].firstarc;2 D% S- k+ L3 y: Y0 O* _4 d
            int t=tmp;" g2 g* m( t) j! e  u
            while(q&&tag[tmp]!=0)
/ @4 j8 `2 `  {4 f6 ~* d' y4 k3 p             {( T5 w* f, ^; I  L6 |. g( K
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);3 s1 Z/ X% i& A4 S$ w
                  //cout<<" 2nd    tmp="<<tmp<<endl;
. ^- j/ k* _8 ?8 w5 _) X  k/ P                   q=NextArc(t,q);% C! V: z4 u9 o4 o6 s
            }
% r3 a$ }. j/ X% n; n! Q             if(tag[tmp]==0)3 L0 g- s8 }+ ?2 `8 ~
                  s.push(t);
* M# N* N! e5 O             ///1、对应上面连通分支只有1个点的情况; i; N( Y! j$ Z' G
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
! h+ `1 h, v0 y7 ]) i* W+ h             ///tmp要么等于找到的第一个未访问节点，
; e; ^* a( C' H7 U. j+ g& @# _: x. Q             ///要么等于与t相连最后一个点（已被访问过）
. ^  C: P. |: E) h* B* H- x9 B             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
- q# I3 C) x% F9 [5 E          }
* t& z& Q( N% n* ]8 x       }
$ a0 F6 l, @! E) Y! n% d3 {" z }
$ v/ |& R6 T/ A) l  D}
6 Q; g" c1 T  e//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
2 |+ s; [( q% o( M) ktemplate<class ElemType, class WeightType> int+ A1 A, k- J4 l' `& t
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
* G; i( Q) \9 b  ^& o. \0 n; u{% k1 {8 ?1 R- P/ m. v
if(head==pre)
8 H& V, L' m; {& F% w       return -1;
$ X# T/ p4 h# M" q; `
/ i5 |0 {) c6 t* [' u MultiAdjListNetworkArc<WeightType> *p;
& E4 T" _" }# j p=vexTable[head].firstarc;
* Y5 \  P" ~$ r- D: x7 } if(pre==-1&&p!=NULL)
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
, B' Q/ ?6 F/ p  @ //pre!=-1&&p!=NULL4 c' b9 a1 m5 q) [
while(p!=NULL)
# Q7 U$ j: D1 Y! b* Q8 } {
( N2 j) K; h) Z# o       if(p->adjVex1==head && p->adjVex2!=pre). P; M' a( N. o1 ?, m
         p=p->nextarc1;" q5 o# B- C$ y* `/ c. J: M
      else if(p->adjVex2==head && p->adjVex1!=pre)& i/ \0 c1 y2 J" X4 `
         p=p->nextarc2;
; D5 G) R+ W& H1 K* Q0 R       else if(p->adjVex1==head && p->adjVex2==pre)6 f, j, ]  H3 B
      {
$ L' Z1 P1 l6 P/ g5 R/ y' Y$ s          p=p->nextarc1;
; u  Q9 T0 f' E6 b          break;9 j( M% p3 R$ b0 k) t
      }) U* ?; v: [5 c; S, W6 }
      else if(p->adjVex2==head && p->adjVex1==pre). `$ A+ p0 p+ c- j8 \; N: ?% r5 W/ S
      {6 t! m: n8 ^) Z' Z
         p=p->nextarc2;
, }8 S# T* l5 w; b: U4 z& t: q' F          break;$ h9 h5 N) B6 N5 h
      }
5 w1 ]) s/ \! Z  n4 v }, E( g! F1 T4 o: b7 ]4 g# @
if(p!=NULL)* S: i: {* P( l' H2 B6 }. Y5 S
{
* u4 p7 Y1 _4 B" T       return p->adjVex1==head?p->adjVex2:p->adjVex1;
, k9 U- l* x; U& G }
" X7 p& d9 [2 e# Z' m- H7 V else0 M+ O5 Z2 P+ \
      return -1;
3 R0 [& |6 _7 m3 a, H7 \}
/ r6 _, D6 J$ \: R. |
1 C# r/ Y, Q/ v  o$ L; ~/ Y* K$ B! ?: c7 R$ Q2 t! |2 c
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
, l& l% [4 x+ ~4 f{
. I: E, E3 e  i* Z stack<int> s;+ R: P* _+ Z6 e; T
int p,cur,pre;
  o  i6 V  J3 Q( C //MultiAdjListNetworkArc<WeightType> *p,*q;+ C( d0 |/ s5 |) m! y  w
for(int i=0; i<vexNum; i++) tag=0;//初始化
& g& V1 K3 X1 G! ]' e* q' U6 v9 O( v, w( m5 J+ h3 C- t
for(int i=0; i<vexNum; i++)3 C1 A) `$ R3 z- U' K; i
{5 a* S! T9 K5 u: g2 B8 Y
      cur=i;pre=-1;0 y1 d, a, R9 E0 g
      while(tag[cur]==0||!s.empty())
2 P/ v- ?' K! u2 M& \8 N       {5 x% U, ^3 T& p4 L7 I' X
         while(tag[cur]==0)) A9 N2 N2 T1 F% B7 y' f
         {
9 h3 {6 B. |4 l  s) W$ q; {             cout<<vexTable[cur].data<<"  ";
# \( S1 S6 u+ N, }             s.push(cur);) B8 ^4 o' [$ z5 V# b
            tag[cur]=1;& k4 L6 C# E& ^, q: u1 \$ y$ s
            //初次访问，标记入栈! D0 q( b2 M* g  |8 N
( P% d! M* l5 l  w4 L- I/ ^! e
            p=GetAdjVex(cur,pre);//p是cur的连通顶点8 O3 d9 I) b+ ~
            if(p==-1)
; h/ S8 }% f; n9 P             {( c" S  }7 g0 a$ `' \
               pre=cur;s.pop();
7 j5 P+ t) D% h8 D  Y                break;
, E' b+ l( m2 X" Q( `- ?             }
" N" E" t: }( w% _$ `             else) W* C7 S, ?: C! [1 W* R
            {
  \* i& J. s) P: u0 ?5 y+ y                pre=cur;, B% ]; b; o; ]1 Y6 o! N1 T: ]
               cur=p;
; l4 b/ Q' g+ L: `2 l. i             }& c5 B8 ^  b; G2 C

9 j! n* _: V+ u8 a' o+ T7 h0 F          }
9 J7 D- \4 h0 ?! I0 e          while(!s.empty())
8 U1 C5 }2 J& I: E- @6 [" m% C7 v  F          {0 r' q& r8 ^; D1 M$ z% r; ^
            cur=s.top();$ o9 v% b" S- u. L, v0 Q/ Q
            p=GetAdjVex(cur,pre);; ?5 W7 S2 e# i; @# |8 \& ^5 \
            if(tag[p]==0)) |7 H) `) j" A9 F0 O1 n
            {  s' _1 U# w, g6 o
                  pre=cur;
/ a! `, U- U' ^; w3 Y) |( x2 q                   cur=p;
$ b+ k! |$ @# ]$ A% f                   break;
* ~# d# {0 l: e             }3 _+ I  B/ B7 ?' p" m' r" p
            else7 X8 {6 `5 q. |$ B/ k9 }
            {
' R+ a, v7 H9 ~# P                   pre=s.top();
- S5 |$ O# K$ P1 {                   s.pop();  Q, x! ~0 P/ D4 S
            }
5 _0 K8 M+ a) \: \5 B4 G% J! n2 d# c) }8 R
         }5 U# ]" [# {6 ~& G

8 E. D1 U( ?- ~1 M0 p- d       }
& v$ b4 @% A/ ]4 C) V& x }
* \& G% [1 z0 l% U}
6 @4 h! @: m. E( G  K4 Mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
# j, p* C; k8 A( S2 f{5 A1 ?; U5 s' K1 k: t
for(int i=0; i<vexNum; i++)
1 ?1 {3 c! ~% V2 G9 a/ o: u       tag=0;" ]4 l# h( {4 ~! J. i  A$ x4 J
queue<int> q;
/ d3 Y( v/ Y$ E' E2 Q int tmp,t;
9 B  q: s  p! p, d" a+ U2 N/ N MultiAdjListNetworkArc<WeightType> *p;
. a9 G! n! X3 Y for(int i=0; i<vexNum; i++): X. x' d2 l$ E1 a. Z# E# m% {
{
+ A& ?5 I  k; X2 x       if(tag==0)
' m  Y% b5 H5 J5 B/ T       {4 M) S! e) |3 j$ ^4 G7 I
         tag=1;7 ^3 b) @* H1 l8 O5 k
         q.push(i);3 @* S' s. K& X1 z
         cout<<setw(3)<<vexTable.data;
' g/ _0 H3 |) m/ i1 [+ t       }  `% a# e' q$ o1 {+ s6 k7 H3 t. h
      while(!q.empty())
* Y9 t: c# M7 R+ c       {
% O& Y! h3 T8 K: X. o6 R- h          tmp=q.front();
! q5 Y/ z. `7 m3 w8 m          q.pop();! X* ~# l4 X# F: t* x/ f9 e  b
         p=vexTable[tmp].firstarc;) f3 v% h' F& D$ `# F# g
         while(p!=NULL)
: K& S; E. o7 ~1 U/ ]3 W/ G4 x8 R          {
6 B/ N" Z" f9 E8 H$ k9 V             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);9 I& l$ @7 U  v* {
            if(tag[t]==0)2 l: W7 G4 S# {- r/ [
            {
1 F2 a: ^) N7 O* l                   cout<<setw(3)<<vexTable[t].data;$ \- [( R& o# S. T7 @6 F2 a7 J
                  tag[t]=1;
9 S4 |3 }3 r& _7 J/ [/ G                   q.push(t);
& P5 |# q4 W1 G" p             }
; G& X0 ]$ W: G5 ]' y             p=NextArc(tmp,p);
& n! I/ e  Q/ \7 L$ K/ w$ h$ [          }
0 z4 X# V# p/ R' u       }/ T2 X) i/ H: z, f2 y
}
7 B) S' s' S& u: [1 @/ z6 h5 J}, Z* ~- O& V5 W1 H$ H2 [& Q& o
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
* B7 e. r! s, Q; m; ?$ C  \{' v& ]0 o- f. \8 A3 I
MultiAdjListNetworkArc<WeightType> *p;
. z4 c0 f# C1 R7 @6 S cout << "无向图有" << vexNum << "个点，分别为:";
1 {' z+ K. B% ]. E  R, j- P, ]! r for (int i = 0; i < vexNum; i++): O2 g9 {) k. I0 \9 l
      cout << vexTable.data << " ";% Y+ e# ~5 g; p9 F9 r
cout << endl;3 e0 y: d2 j9 e2 R6 I5 ?( }) C
cout << "无向图有" << arcNum << "条边"<<endl;; o) s. l$ [7 Q$ _. S
for (int i = 0; i < vexNum; i++)$ l( X% Y; }5 k( {+ M7 @) J
{
' O8 J% J$ A: f       cout<<"和" << vexTable.data << "有关的边:";
; }2 D. G, r+ M) h       p = vexTable.firstarc;
1 Z: Q, U/ P1 C  U       while (p != NULL)$ T2 b+ g3 y- E' L
      {. p0 C1 d0 R7 z) }; T8 G
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
$ @7 L+ V7 k2 F/ b# ]( I  ]) M          p=NextArc(i,p);
3 I. m, K8 _# ^& H/ I0 P       }: v  |$ j4 c& K) }
      cout << endl;( `5 N( m* Y8 z: N) d4 T) F; C( @
}* f1 O% k2 P7 p; f/ G' U: l
}. c, e0 W/ c# L! L; a+ o5 b

' R" E1 Z" j4 F, Y+ _4 _8 R$ S% C+ O. m- k! Q+ j
邻接多重表与邻接表的对比1 }: Z* X! D, @6 V. ~$ A2 v
! [6 ^: I( T3 A
邻接表链接
6 J" S% y# L4 E& P/ x, n( g在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。; F* v* h& G) ]8 R
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
; S; |1 U9 `  V/ \. k$ I* b为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
' D- h1 ?9 E7 B- A0 u* q8 L- A2 P! E————————————————  L) A. T, O2 ?2 x1 }
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。1 q3 P( M9 O  e
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958( y& W2 s- m) F% A8 p' z5 C

! \1 m9 u5 d6 p& T# o8 f, x
; l& c0 ?- z; X9 g7 R: T8 h- _6 S: L3 _5 N. ^$ n

0 a. a) F" d8 W7 e2 R( Z. O————————————————
' W0 N! h/ p/ m& B* Q) k7 c版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。0 `' j0 X5 @" z5 G) N( Z8 A, \
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958) U' U$ H2 r6 e  h: x

# ?% y' f" @7 [9 c
$ a# o3 f8 L. Q' n5 S- M

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