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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
( U" ^/ S# B7 I9 R9 Ldata域存储有关顶点的信息；# A' u4 M# B. M0 V& l W4 t( k( J/ O
firstarc域是链接指针，指向第一条依附于该顶点的边。
$ K3 P$ Z+ j, k/ e1 M所有的顶点结点组成一个顺序表。

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: H( m* c8 J5 o) b4 D( R4 b for(int v=0; v<vexNum; v++)
; F( o) x2 P+ H# E  n' i {: U5 A" A' m- |6 Q
      if(tag[v]==0)! ~$ Q% T1 W3 ^( C# m. [
         DFS1(v);
# W& ^) [+ |% Q }
. _- I+ [0 \2 r4 n) Q" F1 m! n}
5 ^4 a2 c6 f  stemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()0 t% S0 ^: r3 I/ R& {% `& j
{  r7 ^8 H9 ^4 i3 k
stack<int> s;9 T- Z9 y) e( }, \6 ?
int tmp;
, B2 |$ S9 ^, C) D9 G MultiAdjListNetworkArc<WeightType> *p,*q;
0 m: U/ u# {5 ?% ~ for(int i=0; i<vexNum; i++)7 U: A1 O* o2 V- i' q
      tag=0;1 ^9 v$ k0 }3 r2 r) i0 n% @
for(int i=0; i<vexNum; i++)  i* z+ z+ ]7 n
{
# z6 D1 p# U! W* I6 [       tmp=i;( p: D0 b' s7 K! ]2 ^4 `1 A
      while(tag[tmp]==0||!s.empty())
+ Z0 S* y! P7 A5 e8 a6 V8 H; ?1 I# N       {9 O0 b3 J3 ^6 R
         p=vexTable[tmp].firstarc;
/ V- T- Z) x2 G" O          while(tag[tmp]==0)
. l: N+ O6 W- I          {
6 w4 f  l6 ]0 x+ E             s.push(tmp);2 V* ]- y0 {5 e$ J
            cout<<setw(3)<<vexTable[tmp].data;
' x! ?& V5 a6 [5 j+ X& D" W             tag[tmp]=1;, W$ _: u+ N/ H% o1 q
            p=vexTable[tmp].firstarc;
: x! ]( a% K: Q  m1 X& A* L) q             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
+ b) h0 g- v, Y. ^7 w( a: k             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);4 z; \) `! U4 l7 a& L' q9 ]
            //cout<<" 1st    tmp="<<tmp<<endl;9 ?6 v0 a2 H, M+ r& ]+ I# X7 s3 v
         }( a4 z& ~& W$ L( O/ n% E
         if(!s.empty())
" F: |$ \( P: W  b6 s, Y' o          {
' O: m* Y  q3 G7 V# z             tmp=s.top();
: u. e9 I; B3 F             s.pop();: f. u4 \6 z5 p- V8 Z
            q=vexTable[tmp].firstarc;
" J2 O( U$ m0 n  b2 O1 n3 S  z             int t=tmp;- K% S: {) w, w! k) `
            while(q&&tag[tmp]!=0)
