查看: 1695|回复: 0

图的存储结构——邻接多重表（多重邻接表）的实现

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-4-26 15:26 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
- n: p3 e5 g* Z" ydata域存储有关顶点的信息；
/ C* d/ P% B# R2 S8 A* Q1 Gfirstarc域是链接指针，指向第一条依附于该顶点的边。
+ O4 ?9 Q' P8 G- E# Z1 W3 Z所有的顶点结点组成一个顺序表。

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;
5 B& V  U, W/ M3 W8 m  o) V for(int v=0; v<vexNum; v++)" m/ C0 ~% w* G% s9 f3 s$ A/ R
{" j5 }  `: q) l" W( s2 _- c
      if(tag[v]==0)- S9 |) w* ^- g: ]1 x
         DFS1(v);6 [7 d0 X* d. t; }7 I, K7 x2 E
}+ ]* y1 c2 Y2 q
}: g& Q5 b0 S9 A9 f9 R; o( J. g
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
: |/ C3 w# r8 J. W& V# J* g{
0 I1 q: ~2 C0 c* R stack<int> s;
" b4 d0 n3 }1 L& [! z int tmp;
; x; F3 d7 L" Y$ ?4 N MultiAdjListNetworkArc<WeightType> *p,*q;" o! D9 n+ |4 A
for(int i=0; i<vexNum; i++)
5 c' S9 I* e. o3 I$ W+ a& U9 e( [       tag=0;; X- n# d, V% D; u
for(int i=0; i<vexNum; i++)
+ k9 [1 U% @7 G {
1 G8 H* K( g6 |) l8 X6 G% _       tmp=i;% x3 y  W/ n  B- J* V7 S  ^
      while(tag[tmp]==0||!s.empty())
0 |; q* i6 c! p+ z       {
& f4 X5 T/ H% t( f          p=vexTable[tmp].firstarc;/ v0 f1 c, }4 f/ R
         while(tag[tmp]==0)
, U# _) Y! |2 N! d% v          {: A8 L$ P) M0 g
            s.push(tmp);8 M* K5 D; ?- Z
            cout<<setw(3)<<vexTable[tmp].data;; Q6 S0 ]( K4 Y/ Y8 g0 Y. K  v
            tag[tmp]=1;
9 G! u0 B8 f! c: [% e! I             p=vexTable[tmp].firstarc;7 ^. E$ ~$ Y  J. z6 V3 X
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
( G4 j6 _7 ?* h             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);" q) b4 X1 c1 I- |
            //cout<<" 1st    tmp="<<tmp<<endl;
' J( {: k$ ]+ ?  L, d0 X          }
, c; M$ G& W2 i7 M) }' U' S          if(!s.empty()): m: @* B/ f: V6 A6 S! a
         {
# _* Q5 E) l% Z) w! W             tmp=s.top();7 L4 H8 r. n# S2 g
            s.pop();5 g# [4 n+ `6 V, |# h
            q=vexTable[tmp].firstarc;6 i* a% Y& i' q* l$ u& ]! o: h) w- N
            int t=tmp;+ H  [( |/ e" Y: H6 h+ Y% ]) c+ b, A
            while(q&&tag[tmp]!=0)
! _  f; A1 w( w  O             {
/ H) W3 Z( @( [9 k9 Z                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
9 M9 Y1 [, Z4 ?6 L* m9 F                   //cout<<" 2nd    tmp="<<tmp<<endl;. \# f5 R9 ]2 }+ b, x' S6 Z8 _: X
                  q=NextArc(t,q);- r4 k; H. a4 j  V8 P' [
            }' p4 k/ p& V  T5 ~( Y6 Q
            if(tag[tmp]==0)
$ L+ _4 l, ~* o- U5 e/ \                   s.push(t);
$ ]! O% I- c  X( P* {; M9 h8 K             ///1、对应上面连通分支只有1个点的情况8 q- d% k* o: Y7 `+ f8 e
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈& f# j! H: s1 G, \' d9 \
            ///tmp要么等于找到的第一个未访问节点，" ?, ~( o7 ?6 F! [' E% e
            ///要么等于与t相连最后一个点（已被访问过）" B7 h8 x1 w/ x+ N/ i
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点( P* B& U- _* v1 x  x6 M
         }
& z8 F8 y! p( [       }' ^5 O; N3 f1 X' y, L, Q3 ?) R
}! D) d5 H4 C. j6 B6 z/ z* s8 I( u
}
* h' A4 V* s0 |+ ^' A//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
! [; @5 k0 a9 \0 Z7 atemplate<class ElemType, class WeightType> int& k% {! v* q0 L1 `! ?0 t5 u: S
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
" r6 f; [: L( |# p{# L6 J8 A% J/ _7 C5 L
if(head==pre)
( F4 A  U( l, ^* ?; x       return -1;* K) U$ C% u+ L' S% J
) A: V- Q% Q6 @; u
MultiAdjListNetworkArc<WeightType> *p;
  u1 H$ g  j5 f% ]& \; S p=vexTable[head].firstarc;
) j, D) h& q( I1 g; n if(pre==-1&&p!=NULL)3 @- v2 T( {1 N
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
( H2 t' }" g+ T //pre!=-1&&p!=NULL* O) L) }$ C% a. I: d9 Q  \
while(p!=NULL)$ g  V& U2 J. H" r6 f: z0 l" M
{
' a$ g2 ^5 A: E( n* B       if(p->adjVex1==head && p->adjVex2!=pre)" Z% y$ w' [5 I5 e# j3 T
         p=p->nextarc1;. q- m% u! L& k' s- {
      else if(p->adjVex2==head && p->adjVex1!=pre)
$ V5 [  I6 {0 w* V          p=p->nextarc2;
7 x* t$ H& t! k7 G5 A       else if(p->adjVex1==head && p->adjVex2==pre)
) o/ [2 ]1 S9 j1 t& W) k" g       {% A4 e+ i8 g  K( [2 K- S
         p=p->nextarc1;9 U' \. c9 [5 V: u1 B# A
         break;
" }& s4 c; W# J  c' W- g9 C       }  V3 E+ t& N) F$ ~
      else if(p->adjVex2==head && p->adjVex1==pre); i2 U7 J/ r6 l; g4 l+ Q8 h
      {
- g# O5 D8 y9 `3 t3 N/ H+ |          p=p->nextarc2;2 ?* o: s: s+ M. v' u& z# H: @
         break;
& S; t  L- F, d" B" H: K( X# }       }( w* ^: g% l8 L
}4 i- F4 P! J6 h( b7 h; @/ X& V, @0 a
if(p!=NULL)$ o0 Y1 a, T' T" u3 S7 T* c# @3 N
{
5 O" ^' O0 s" L; u       return p->adjVex1==head?p->adjVex2:p->adjVex1;) Q* o. ~/ M! }( ~
}
4 O2 @8 L! J! N' O. h* f else
' N3 q2 @, Y. [       return -1;
; _3 v$ y& W& \6 I}
+ Q( ]; P# o! \# \# H% p: Y6 ~6 O! h8 \3 N, w% }/ Z
$ u$ e' K) f" o. E3 m5 I  h' F" N
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
, z( `7 r6 @. n{% w: o% c7 w8 v! ^7 M: D% h9 M7 A
stack<int> s;
1 z* M$ a& H  d" \ int p,cur,pre;
& \* l/ X2 N7 _" ~ //MultiAdjListNetworkArc<WeightType> *p,*q;9 Y) p4 K. ?! ]+ Q2 _  T/ ]3 p# Z
for(int i=0; i<vexNum; i++) tag=0;//初始化
/ X- n4 \; ?2 G9 E
! A) f' f2 V1 v! c9 u' g: L0 p  T for(int i=0; i<vexNum; i++)- i+ ^9 k2 ^# }* {4 x
{
5 d6 N* h: J' o. E) m3 @; z, v       cur=i;pre=-1;5 [) ~8 R/ S6 D2 s' s# b+ W% O
      while(tag[cur]==0||!s.empty())& Q1 O# N/ e  X3 D6 Z9 d* c
      {
: @3 r% o$ |& v6 ~, R( G" U          while(tag[cur]==0)
" G' X+ h, {3 J          {
6 ~0 w7 H, p& q* a8 d, Y             cout<<vexTable[cur].data<<"  ";. }3 L5 Q) ]; O9 D
            s.push(cur);
2 c$ M2 n0 m1 e9 Y  q  y* Y             tag[cur]=1;  |8 G2 L9 C8 o8 n3 i& k
            //初次访问，标记入栈
+ m& O* `$ f# ?: `/ N( e# Q# e2 ?4 o0 l
            p=GetAdjVex(cur,pre);//p是cur的连通顶点3 j1 ]/ p8 [, M0 o6 w
            if(p==-1)
+ m. z: {" [# c4 T" A  K' g             {
) D3 l4 E- d" ?! Q6 i, B9 }                pre=cur;s.pop();# F* F  Z" Q3 K9 g, P' R2 g- M2 H$ ~
               break;
# Z( A; v" f; K# h  i/ R             }- _: H. V+ k/ O7 f, v+ e
            else" J: e0 Q' G; r! L
            {
* s+ G8 j' X! W4 c  f6 f2 w2 W9 G, M                pre=cur;
, C0 [* h* l% A2 K; B5 W5 J                cur=p;2 X( L9 {9 ^+ j) r, {
            }6 b  |% Y# f5 w$ A3 M$ w6 l
- f  I, D7 _9 ?4 g. h
         }
  C# v% K# c1 ]+ ?- B% a' K$ T          while(!s.empty())! ~" T1 |9 J8 k+ x8 f7 ?
         {
5 {9 P3 A" h/ ^             cur=s.top();! ~% l# I/ V9 ?. V
            p=GetAdjVex(cur,pre);
5 N4 J3 I5 p; G8 p, k. K' x             if(tag[p]==0)
" e) H1 x/ ~1 A) c0 z9 H8 C             {7 f; ]/ J) i' \" ~: G5 R2 m
                  pre=cur;
& [7 ]8 X; A" Z$ A                   cur=p;
: b0 j6 u+ T- ]8 L/ T! i, S                   break;
( D1 s3 G$ i1 q3 ^$ S. J+ I- K             }7 ~! m9 f+ ^- M7 ~$ X
            else
, Y, S3 B- s( g+ ]+ d             {
; N9 K: W5 f' }4 b. W                   pre=s.top();9 a3 W+ d+ J& H
                  s.pop();
, t( g# e( S( Q" K6 W: O$ {+ F) H             }
5 R# S/ l9 `' }) M# d7 w
2 n' n6 T9 |: s          }
+ V9 g8 `8 g) |. F% f
5 K! K: ~# }& S4 `       }
* I* ~7 F. M6 }8 L( f) R0 K# W }
+ \2 C( D( t$ L1 d3 k* o9 r+ ?}
" c& u* [/ q& Z! ~: _: ntemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()* K& _' q4 B0 f
{/ _4 W3 L4 X/ p2 x9 k
for(int i=0; i<vexNum; i++)4 ~3 \# l' n. V/ u$ |$ G0 e0 t
      tag=0;
5 ~( r7 ^/ j" j; P( ], L9 W4 F; { queue<int> q;/ G" n" g+ j2 n# F
int tmp,t;
7 k9 {3 i: l5 U' _- A% u9 P  j MultiAdjListNetworkArc<WeightType> *p;, P  m% b' U6 v8 a1 X! z
for(int i=0; i<vexNum; i++)5 V7 M; I3 X* ^6 q$ h# ^. ^$ V
{4 i- m: Y( \8 n0 T3 s* g
      if(tag==0)
6 c) a+ y# D& v' L       {
% H# A! G& U5 \" Z0 i6 W          tag=1;
/ p3 D2 K7 W) `          q.push(i);
* C. z2 g* C8 O7 S          cout<<setw(3)<<vexTable.data;' c( L$ a0 i2 W3 u( J, U- E. Y
      }9 i* T" P( ?2 f1 a7 ^% B1 @' i% q
      while(!q.empty())" d7 M- b8 f; @$ ]; L- ?) m& [
      {
3 G5 P* l: f9 h* J          tmp=q.front();8 o1 |+ p  e( {0 K. ^' m
         q.pop();
) K! h% _4 z1 l9 \7 ?. J' t. z* M          p=vexTable[tmp].firstarc;% f3 P4 j0 ]( Y3 a! c
         while(p!=NULL)  {0 ]: D% M. j6 _/ ~2 ^
         {
" [) v- l8 T! O# ^- l2 \5 n             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);. s1 |3 q4 v* _. k5 d$ c' o
            if(tag[t]==0)
1 o2 e" f6 c4 h& ]' i             {
# D. l; x& q0 p3 e$ h3 r                   cout<<setw(3)<<vexTable[t].data;
# n# i0 u" y, Z( T5 v                   tag[t]=1;9 _# l; Z" o- f- p' ?; Z* D0 E
                  q.push(t);) t+ A: N3 `* V+ k/ {# _
            }5 d! O- p. o; F$ I
            p=NextArc(tmp,p);3 s4 o2 r1 P! o8 M2 S
         }, o7 @1 _) R6 l& Q0 l
      }- C; i  H$ y. Y, Z
}
+ i! i# L" {# @4 |}
* z3 c! G; D6 I8 l6 Ntemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
& z4 A* \  O9 Z' I1 L" i. c{
" i1 K9 D9 V" c; q& P MultiAdjListNetworkArc<WeightType> *p;4 G; _3 D1 o" t8 v
cout << "无向图有" << vexNum << "个点，分别为:";; |9 s! O/ I3 s+ t. b. B- O+ J
for (int i = 0; i < vexNum; i++)
& U$ R: _2 \1 H. w$ `       cout << vexTable.data << " ";
% N3 o; u2 @! h; v9 \ cout << endl;
! B6 @; H# C7 a; I& B2 [- F4 Q' i cout << "无向图有" << arcNum << "条边"<<endl;
0 @1 x3 w$ X3 O/ X+ G for (int i = 0; i < vexNum; i++)& ]; ~+ e) I; H! t* Y3 }( P
{. J" ^) Y" m7 [: r( ~$ c
      cout<<"和" << vexTable.data << "有关的边:";
, B! u. |0 o8 O5 l       p = vexTable.firstarc;' a9 C1 J+ J) V9 _/ x
      while (p != NULL)
( w; m6 U" P* _       {
0 m+ q8 a. o7 \8 Y          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";- F$ g. j4 Y" k& z5 F* O: @* I! \) G
         p=NextArc(i,p);
' A9 C- u9 j3 G0 l. d) T+ c0 E       }8 `) ]8 P3 W/ D( a# W4 H4 m; N
      cout << endl;% R8 O1 ~8 l* G& l6 W- P/ V
}
$ \) f, i1 M6 l) Z# l}0 M) y4 S6 {% [
0 D( J& n$ ]* j

2 {% X! Q) o  P5 X; K邻接多重表与邻接表的对比
& u4 B( ~/ V% w- B/ G! w. i+ Z. _# }# K: e) A' m
邻接表链接' V3 T$ M6 @# K: m$ c0 T: u
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。% i0 u$ F& v$ r) K. u3 Q! y6 y
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。# V' S2 N) ?9 C" D, t( a+ q, n% V
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
, K2 V/ S) ~4 [) ~% y5 S$ L————————————————' n9 J/ f7 ?4 f1 [
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。) i3 u* R9 R' r; J
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
1 ?9 y' z; q4 B# G" z. V5 ?. z: i! {' m' j3 n- n
' {( e& M0 \6 V) O. b
2 v: i4 F8 u6 L: m2 h

5 V: @; d6 |  \& W) ]————————————————: B; @, J. U# t2 ^( S
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: Z2 X7 {; k$ ~原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* q' N8 A0 u( |* |4 {. O: d* c  w- W6 U0 X4 l9 k

1 M: G% f0 O, h" _