* K* D4 ?0 [- f6 F' P1 A8 Q6 F             {8 S- |9 Q1 S) [# r5 p7 u1 \& Z
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);5 C; Q( v# [6 s6 \8 c- }/ t
                  //cout<<" 2nd    tmp="<<tmp<<endl;* H. M) }  V5 X: P5 I
                  q=NextArc(t,q);3 f6 j( O+ i9 r
            }8 H3 T* B* S2 L/ g
            if(tag[tmp]==0)
! A% C; @( k) C                   s.push(t);
6 B' t* x& @2 Z1 U             ///1、对应上面连通分支只有1个点的情况
* v, w( U. Q# h9 j; v- v             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈, Q& Y4 N5 c1 }: e! w3 s
            ///tmp要么等于找到的第一个未访问节点，' l! e9 s2 m( A' @& r7 o8 }3 ~
            ///要么等于与t相连最后一个点（已被访问过）9 j. A2 J$ z- y& V- N1 N
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
6 Y( r, T' l# X" Z3 P* N          }
3 Z- j6 m# J, S1 \3 R8 Y       }4 i! N( h9 ^+ i  Z- ?# e6 ~
}
& v- z! b/ ]2 N- q}
3 Z2 |8 ]/ ^* @) s. ^. {; ?# U//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
/ _+ b6 ^/ l1 M, |! z; g" s$ btemplate<class ElemType, class WeightType> int' b& i: q" G1 r$ q
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre). H; G9 D" N- j6 K
{
! P% G3 l8 }6 L8 k if(head==pre)
' q( i. B0 y' @, e, L1 @$ z6 L       return -1;
1 v, M  q1 n. \
) m8 y6 w0 }" `4 ]& Z MultiAdjListNetworkArc<WeightType> *p;' @& K. Z9 N4 I& z9 F
p=vexTable[head].firstarc;4 d: D2 V# R# L0 i
if(pre==-1&&p!=NULL)
/ K$ ]4 z! d+ J# T( Q; ~; D       return p->adjVex1==head?p->adjVex2:p->adjVex1;2 T8 Z/ L: I, \& V" x( E% `
//pre!=-1&&p!=NULL8 {" k. v, y3 ^1 k0 h
while(p!=NULL)0 O% C9 {, I0 a7 C0 O/ c
{
. h8 H. i- C1 z0 u4 ~- ?; ^, b3 Q/ c       if(p->adjVex1==head && p->adjVex2!=pre)
# f' w; b0 g- t# L' X! c          p=p->nextarc1;
; K4 ?0 j/ u/ O" z% n       else if(p->adjVex2==head && p->adjVex1!=pre)
" v  G, [$ l1 _. @8 y. H          p=p->nextarc2;6 D7 o; Q  F2 }
      else if(p->adjVex1==head && p->adjVex2==pre)' ^* F6 X- l, S, I% i# G
      {
  Z: v" K" C1 q4 E8 Y          p=p->nextarc1;
+ E+ o8 a) ?5 w3 J* H3 a' [          break;3 w* e$ ]2 J) I4 h
      }
% `3 |# |( X0 e1 A1 l       else if(p->adjVex2==head && p->adjVex1==pre)
9 @+ M0 g# H! X. z: n& g& B) P       {5 U; ~3 e; M4 d/ X: G# s8 h0 H4 _
         p=p->nextarc2;6 Q" P; X. s2 k; X1 z
         break;" ]6 r. I$ O5 T- r, e. K& b! _8 r
      }; v- K* N' o" ^8 o& t
}: p0 q$ |3 H7 O8 q' r! V
if(p!=NULL): l- I0 Q  T3 I
{/ V" i! m! a9 Z; S
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
3 I9 H& v& B# V; D+ R; ?* Q0 [0 L }
) a% \$ B! o. m/ l else2 W9 y, H. R. z5 ?4 r9 U- [
      return -1;6 y' A5 o4 o, [) y( b  J
}
# V3 a; P( ~& n: ]6 I# K% q! g5 m& Y
1 M+ K6 M7 v2 f7 R. V. B, e* _
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()8 Y3 j. r2 n8 e
{. @9 \' x. [' l. x! j# g, o# X
stack<int> s;
& j! i3 A! J% R% N int p,cur,pre;2 C7 T2 [0 n* Q
//MultiAdjListNetworkArc<WeightType> *p,*q;
, @' E9 i& k1 h for(int i=0; i<vexNum; i++) tag=0;//初始化
8 z! {1 ~# I# P* E+ ~! Y) I
6 V+ _  [2 u& N4 `6 ^ for(int i=0; i<vexNum; i++)# p- f8 H4 l6 K0 |
{" }1 `  E# w$ R
      cur=i;pre=-1;" R8 q; @, J& s% [
      while(tag[cur]==0||!s.empty())6 `- X& k# E- T5 m
      {
. ]: X# D; C3 O6 J; L1 Z          while(tag[cur]==0)0 \4 p/ F3 f: o3 o! z
         {5 c9 H# Q/ l8 N" p; Z
            cout<<vexTable[cur].data<<"  ";; ], C. B: g. t+ K) ], n9 i/ \
            s.push(cur);
( ~) ?- j/ e# {+ _9 G% _0 V             tag[cur]=1;5 k" P0 C" `6 x) \. G# Z. a
            //初次访问，标记入栈% T" O8 q3 \' ~  L* x2 W" d

0 ~1 r; R) k8 f/ p/ g8 a" Y9 U/ M$ j             p=GetAdjVex(cur,pre);//p是cur的连通顶点
: Z. l" C8 u! L0 _" I/ F. e/ t             if(p==-1)
7 I9 R+ Z" M' p0 C             {
. W  w& Y5 ]6 ]7 G                pre=cur;s.pop();$ e. o8 m) @/ H+ \/ v
               break;4 ]: H. g8 m9 \. Q1 J5 c  [0 ]
            }3 @. Q) G7 P4 ~6 i9 l/ ]1 I
            else
" |2 ~3 p# W# U$ L# C, T. f+ {             {4 B+ H. w+ \" l( |
               pre=cur;) T7 ~" |: _4 {9 G  m4 ]% H, l
               cur=p;5 o; F; C' z+ M1 s4 \4 G. j/ K
            }  S$ r- G' j& D9 A! c2 _
7 s% ?% Z2 h% Z" ^" X5 N8 J
         }
5 i* T& [7 `6 n+ K5 B4 \4 v4 J% v          while(!s.empty())
3 F+ p. n+ r5 d% v7 I/ J          {
9 X5 `! ~; F, x* U, s/ s/ Y             cur=s.top();# ^( m& q' X8 w# C3 U
            p=GetAdjVex(cur,pre);1 ^& X0 f6 G% ]1 n
            if(tag[p]==0)5 y# S) E2 h6 Y5 g# x% V
            {
% ^- @5 g  u) A' G; f                   pre=cur;/ P% N  g7 u, {, X  v0 K
                  cur=p;  S  ]" r; v5 U$ {. @
                  break;5 L. H; J. c; p. c4 I8 d' f
            }0 U( S& B5 }3 p# i
            else
# B9 {6 k4 i' P( Y" Y4 s3 i/ ~+ {             {
- w% C+ _, |& X  ^! c$ v" ~                   pre=s.top();
( A1 d+ [: P! e- b+ H0 Y3 }! L                   s.pop();
3 M$ Z$ z# _5 e8 v0 I. `8 o* U             }" _' z# l7 }6 S- L0 H5 b& }& w

. a1 a1 M3 d& C3 t# M# f          }
% u/ Q' D6 [/ `; O4 S; c% I: g0 T8 I
      }
8 D. z/ {/ A+ l* g8 F }
4 }" e6 u! |( U! `1 A- z}% S, I+ l! b+ k& N$ u/ C3 ^
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
4 b- p- ^) T: ~: ?{
* i1 n6 M8 j! }. ~* H; V; o# v for(int i=0; i<vexNum; i++): J0 ~! G+ y3 T& I+ H4 u5 i0 i
      tag=0;
3 g* V3 K( g  g* `1 E0 Y; n queue<int> q;
+ z9 S7 T; u2 J$ e int tmp,t;, V9 Z/ V, ?; g  y5 V
MultiAdjListNetworkArc<WeightType> *p;
( {/ v; Y3 c. l8 [ for(int i=0; i<vexNum; i++)
$ @7 z  U/ Y* N+ h1 S {% z7 Z2 Q6 J1 o$ m
      if(tag==0)6 K. S4 q2 b% u
      {1 f/ F2 d! p" @5 Q
         tag=1;3 L5 q# t1 m0 d# a4 h
         q.push(i);
  a5 Z4 u! {7 B0 d# Q+ W          cout<<setw(3)<<vexTable.data;& f( b7 A2 D# ?" u" H0 f
      }. o! n) z- v: k6 q
      while(!q.empty())
! y& Q2 Q& K0 F       {
$ [  }, G, J0 t  U; V          tmp=q.front();
  u- E3 p! u( K* t          q.pop();
5 d* M: w: E0 h1 ]8 w1 _          p=vexTable[tmp].firstarc;
& u( G7 x' ^& t          while(p!=NULL)
' C, F! N3 ?: A3 B8 G( ?" B- g" k          {
4 ^: U( V& O+ d  a/ O$ H+ L7 N7 l             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
/ K  Y! R; O6 H9 ^7 S             if(tag[t]==0), B& g* D; @1 P
            {! r7 _# ?5 f0 L/ F0 _; ~% [2 c
                  cout<<setw(3)<<vexTable[t].data;
. m0 O; O/ ^  z9 W/ s* s                   tag[t]=1;
2 k* u. d! M$ V                   q.push(t);
9 E( k1 ]3 X& \/ R             }
) i  F0 V3 w8 _             p=NextArc(tmp,p);
. h( o) p0 [- c4 Q, G          }
! x" b, {2 \+ `" L5 T) e/ {       }- l1 M6 J8 B5 M! x! S: }
}
) P* F* P0 m; n, f  Y, }+ o}
- y0 }3 N& q. jtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()' a7 S8 G9 ~% V; B. t
{
0 {6 C, o8 _* e5 E! ^1 I+ W MultiAdjListNetworkArc<WeightType> *p;
6 Q3 ?) \1 A- O4 l6 T* Q cout << "无向图有" << vexNum << "个点，分别为:";
- |: K4 J# s! _0 t) y+ Z for (int i = 0; i < vexNum; i++). P" w6 R% k# V  z* e8 W
      cout << vexTable.data << " ";/ v# G/ s  B/ c$ R/ {% u% e4 R1 x. W
cout << endl;
3 y5 D2 a/ L$ @2 x5 [- S7 ^# E cout << "无向图有" << arcNum << "条边"<<endl;6 {8 P: V$ e/ S# s9 _1 E: O- L3 Z
for (int i = 0; i < vexNum; i++), {& s% {5 C% a$ ^
{4 o% U0 J* s0 f3 ^
      cout<<"和" << vexTable.data << "有关的边:";& ^' r' g7 P4 m/ S6 p. M: x" m
      p = vexTable.firstarc;
4 _4 x" l2 B: x       while (p != NULL)
6 }$ i: y+ e2 P$ i. ?5 D+ B, J       {, }! l1 f( f# V
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";1 _# S8 T3 d; ~5 ?; ^5 ?
         p=NextArc(i,p);
+ x( G( `$ `& n3 [7 H" \! ~       }
# C9 m" R7 G6 n9 u6 m5 U+ x       cout << endl;& b; W: B# D. G9 V
}
1 I( J, ^; R4 u* E2 x. [+ A% V}
, \( T2 `& n+ O6 A5 ?& \3 _6 D0 l, C) s3 K5 L7 O1 T

% V8 R7 a  C$ k1 q/ I! O$ K+ r# K* n邻接多重表与邻接表的对比
0 F' h. y5 X  p- e$ p" }  k0 A# R* Q1 M4 ^' v$ a+ U
邻接表链接
: F: `6 b, g! |* U% Q4 Y. Y* O在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。& v: T5 l" ~# L$ s+ P; `8 l0 l7 o+ Q
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。. O( E7 }2 i; Z* `
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。& f+ i' L: v9 X% L4 m, r" S
————————————————
) G* C$ a3 x* R4 L8 r+ U版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' n9 ~9 ]- b3 _7 g4 J1 v原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958

9 c# ]6 @% m$ q" A8 `# i1 _
4 M' ~1 I  C% }( _; N
& x" z2 s2 E+ a! B8 e3 o( ]
' t( @6 M$ ]* a( O/ O————————————————" ]& b( `, L- G8 K9 V( y
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。7 D: U1 F2 L/ i. J8 }6 s- v; B
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
2 J/ c: Z% _  L* Z% l* g/ l' [, n+ n3 s3 s5 j: L4 y) p

% @/ L6 s' W9 {( X